poksul_log

관련 알고리즘 : DP 문제 링크 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 n자리 숫자 중 계단수(각 자릿수마다 있는 수의 차이가 1인 수)의 개수를 구하는 문제이다. '일의 자리 숫자가 무엇인가' 와 'n(자리수)'를 기준으로 dp 식을 세우면 문제를 해결할 수 있다. n=2인 경우를 예를 들어 생각해보자. 일의 자리 십의 자리 개수 0 1 1 1 2 1 2 1, 3 2 3 2, 4 2 4 3, 5 2 5 4, 6 2 6 5, 7 2 7 6, 8 2 8 7, 9 2 9 8 1 십의 자리 숫자가 일의 자리 숫자가 무엇이느냐에 따라 영향을..

📍 다이나믹 프로그래밍이란? 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 컴퓨터는 연산 속도와 메모리 공간에 한계가 있기 때문에, 이를 최대한으로 활용해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수가 있는데, 이를 이용한 방법이 바로 DP이다. 📍 다이나믹 프로그래밍이 쓰이기 위한 조건 큰 문제가 작은 문제로 나눠질 수 있어야 한다. 작은 문제에서 구한 정답은 이를 포함하는 큰 문제에서도 동일하다. 다이나믹 프로그래밍은 1번 조건에 의해 분할 정복과도 비슷한 성질을 지니고 있지만, 분할 정복과 달리 문제들이 서로에게 영향을 끼친다. 📍 피보나치 수열 문제를 통해 알아보는 DP 다이나믹 프로그래밍의 대표적 예로 피보나치 수열 문제..

관련 알고리즘 : 재귀, DP 문제 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 해결 과정 문제를 보면, 어떤 아이디어를 SNS에서 퍼뜨리고자 할 때 얼리 아답터가 아닌 사람은 모든 친구가 얼리 어답터여야 아이디어를 받아들임 얼리 어답터인 사람은 친구가 얼리 어답터인지 여부에 관계없이 아이디어를 받아들임 즉, 얼리 어답터가 X인 사람 => 연결된 친구들이 모두 얼리 어답터----------- 얼리 ..

관련 알고리즘 : DP, 브루트포스 문제 링크 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 해결 과정 상담 완료에 걸리는 기간 : Ti 상담 시 받을 수 있는 금액 : Pi 문제를 보면, N일 후 퇴사하므로 N일 이후까지 진행되는 상담은 진행할 수 없다. 또한, 1일 이상의 상담을 진행할 시 그 상담이 끝날 때까지는 다른 상담을 진행할 수 없다. 퇴사까지 상담을 최대한 진행해 최대 수익을 얻어야 하므로 이전 값들을 저장하여 최대 이익을 구할 수 있는 동적 프로그래밍(DP)과 브루트포스를 이용하여 모든 경우의 수들을 비교해 최대 이익을 구할 수 있었다. 문제에서 제공한 일정표..

관련 알고리즘 : DP 문제 링크 : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 풀이 과정 처음에는 그리디처럼 파일크기를 제일 작은 애부터 먼저 더해줘야 하는 줄로만 생각했는데, 문제를 읽다 보니 dp를 이용하여 구간별로 최소값을 구하는 방법을 모두 탐색하여 그 중 최소를 구하는 것이 옳겠다는 생각이 들었다. 그래서 dp를 이용하여 문제를 해결하였다. 만약 구간이 [a,b]라면, [a, k][k+1, b] (이 때, a T; wh..

관련 알고리즘 : DP, DFS 문제 링크 : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 과정 무작정 상하좌우 네 방향을 모두 탐색하는 방법으로 한다면, 시간초과가 발생할 것이다. 따라서 dp를 이용한 메모이제이션을 통해 시간과 더불어 중복을 감소시켜 주어야 한다. 재귀를 사용하여 현재 좌표(x,y)에서 상, 하, 좌, 우 중 어느 곳으로 이동할 수 있는지 확인하고, 마지막 목적지인 (m,n)에 도착할 수 있는 경로를 찾을 때마다 ..