이번글은 이진 탐색 트리(Binary Search Tree)에 대해 알아보고 구현을 해보도록 하겠습니다. 이번글의 BST는 균형의 개념이 안 들어간 BST입니다. (다음글에 균형잡는 AVL 트리를 이어서 적도록 하겠습니다.) 먼저 이진탐색 트리의 개념부터 살펴보도록 하겠습니다. BST는 이진트리의 확장된 버전입니다. (힙도 이진트리의 일종이지만 힙은 "완전 이진 트리"입니다.) 이진트리는 자식노드를 두개를 가지는 자료구조입니다. 이진트리를 기반으로 구현되어 있고 데이터를 빠르게 찾는데에 최적화 되어 있습니다. O(Log 2)를 탐색하는데 가집니다. BST의 핵심은 "삽입", "탐색", "삭제"입니다. 삽입의 핵심로직을 살펴보면 Root보다 값이 작다면 왼쪽에 데이터를 삽입하고 Root보다 값이 크다면 오..

Linear Search 보다는 상대적으로 복잡하지만 자료구조의 원소가 "정렬"되어 있을 경우 O(log n)으로 동작하는 이진 탐색을 반복문과 재귀함수로 구현해보도록 하겠습니다. 먼저 이진탐색의 로직은 정렬되어 있는 데이터의 첫번째 부분 first, 데이터의 마지막 원소 last 인덱스를 구한뒤 (first + last) / 2를 통해 mid인덱스를 구합니다. (나머지는 버립니다) 이후 mid인덱스에 들어 있는 값이 찾을려고 하는 값과 같다면 그대로 값을 찾은 것이고 찾을려고 하는 값이 mid인덱스에 들어있는 값보다 작다면 last를 mid - 1로 변경한뒤 first와 last를 다시 합한뒤 2로 나누어 mid를 다시 구해 줄 수 있습니다. 종료 조건은 first가 last보다 클 경우 입니다. fi..

이번 글은 정렬 알고리즘 중에서 Quick Sort에 대한 글입니다. 퀵 정렬은 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속합니다. 퀵 정렬은 합병정렬과 비슷하게 분할 정복(Divide And Conquer)알고리즘을 사용합니다. C++ STL의 sort()의 경우 순차열 [b, e) 원소들을 퀵 정렬로 수행하기 때문에 평균적으로는 O(N log N)의 시간복잡도를 보장을 하며 최악의 경우 O(N^2)의 시간 복잡도를 가집니다. 퀵 정렬의 원리는 pivot을 임의의 인덱스에 하나잡은 뒤 Left/Right Pivot을 양 끝으로 잡고 현재 Pivot보다 작은 값들은 왼쪽으로, Pivot보다 큰 값들은 오른쪽으로 옮기면 됩니다! 이후 Pivot을 제외한 왼쪽 부분과 오른쪽 ..

25206번: 너의 평점은 (acmicpc.net) 25206번: 너의 평점은 인하대학교 컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 그런데 아뿔싸, 치훈이는 깜빡하고 졸업고사를 응시하지 않았다는 사실을 깨달았다! 치 www.acmicpc.net 일단 문제를 잘 읽어야 한다는 것을 다시한번 느끼게 되었습니다. 현재 학교를 다니는데 학교 평점이 이렇게 계산되는지는 몰랐네요...;; 핵심은 "전공평점은 전공과목별 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값이다." 이부분인거같습니다. 저는 map 이진 탐색트리인 레드블랙트리를 통해서 학점에 따른 점수를 구할 수 있도록 하였습니다. P라면 continue 해주어야 겠지요. 또한 double타입으로 수를 더해..

https://www.acmicpc.net/problem/10811 10811번: 바구니 뒤집기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net 쉬운 문제이지만 reverse의 기능과 vector와 같은 container의 iterator가 무엇인지 모른다면 풀기가 어려워 보이는 문제입니다. 저도 처음에 조금 돌다가 풀었습니다. reverse()에는 vecotr와 같은 container객체의 iterator를 넣을 수 있습니다. iterator는 vector 객체의 주소를 가르켜주는 "도구"의 느낌으로 저는 생각하고있습니다. 따라서..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 후기 먼가 짝을 짓는거 같긴해서 stack을 잠깐 생각은 했지만 아닌거 같아서 pass... 이런식으로 표를 그려서 2시간정도 이리저리 생각을 해보았지만 아이디어가 떠오르지를 않았습니다. 물론 떠오른 아이디어는 있었습니다. 이중 for문으로 돌리면 가능하지만 시간복잡도상 사람수가 50만이라 50 * 50만이 되면 절대 풀 수 없다고 생각해서 - 구조체안에 이전 데이터를 넣어..

https://www.acmicpc.net/problem/15926 15926번: 현욱은 괄호왕이야!! 첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다. www.acmicpc.net 이전에 괄호왕 문제를 풀었었는데 그거랑 비슷하다고 생각해서 만만하게 생각했습니다...ㅠ 이전 괄호왕이라는 문제에서는 그냥 stack에 push, pop이 전부 였는데 해당 문제는 조금 다른거 같습니다. 일단 배열을 사용해서 1로 만든다음에 1인 경우만 카운팅하는 아이디어를 떠올리지 못했습니다. stack을 사용했으나 최대값을 찾으면서 pop을 할려는 로직을 구현을 하다보니 코..

https://www.acmicpc.net/problem/15353 15353번: 큰 수 A+B (2) C++17, C11, C99, C++98, C++11, C++14, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang) www.acmicpc.net 후기 및 분석 일단 문제를 보고 int는 당연히 안되고 long long도 안되기 때문에 Big Int나 string을 써야한다고 판단하였습니다. 하지만 BigInt는 써본적이 없어서 일단 string으로 구현을 하였습니다. (참고로 해당문제 예시입력이 long long 64번째 비트를 켰을 때 값인거 같았습니다. 그래서 long long안된다 판단했습니다...