문제 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 윗줄에서 1, 3, 5를 뽑으면 첫째 줄과 둘째 줄에서 동일한 집합을 만들어낼 수 있다. 여기서 생각해볼 수 있는 것은 결국 다른 것들은 고려할 필요없이 첫째 줄과 둘째 줄에서 같은 열에 놓이는 대응되는 숫자들이 중요하다는 것이다! 여기서 좀 더 추상화를 해보자. 위의 표를 둘째 줄의 노드가 윗줄의 노드를 가리키고 있는 한 방향 그래프로 바꾸어 생각해보면, 다음과 같은 연결..
문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 그래프 탐색 문제였다. 각 노드를 기준으로 모든 노드에 대해 거리를 구해주는 문제였다. 모든 노드에 대해 거리를 구한다는 점에서 플로이드-와샬 알고리즘을 적용해서 푸는 방법도 있지만, 나는 BFS를 이용해서 풀었다. 언뜻 보면 복잡해보이지만, 아주 간단하다. 매 탐색시마다 visited를 초기화시키고, 인접한 노드를 방문할 때마다 거리를 기록해주면 된다. 별개의 리스트를 이용할 수도 있..
문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 언뜻 보면 백트래킹 문제 같은데, 그리디 문제였다. 이 문제의 경우, 만약에 '-'연산자가 하나라도 있으면 뒤에 나오는 피연산자(숫자)들을 모조리 빼주는 것이 최적의 방식이었다. 다음의 예시를 보자. 55-50+40 -> 55-(50+40) = 55-50-40 = -35 55-50+40-20+30 -> 55-(50+40)-(20+30) = 55-55-40-20-30 = -85 이 ..
문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 그리디 알고리즘 문제였다. n이 최대 100,000이므로 관건은 O(nlogn) 안에 풀어야 한다는 것이었는데, 이 문제의 경우 O(n) 안에 풀이가 가능했다. "첫 번째 점수인 서류심사 성적순으로 정렬을 하고, 두 번째 점수인 면접 성적을 비교해서 합격자를 결정하면 된다."라는 기본적인 아이디어는 모두 비슷할 것이다. 하지만 두 번째 점수인 면접 성적을 비교하는 ..
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 처음엔 그래프만 보고 바로 너비 우선 탐색으로 풀었는데, 시간초과가 떴다. 다시 보니 치킨 거리를 구하는 데엔 O(1)로 충분하기 때문에 그래프 탐색이 필요없는 문제였다. 입력을 받을 때 집(1)과 치킨집(2)의 좌표를 저장한다. 조합을 이용해 m개의 치킨집(2)을 선택한 후, 각 집마다의 치킨 거리를 구한다(여기선 m이 작기 때문에 min함수를 이용했다). 그 다..
