백준 8980 택배 문제 풀이
백준 온라인 저지, 8980번: 택배 도입 주어진 구간별로 배송이 필요한 택배 상자 양이 평이한 경향을 보인다면, 다소 많은 택배 상자의 배달을 요구하는 긴 구간보다 양이 적은 짧은 구간을 여러 개 선택하는 것이 더 낫다. 1번 마을에서 2번 마을 구간 $A$에서 10개의 택배 상자 배송을, 2번 마을에서 3번 마을 구간 $B$에서 5개의 택...
Park Jonghyeon
백준 2597 줄자접기 문제 풀이
백준 온라인 저지, 2597번: 줄자접기 도입 줄자를 접어 만나도록 할 두 점에 대해서, 두 점의 중점을 기준으로 중점의 한 편에 위치한 모든 점을 대칭 이동하여 대응한다. 문제 풀이 편의상 여기서 조금 더 확장하여 다음의 규칙에 따라 처리한다. 처리 대상의 두 점의 중점을 구한다. 대칭 이동: 항상 중점의 오른쪽에 위치한 모든 점과...
데이크스트라 알고리즘
도입 그래프 문제에서 BFS와 DFS는 용이하게 사용된다. 하지만 BFS/DFS는 간단한 형태의 그래프에서만 제대로 사용할 수 있다. BFS/DFS에서는 모든 간선을 동일한 것으로 가정했다. BFS/DFS에서의 정점 간의 거리는, 시작 정점으로부터 도착 정점까지 이동하는 과정에서 정점을 방문한 횟수로 계산되었다. 모든 간선의 거리를 1로 간주한 것...
백준 16953 A → B 문제 풀이
백준 온라인 저지, 16953번: A → B 도입 어떤 그리디 문제는 명시적인 그래프 표현이 없더라도 그래프 탐색 전략을 사용하여 해결할 수 있다. 사실 이상한 이야기는 아니다. 그래프 탐색도 반복 과정을 사용하는 다른 알고리즘과 마찬가지로, 목표를 달성하기 위해 반복 과정을 어떻게 사용할지, 다음 반복과 이번 반복에서의 상태가 어떻게 변화해야하...
백준 14940 쉬운 최단거리 문제 풀이
백준 온라인 저지, 14940번: 쉬운 최단거리 도입 쉬운 최단거리 문제는 전형적인 형태의 격자 그래프에서의 BFS/DFS 문제이다. 그래프 탐색이 익숙하다면 쉽게 구현 가능하지만, 충분히 경험하지 못했다면 상태 전이 방법을 고민해야할 수도 있다. *사실 모든 그래프 탐색 문제는 그래프를 탐색하면서 상태를 함께 전이해야 하므로 이 문제의 특징은 ...
LDPC 코드의 반복적 디코딩 방법
도입 LDPC(low-density parity-check) 코드는 반복적 디코딩(iterative decoding)으로 섀넌 한계에 가까운 성능을 달성했다. LDPC 코드를 디코딩하는데에는 여러 알고리즘을 사용할 수 있다. 대표적으로 SP(sum-product; 합-곱, 혹은 BP; belif-propagation) 알고리즘이 최적의 성능을 보이...
동적 계획법
도입 동적 계획법(DP; Dynamic Programming)은 계산한 값을 임시로 기록해두었다가, 이후에 다른 계산에 활용하는 최적화 전략이다. 동적 계획법을 적용하는 전형적인 방법이나 시나리오는 있지만 정해진 구현이 있는 것은 아니므로, 특정한 알고리즘보다는 문제해결에 사용할 수 있는 패러다임에 가깝다. 동적 계획법에서 사용하는 전략들은 분할 정...
백준 7576 토마토, 7569 토마토, 17114 하이퍼 토마토 문제 풀이
백준 온라인 저지, 7576번: 토마토, 7569번: 토마토, 17114번: 하이퍼 토마토 도입 백준 온라인 저지의 토마토 문제는 격자 공간에서의 BFS, DFS 탐색을 다루는 대표적인 문제이다. 기본적으로는 <7576번: 토마토>, <7569번: 토마토>, 그리고 <17114번: 하이퍼 토마토> 문제는 처리할 격자...
너비 우선 탐색과 깊이 우선 탐색
도입 너비 우선 탐색(BFS; Breadth First Search)과 깊이 우선 탐색(DFS; Depth First Search)은 어떤 대상을 처리할 때, 대상을 여러 개로 분할하여 처리하기 위해 반복 과정을 도입할 때 사용한다. 단순히 분할 가능한 대상을 처리할 때는 특별한 반복 과정 전략은 필요하지 않다. 일반적으로는 분할된 각 부분이 서로 ...
백준 1946 신입 사원 문제 풀이
백준 온라인 저지, 1946번: 신입 사원 도입 신입 사원의 선정에 고려되는 값은 두 가지이다. 다만 이 두 가지 값을 모두 고려하면서 신입 사원을 선정하는 것은 무리가 있다. 두 값 중 하나의 값을 기준으로 정렬한다면, 순서대로 각 신입 사원을 확인하는 반복 과정에서 두 값 중 하나의 값만을 고려하는 것으로 대응할 수 있다. 서류 심사 성...