부분집합의 합 2 (http://boj.kr/1208) 부분집합의 합 문제는 \(N\)의 제한이 \(20\)이기 때문에 모든 부분집합을 구하는 \(2^N\)의 방법으로도 풀 수 있었다. 하지만 이 문제는 \(N\)의 제한이 \(40\)이기 때문에 같은 방법으로는 풀 수 없다. 풀이부터 말하자면,배열을 반으로 나눠서 \(A\)와 \(B\)라고 했을 때,\(A\)의 부분집합의 합이 \(S\)가 되는 경우 + \(A\)와 \(B\)의 부분집합의 합이 \(S\)가 되는 경우 + \(B\)의 부분집합의 합이 \(S\)가 되는 경우를 구해야 한다.앞의 경우와 뒤의 경우는 그냥 구하면 \(2\times 2^{\frac{N}{2}}\)만에 구할 수 있고,가운데의 경우를 구하기 위해서는 \(A\)와 \(B\)를 합쳐야 ..
로고 (http://boj.kr/3108) 완전 탐색 문제라는 걸 알고 봤는데도 뭘 기준으로 탐색을 해야하는지 찾기 힘들었다. 이 문제는 격자에서 구역을 나누는 것 처럼(Flood Fill) 교차되는 사각형끼리 이동하며 생기는 구역의 개수를 찾는 문제였다. 사각형이 교차하는지 판단하는 방법은 여러가지가 있겠지만,사각형이 겹치면서 하나가 다른 하나를 완전히 포함하지 않는지를 확인했다. Flood Fill이나 BFS를 배울 때 안전 영역같은 문제만 있는 건 아니라고 알려주기 좋은 문제같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include using namespace std; int ax[1001], ay..
준오는 최종인재야!!(http://boj.kr/14657) 대회 때는 문제 자체도 이해하기 힘들었는데, 지금 다시 보니 트리의 지름 문제와 매우 비슷했다. 처음에 설명하는 문제 풀이 시스템은 사실 트리의 설명이다. 그리고 트리에서 가장 긴 경로(트리의 지름)을 찾는 것이다. 트리의 지름 문제와 다른 점은, 이 문제에서는 지나는 노드의 개수를 최대로 하면서 가중치는 따로 계산해야 한다. 트리의 지름을 구할 때는 아무 점이나 잡고 그 점에서 가장 먼 점 u를 찾고, u에서 가장 먼 점 v를 찾으면 u에서 v로 가는 경로가 트리의 지름이다. 그렇게 구현하니 맞기는 했는데, 저게 되는 이유가 잘 이해되지 않아서 그냥 모든 노드에서 자신이 지름에 포함되는 경우를 보도록 다시 구현했다. n = 2인 경우도 잘 고려..
버블 소트(http://boj.kr/1517) 버블 소트의 Swap 횟수는 최악의 경우 n(n+1)/2이기 때문에 직접 버블 소트를 해가며 횟수를 세면 시간 초과이다. 그렇기 때문에 다른 방법으로 알아내야 하는데, 기본적인 아이디어는, 버블 소트는 어떤 수가 자기 자리를 찾기 위해서는, 자신의 왼쪽에 있는 수들 중에서 큰 수들과 바뀌어야 한다는 점이다. 그렇다면 이제 그걸 어떻게 구할지가 문제가 된다. 이 방법은 여러가지가 있는데, 몇 가지를 고르면, 첫 번째 방법으로는 머지 소트 과정에서 그 수를 구하는 것이 있다. 머지 소트 과정에서 왼쪽 배열과 오른쪽 배열을 비교할 때, 만약 왼쪽 배열의 수가 오른쪽 배열의 수보다 크다면 Swap이 일어난다는 것이다. 즉, 왼쪽 배열의 수 > 오른쪽 배열의 수인 경..