프로그래밍/알고리즘

BFS를 이용한 완전 탐색조건: 모든 간선의 가중치가 동일할 때결과: 한 정점에서 다른 모든 정점까지의 거리구현 방법 / 시간복잡도: 큐 / $O(V+E)$ 간선에 가중치가 없거나 모두 동일한 경우 단순 탐색으로 $O(V+E)$만에 최단 경로를 찾을 수 있다.더보기from collections import dequedistances = [None] * Vqueue = deque([0])distances[0] = 0while queue: target = queue.popleft() for next_target in graph[target]: if distances[next_target] == None: queue.append(next_target) distances..

투 포인터 알고리즘이란?투 포인터 알고리즘이란 일차원 배열에서 말 그대로 2개의 포인터를 이동시키며 원하는 값을 찾아내는 알고리즘을 의미한다.참고로 두 포인터간의 간격이 항상 동일한 경우 슬라이딩 윈도우 알고리즘과 동일해진다. 어떻게 구현할까?두 포인터의 위치를 저장할 변수를 만든다. (주로 left, right와 같은 단어를 사용한다.)두 포인터의 초기 위치와 탐색 조건을 지정한다.초기 위치는 left = right = 0으로 지정하거나 left = 0, right = n - 1로 지정하는 경우가 많다.탐색 조건은 left 탐색 조건을 만족하지 않을 때까지 left나 right 포인터를 옮긴다.각 포인터는 계속 한 방향으로 움직여야 $O(N)$의 시간 복잡도가 보장됨에 주의한다. 구현해보기 (Pytho..

서로소 집합이란? 서로소 집합(분리 집합; Disjoints Sets)이란 공통 원소가 없는 집합들을 의미한다. 주로 트리 형태로 구현하며, 원소가 어떤 집합에 속해 있는 지 찾는 Find 연산과 두 집합을 합치는 Union 연산을 사용해 Union-Find라고도 불린다. 서로소 집합은 그 자체로도 자주 사용되지만 다른 자료 구조나 알고리즘에 적용되는 경우도 많다. (크루스칼 알고리즘, 그래프 사이클 판별, 동적 연결성 판정 등) 구현해보기 (코드) 서로소 집합은 트리 구조를 이용해 구현할 수 있는데, 같은 루트 노드를 가진 원소들은 같은 집합에 속해 있는 것이라고 보면 된다. 초기 단계 초기 단계에서는 각 원소들이 서로 다른 집합에 속해있다. 따라서 각 원소들은 자기 자신을 부모로 가진다. 각 원소들의..

스위핑이란? 스위핑(Sweeping) 기법이란 말 그대로 어느 한 쪽에서부터 휩쓸고 지나가는 알고리즘을 의미한다. 즉, 주어진 요소를 특정 기준에 따라 정렬한 후 순차적으로 처리하는 기법이 바로 스위핑이다. 정의에서도 알 수 있듯이, 스위핑 기법은 굉장히 단순하면서도 범용적으로 사용된다. 같은 스위핑 기법을 활용하는 문제더라도 사용해야 하는 자료 구조나 구현 방식은 천차만별이다. 따라서 스위핑을 적용하는 경우 대부분 다른 자료 구조나 알고리즘에 대한 이해와 적용이 필요하다. 대표적인 문제들(BOJ) [2170] 선 긋기 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,..

배낭 문제 배낭 문제란 버틸 수 있는 무게가 정해져 있는 배낭이 있고, 일정한 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 하는 방법을 찾는 문제이다. 배낭 문제는 짐을 쪼갤 수 있는 경우(Fractional)와 없는 경우(0-1)로 구분된다. 쪼갤 수 있는 경우는 무게당 가치가 높은 물건부터 그리디하게 넣으면 $O(N)$만에 해결할 수 있다. 쪼갤 수 없는 경우는 다항 시간에 해결이 불가능하며, 다이나믹 프로그래밍이나 백트래킹과 같은 방법을 적용해야 한다. 이 글에서는 다이나믹 프로그래밍을 이용해 0-1 배낭 문제를 해결해보려고 한다. 점화식 세우기 $i$번째 짐까지 고려했을 때, 무게 제한이 $j$인 배낭에 담을 수 있는 최대 가치를 $f(i, j)$라고 하자. 각 짐을 고..