알고리즘

스위핑 알고리즘 보통 배열의 모든 원소를 앞에서부터 끝까지 한 번만 쭉 훑어보면서 문제를 해결하는 것을 스위핑 알고리즘이라고 합니다. 배열의 모든 원소를 한 번씩 훑어보는데 $O(n)$ 시간이 걸리지만 그전에 보통 정렬을 하기 때문에 총 $O(nlogn)$ 시간이 걸리게 됩니다. 스위핑의 가장 어려운 점은 훑어보기 전에 어떻게 정렬해야 하는지 알아차리...

누적 합 배열의 $i$번째 원소부터 $j$번째 원소까지의 합을 구하기 위해서는 단순히 for 문 한 번을 사용해 구할 수 있습니다. 하지만 이런 쿼리가 여러 번 계속될 경우 누적 합을 사용해 $O(1)$ 시간에 빠르게 구할 수 있습니다. 누적 합의 아이디어는 이전까지의 모든 원소의 합을 저장해두는 것입니다. 누적 합에서 주의해야 할 것은, 계산의 편...

너비 우선 탐색 너비 우선 탐색 알고리즘은 정점 s로부터 거리가 k + 1인 정점을 만나기 전에 s로부터 거리가 k인 정점을 모두 발견하는 알고리즘입니다. 기본 구현 기본적인 구현 모습은 위와 같습니다. 시작 정점 s를 큐에 넣고 방문 표시를 합니다. 큐기 빌 때까지 반복문을 돌면서 방문하지 않은 인접한 모든 정점을 방문하게 됩니다. 분석 총 ...

LCS 최장 공통 부분 수열(LCS)는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제입니다. LCS의 길이를 구하는 방법 LCS의 길이는 다음과 같은 점화식으로 다이나믹 프로그래밍을 사용해 구할 수 있습니다. 구하는 과정은 [여기](https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0...

서로소 집합 서로소 집합(disjoint set) 는 집합의 묶음을 관리하는 자료 구조입니다. 각 집합은 서로소 집합으로, 한 원소가 둘 이상의 집합에 속할 수 없고, 집합에 속한 임의의 원소가 대푯값이 되어 식별할 수 있습니다. find find 연산은 각 집합에서 대푯값을 찾을 때 사용합니다. 맨 처음에는 모든 원소는 자신만을 원소로 가지는 집...