https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 유형 다이나믹 프로그래밍 DFS 문제 풀이 이 문제는 DFS(깊이 우선 탐색) 과 다이나믹 프로그래밍 으로 각각 해결할 수 있다. DFS DFS 를 이용한 풀이 방법은 매우 간단하다. 별도의 방문처리 배열을 사용하지 않고, 조건에 맞게 재귀를 수행하면 된다. 이런 점에서 재귀를 이용한 구현 문제에 더 가깝다고 할 수도 있다. 소스 코드 import java.util...

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 유형 다이나믹 프로그래밍 비트마스킹 문제 풀이 이 문제를 완전 탐색으로 접근한다면, 시간초과 판정을 받게 된다. 왜냐하면 모든 도시를 탐색하는데 드는 비용은 순열의 비용과 동일하기 때문에 (N-1)! 의 시간복잡도를 가진다. 다이나믹 프로그래밍을 이용하면 반복되는 부분을 제거하여 시간복잡도를 줄일 수 있는데, 이해를 돕기 위해 한 가지 예를 살펴보자. N..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 유형 투 포인터 이진 탐색 문제 풀이 전체 용액의 수 N의 범위가 2 이상 100,000 이하의 정수이므로, 완전 탐색을 이용해서 풀 수 없다. 따라서 O(NlogN) 의 시간복잡도 문제를 해결해야 하는데, 다행스럽게도 입력 데이터가 이미 오름차순 정렬되어 있다! 이를 이용하여 문제를 해결하기 위한 가장 직관적인 방법은 투 포인터이며, 이외에도 이진 탐색을 이용해서 풀 수 있다. 투 포..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제상황 처음 이 문제를 접했을때, 저는 강의의 시작(start) 및 끝나는 시간(end)을 담은 Lecture 클래스를 만든 뒤에 입력 값에 따라 LinkedList 리스트에 담았습니다. 그리고 해당 리스트를 강의실 시작시간 기준 오름차순으로 정렬한 뒤, 리스트 내 첫번째 아이템을 기준 값을 정하고 순회하였습니다. 순회 값을 poll 한 뒤 기준 값의 끝나는 시간보다 순회 값의 시작 시간이 크거나 같으면 기준 값을 순회 값으로 바꿔주고, 그렇..