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://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 다이나믹 프로그래밍 문제 풀이 이 문제는 동적계획법, 즉 다이나믹 프로그래밍 을 이용하여 해결할 수 있다. 처음에는 문제에서 주어진 number 와 관련된 점화식을 세워 접근하려 했으나 쉽지 않았다. 그래서 N 의 사용횟수에 따라 가능한 값을 구하는 방식을 사용했다. 이해를 돕기위해 한가지 예를 들어보자. N 이 5일 때, N 의 사용횟수에 따라 가능한 값들은 아래와 같다. N의 사용횟..

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..