Skip to content
Beside the Wheel

태그: 알고리즘

LSM Tree
자료구조
LSM 트리는 로그파일 기반으로 작성되는 방식의 파일 구조이다. LSM 트리는 Append-only 방법이어서 쓰기작업의 효울성이 좋다. 작동 방식 쓰기 작업 LSM 트리는 데이터를 disk에 바로 쓰지 않고, 정렬된 메모리 테이블(memTable)과 로그파일에 먼저 쓴다. 메모리 테이블은 주로 레드-블랙 트리를 사용하여 키-값 쌍을 기반으로 정렬된 구조를 유지한다. Memtable이 설정된 임계값에 도달하면, 그 내용은 디스크에 파일로 저장됩니다. 이때 데이터는 정렬된 상태로 저장되기 떄문에, 이 파일을 SSTable(Sorted String Table)이라고 부른다. SSTable은 불변성을 지니며, 한 번 기록된 후에는 변경되지 않는다. 이 구조는 데이터 일관성을 보장하며 압축이 진행되는 중에도
Trie
자료구조
트라이는 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조이다. 트라이는 루트 노드부터 시작하고, 각 노드는 문자를 나타낸다. 그리고 문자열은 루트에서 리프 노드까지의 경로로 표현된다. 트라이 자료구조를 사용하면 문자열을 매우 빠르게 검색할 수 있다. 특히 접두사 검색에 효율적이다. (O(m) 시간, m은 문자열 길이). 큰 메모리가 필요하다는 단점이 있다. 접두사를 바탕으로 한 자동 완성이나, 문자열 매칭을 위해 사용할 수 있다. 구현 트라이의 한 노드를 구성하는 객체는 자손 노드를 가리키는 포인터 목록과, 문자열의 끝인지를 나타내는 bool 변수로 구성된다. 자손 노드 포인터를 저장하기 위해 맵이나 벡터를 사용할 수 있다. struct Trie { map&x3C;char, Trie*>
가장 가까운 두 점
알고리즘
2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 점을 x 좌표 기준으로 정렬한 다음, x좌표가 현재까지의 최소 거리 범위 안에 있는 점 중 y좌표도 현재까지의 최소 거리 범위 안에 있는 점들을 순회하며 최소값을 구하면 풀린다. 같은 위치의 점이 여러개 있을 것을 고려해서 multiset을 썼었는데 multiset을 쓰니 시간초과가 났다… 어차피 같은 위치의 점은 정렬 후에도 바로 옆에 붙어있을 것이고, 이 때문에 항상 S라는 set에 이전 점이 남아있는 동안 이후 점과 비교하게 되어 상관없다. include&x3C;iostream>include&x3C;algorithm>incl
담금질 기법
알고리즘
담금질 기법은 기본적으로 문제 공간에서 무작위 방향 중 에너지를 최소화하는 경향으로 상태를 확률적으로 바꾸며 해를 탐색한다. 마치 금속을 담금질하는 것과 비슷한 원리라고 해서 Simulated Annealing(모의 담금질) 이라는 이름이 붙었다. 이를 구현하는 방식은 다양하겠지만, 시뮬레이티드 어닐링은 다음과 같이 행동한다. 현재 상태와 인접한 상태를 하나 구한다. 그 상태로 변할 때 얼마만큼 이득인지/손해인지를 판단한다. 얻을 이득과 손해의 정도에 따라 확률적으로 그 상태로 이동한다. 여기서 인접한 상태란, 현재의 상태를 국소적으로 바꾸어서 만들 수 있는 상태이다. 담금질 알고리즘은 이 과정을 반복함을 통해서 최적해를 향해 나아가고, 와중에 더 나빠지는 해에 대해서도 가끔씩은 탐색을 해보면서 지역 최
볼록 껍질과 회전하는 캘리퍼스
알고리즘
볼록껍질(Convex Hull) 여러 점들이 막 주어져 있을때 모든 점을 포함하는 볼록한 다각형을 의미한다. 볼록 껍질에에서 연속한 세 점을 한 쪽 방향으로 잡으면 모든 결과가 같다는 것을 이용하여, CCW 방식으로 구할 수 있다. 볼록껍질을 구하는 대표적인 알고리즘인 Graham Algorithm은 점들을 정렬하는데에서 시작한다. 볼록껍질에 무조건 들어가는 점 하나를 잡는다. (보통 가장 x좌표가, y좌표가 작은 점) 그 점을 기준으로 기울기 순으로 정렬한다. 같은 기울기면 거리 순으로 정렬. 점들을 그룹에 순서대로 넣는다.  넣으면서 그룹의 제일 최근 3점의 ccw가 옳지 않으면 그 세 점 중 중간 점을 뺀다. 3~4를 반복하면서 1번점까지 돌아온다. 코드로 구현하면 아래처럼 된다. vector&
오일러 경로 테크닉
알고리즘
다음과 같은 트리가 있다고 가정해보자. 1번 정점이 루트이고, DFS 방문 순서대로 번호가 붙여져있다. 이 트리를 배열에 저장하면 각 정점을 루트로 하는 서브트리를 구간으로 나타낼 수 있게 된다. (번호가 DFS 방문 순서대로 되어있어야 성립한다. 일반적인 트리가 주어지는 경우 구간을 계산하기 위한 번호를 다시 붙여야 한다.) 구간의 시작지점은 각 정점이 처음 방문 되었을 때, 끝 지점은 그 정점에서의 DFS함수가 끝났을 때의 번호를 저장함으로써 알 수 있다. 이것을 이용하는 것이 오일러 경로 테크닉이다. 오일러 경로 테크닉을 활용하는 대표적인 문제로 회사 문화 2,3,4가 있다. 회사 문화 2 영선회사에는 상사가 직속 부하를 칭찬하
왜판원순회
알고리즘
외판원 문제는 그래프에서 모든 정점을 방문하여 시작점으로 돌아오는 최단경로를 찾아야 하는 유명한 문제이다. 왜판원 문제의 목표는 조금 다르다. 정점의 개수가 N개인 그래프에서 역시 모든 정점을 방문하여 시작점으로 돌아오되, 정확히 그 길이가 L인 경로가 존재하는지를 알아내야 한다. 다시 말해서, 경로의 길이가 L이고 크기가 N인 싸이클이 존재하는지를 알아내야 한다. Meet in the middle을 활용한 문제이다. 이론상으로는 구상했는데 복잡하게 생각하다보니 로직이 꼬여서 많이 고전했다.. claude와의 진지한 대화로 리팩토링해서 성공했다. 특정 점이 중간에 방문하는 점이라고 가정한다. 시작 점으로부터 해당 점까지 도달하는
직사각형 스위핑
알고리즘
직사각형 합집합 면적 구하기 기본적으로 각 직사각형의 꼭짓점이 되는 점을 x좌표 기준으로 스위핑하면서 각 점 사이의 사각형 넓이를 구하는 식으로 답을 구한다. 위 그림과 같이 두 직사각형이 주어지면, 노랑, 빨강, 파랑에 해당하는 사각형의 넓이를 각각 구한 후 더하는 것이다. 이를 위해서 우선 각 직사각형의 x 시작 좌표, x 끝 좌표와 y 시작 및 끝을 저장해놓는다. 그리고 x를 기준으로 정렬한다. cnt라는 이름의 세그먼트 트리에 y 범위에 대해 x 시작 좌표에서 +1, x 끝 좌표에서 -1을 해준다. cnt가 1 이상이면 (직사각형이 있는 구간이면) tree라는 이름의 세그먼트 트리에 직사각형이 있는 y 구간의 총 높이를 저장한다