혜랑's STORY

3주차 자유 문제 Prepare > Algorithms > Sorting 풀이 두 숫자의 차이가 가장 작은 수를 찾는 것이 문제이다. 먼저 숫자가 들어있는 arr을 정렬하고, 양 옆의 숫자들과의 차가 가장 작은 것을 저장해 둔다. 그 다음 두 번째 for문을 통해 가장 적은 차를 만드는 숫자를 찾아 result에 저장한다. 전체적 코드는 다음과 같다. vector closestNumbers(vector arr) { int minN; vector result; sort(arr.begin(), arr.end()); for(int i=1; i

3주차 자료구조 복습 Prepare > Data Structures > Stacks 풀이 스택을 사용하여 h1, h2, h3 배열의 데이터 합이 같아지도록 만드는 문제이다. 배열을 거꾸로 돌며 각 스택에 넣어주며, 합을 계산하였다. 이후 각 합이 가질 수 있는 모든 경우의 수를 계산하여 데이터를 제거할 스택을 골라 num에 넣어주고, switch를 이용하여 최상위 값을 제거하였다. 전체 코드는 다음과 같다. int equalStacks(vector h1, vector h2, vector h3) { stack s_h1, s_h2, s_h3; int sum1, sum2, sum3, num; sum1 = sum2 = sum3 = 0; for(int i=h1.size()-1; i>=0; i--){ s_h1.pu..

🖇checksec 32비트 바이너리 파일이고 Partial RELRO, Canary, NX가 설정되어 있다. 앞에서 학습한 Double Free 취약점을 이용하여 문제를 풀면 될 것 같다. 🖇IDA IDA를 사용하여 함수 목록을 확인해 보았다. 노트의 내용을 출력하는 함수, 노트를 추가하는 함수, 노트를 지우는 함수와 메인 함수가 있었고, 유용해보이는 magic 함수가 있었다. 역시 flag를 출력하는 함수였다. 위 함수는 index를 지정하여 해당 chunck를 free 시킨다. free는 chunk -> nodelist chunck 순서로 free 되고 이때 nodelist[] 안에는 free 해도 주소가 남아있어 악의적으로 사용 가능하다. 🖇Exploit Method 위에서 알게된 del_note(..

Double Free Double Free는 해제된 힙 청크를 다시 해제할 때 발생하는 버그이다. 힙을 해제하면 bin이라는 연결 리스트에 추가되고, 이는 힙을 재할당할 때 참조된다. 해당 버그가 발생하면 연결 리스트에 중복된 힙 주소를 추가하기 때문에 두 개의 객체가 동일한 메모리를 사용할 수 있다. ptmalloc2 할당자는 Double Free를 방지하기 위해 동일한 힙 청크를 연속으로 여러번 해제할 수 없도록 하는 코드가 존재한다. 해당 코드를 이해하고 우회하는 방법을 알아보자. // gcc -o dfb1 dfb1.c #include int main() { char ptr = malloc(32); char ptr2 = malloc(32); free(ptr); free(ptr); return 0; ..

2주차 자유 문제 Practice > Algorithms > Greedy 풀이 Serve time이 적은 고객부터 출력하는 문제이다. (Serve time은 Order + Prep time이다.) pair로 Serve time과 고객의 번호를 기억한 뒤, Serve time이 작은 사람을 기준으로 내림차순으로 정렬하였다. 그 뒤, p[i].secone(고객의 번호)를 차례로 result 배열에 넣게 되면 Serve time이 적은 고객의 번호가 순서대로 저장되게 된다. 전체 코드는 다음과 같다. vector jimOrders(vector orders) { vector p; vector result; for(int i=0; i < orders.size(); i++){ p.push_back({(orders[..

2주차 자료구조 복습 Practice > Algoritms > Greedy 풀이 A 배열의 아이템과 B 배열의 아이템의 합이 모두 k 이상이 되어야 한다. 이때 각 배열을 정렬한 후 한 배열에서는 최대값을, 다른 배열에서는 최소값을 꺼내어 더하면 모두 k 이상이 될 확률이 높아진다. 따라서 A 배열은 내림차순으로, B 배열은 오름차순으로 정렬한 뒤 두 값을 더한 값이 k보다 작다면 문제의 조건을 통과하지 못하기 때문에 바로 "NO"를 반환하였다. for문이 모두 종료된다면 모두 k 이상이라는 것이므로 "YES"를 반환하였다. 전체적인 코드는 다음과 같다. string twoArrays(int k, vector A, vector B) { vector temp; sort(A.begin(), A.end(), ..

1주차 자유문제 Practice > Algorithms > Greedy 풀이 최대한 많은 선물을 사기 위해 적은 값의 선물부터 골라야 한다고 생각했다. 따라서 prices 백터를 STL sort를 사용하여 정렬해 주었다. // sort 함수는 오름차순이 기본이다. //내림차순으로 정렬하고자 할땐, 비교함수를 사용해야 한다. sort(prices.begin(), prices.end()); 이후 순차적으로 선물의 가격이 남은 돈보다 작다면 선물을 선택하는 방식으로 문제를 해결하였다. 전체적인 코드는 다음과 같다. int maximumToys(vector prices, int k) { int cnt = 0; sort(prices.begin(), prices.end()); for(int i=0; i

1주차 자료구조 복습 Practice > Data Structures > Heap 풀이 문제를 살펴보면 배열의 최소값이 주어진 K보다 커야 한다. 이때 최소힙으로 배열을 저장하면 top값이 k보다 크다면 아래 데이터는 무조건 k보다 큰 값을 가지게 된는 것을 알 수 있다. 따라서 c++ STL에 구현되어 있는 priority_queue를 사용하여 최소힙으로 데이터를 저장하였다. // priority_queue는 최대힙으로 구현되어 있기 때문에 //compare인자로 greater를 넘겨주어 최소힙으로 사용할 수 있다. priority_queue pq; top 값을 최소로 만들어 주었으니 이 값이 만약 k보다 작으면서 priority_queue의 size가 1이라면 sweetness를 더 이상 올릴 수 없..