전체 글

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

서로소 집합이란? 서로소 집합(분리 집합; 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)$라고 하자. 각 짐을 고..

이분 탐색(Binary Search) 이분 탐색이란 정렬된 배열에서 범위를 반씩 줄여나가면서 원하는 값을 탐색하는 방법으로, 분할 정복(Divide and Conquer)을 사용하는 대표적인 알고리즘 중 하나이다. 이분 탐색이라는 단어를 모르더라도, 업-다운 게임을 해봤다면 한 번쯤 써본적이 있는 기법일 것이다. 위 그림은 파란색 표시된 값 9를 이분 탐색으로 찾는 과정이다. 각 상황에서의 중앙값과 찾고자 하는 값을 비교하며 범위를 줄여나간다. 구현해보기(코드) 두 변수 $low$와 $high$를 이용해 탐색 범위를 관리할 것이다. 초기 범위를 0 ~ (배열의 길이 - 1)로 두고 범위를 점점 좁혀나가면 된다. def binarySearch(arr, target): low, high = 0, len(ar..