기록
기록

기록

163개 문서
47편 · 24일모든 날짜

모든 날짜의 글

163개 문서 · 14 / 17페이지

문서게시일
Disjoint Set

MST의 크루스칼과 같은 알고리즘에서 유용하게 쓰이는 Disjoint Set에 대한 간단한 정리

자료구조 / 트리
BOJ 2252 (줄 세우기)

풀이를 보면 매우 당연하지만, 그래프에 대한 개념이 확실히 되어 있지 않다면 아이디어 발상이 어려울 수 있다. 어떤 순서를 강제하는 것을 edge 연결로 볼 수 있고, 이런 조건을 만족하게끔 해둔 다음에 방문하지 않은 노드부터 차례대로 dfs로 방문해 나가면, 제일 끝에 도달하는 녀석이

풀이 기록 / BOJ
BOJ 9252 (LCS 2)

LCS는 Longest Common Subsequence의 약자로 이 문제 제목에도 대놓고 쓰였다. 처음 접했을 때 생각하기 어려운 DP이고, 개같이 멸망. 아래 URL의 풀이를 거의 그대로 참고했다.

풀이 기록 / BOJ
시간 복잡도

시간 복잡도 관련 정리

공부 / CS
BOJ 17404 (RGB거리 2)

기존 RGB거리 문제의 강화판. 그래도 최근 DP 짬밥이 있어서 그런지 처음에 막혔어도 힌트 안보고 최종 풀이에 성공했다. 풀이 방식에는 여러가지가 있어 보이는데, 나는 DP 차원을 확장하는 것으로 해결했다.

풀이 기록 / BOJ
벡터의 외적

벡터의 외적은 두 벡터가 이루는 각도를 알아낼 때 매우 유용하다. 특히, 두 벡터가 서로 평행일 때 외적값이 0이 된다는 사실은 잘 알려져 있다.

공부 / 수학
Convex Hull

기하 문제에서 많이 쓰이는 볼록 껍질 알고리즘 Convex Hull에 관한 정리

알고리즘 / 기하
진법

진법에 관해 정리해본다. 2진법은 특히 Computer Science와 관련성이 높다.

공부 / 수학
Heap

Heap 관련 정리. Heap은 주로 Array로 구현하며, 가장 큰 아이템이나 가장 작은 아이템을 O(1)의 시간복잡도로 구할 수 있으며, 이를 업데이트 하는데에 O(log n)의 시간이 걸리는 자료구조이다. set 처럼 k 값을 가지는 아이템을 찾거나 할 수는 없지만, 구조가 비교적

자료구조 / 트리
LCA

LCA는 Least Common Ancestor의 약자이다. Tree에서의 공통 조상을 찾는 문제에 사용되는 알고리즘이다. 공통 조상이 여러개 있을 수 있으므로, 그 중에 제일 빠른 조상을 LCA로 정의한다. input으로는 서로 다른 두 Node가 주어진다. 이 두 Node를 l과 r

알고리즘 / 그래프

서비스 열기

열기 방식을 선택해 주세요.

새 브라우저 탭에서 열기현재 화면을 유지하며 별도 탭에서 사용합니다.

로그인이 필요하거나 창 안에서 열리지 않는 서비스는 새 브라우저 탭에서 열어 주세요.