DP
-
[백준] 1520번 내리막길문제 풀이 2020. 4. 5. 17:57
1520 내리막길 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이..
-
[백준] 2225번 합분해문제 풀이 2020. 4. 4. 00:12
2225 합분해 문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이) 다이나믹 프로그래밍 문제였다.배열을DP[K][N] = K개 골랐을 때 합이 N인 경우 라고 생각해줬다. 점화식같은 경우는 아래 그림처럼 이렇게 생각해줬다. 즉, N또는 N보다 작은 숫자를 K-1개로 만들었다면 거기에다가 합이 N이 되도록 하는 수 T를 더해주어 K개의 정수로 N을 만들 수 있다는 ..
-
[백준] 2533번 사회망서비스문제 풀이 2020. 3. 31. 21:31
2533 사회망 서비스 문제페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adap..
-
[백준] 2293번문제 풀이 2020. 3. 21. 22:07
2293 동전1 문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이) 시간제한이 0.5초의 문제로 dp를 사용해서 풀어야하는 문제였다.dp[i] = i원의 가치를 표현할 수 있는 경우의 수의 합 으로 두고 문제를 풀었..
-
[백준] 2579번문제 풀이 2020. 3. 21. 21:03
2579 계단 오르기 문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.따라서 첫 번째..
-
DP알고리즘 2020. 3. 16. 19:34
DP (Dynamic Programming) 동적계획법 개념 : 큰 문제를 작은 문제로 나누어서 푸는 문제 작은 문제들을 계산한 값을 여러 번 사용하기 때문에 Memoization (메모이제이션)이 필요하다. Memoization? 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해, 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 → 즉, 계산된 결과를 배열에 저장한 뒤, 다음 계산에서 필요하면 저장된 값을 불러옴. 시간 복잡도가 훨씬 줄어든다. 구현 방식 : Bottom-up 방식과 Top-down 방식 Bottom-up 방식 : 작은 문제부터 계산해 나가는 방식, for문 이용해서 처음 값부터 다음 값을 계산해 나가는 방식 Top-down 방식 : 큰 문제를 풀 ..