알고리즘 별 문제 정리 (33) 썸네일형 리스트형 [C++] 백준 1516: 게임 개발 문제 이해각 건물에는 건설 시간이 존재한다.건설은 동시에 진행이 가능하고, 건물 순서상 필요한 건물이 모두 건설되었을 때 다음 건물을 건설할 수 있다.N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력하라.N: 건물의 개수 1 ~ 500(10^2)Di: 각 건물 건설에 걸리는 시간 1 ~ 100,000(10^5) 풀이N개의 각 건물을 짓는데 걸리는 최소시간을 구하는 문제이다. 각 건물마다 짓는데 걸리는 최소시간을 DP로 저장해놓고,순서가 주어진 그래프를 위상정렬을 하면 되는 문제이다.즉, DP와 위상정렬에 대해 둘 다 알고있어야 풀 수 있는 문제였다! 1005: ACM Craft 문제와 거의 같은 문제이다.https://dmoritle.tistory.com/entry/C-1005-ACM-Craft.. [C++] 백준 1915: 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 문제 이해n * m의 0과 1로 구성된 배열이 있을 때1로만 이루어진 정사각형 중 가장 큰 것의 넓이를 구하는 문제입니다. n, m : 1 ~ 10^3 완전 탐색으론 시간 초과가 났기에, DP를 사용해야겠다는 생각을 했는데 도저히 점화식을 못 찾았습니다. 도저히 감이 안 잡혀서 다음 포스트를 참고하고 풀었습니다. https://yabmoons.tistory.com/158 [ 백준 1915 ] 가장 큰 정사각형 (C++)백준의 가장 큰 정사각형(1915) 문제이다.[ 문제 바로가기 ] [ 문제풀이 ]1) 주어진 맵에서, 가장 큰 정사각형의 넓이를 출력하는 문제이다. Dynamic Programming으로 어떻게 구현해야 하는지 알아보자.. [C++] 백준 10492: 팰린드롬? https://www.acmicpc.net/problem/10942 문제 요약수열이 주어졌을 때, S ~ E까지의 수열이 팰린드롬인지 확인하는 문제.수열의 원소의 개수는 최대 2,000(10^3)개질문의 횟수는 최대 1,000,000(10^6)개 ※팰린드롬: 앞에서 읽어도 뒤에서 읽어도 같은 값을 나타내는 문자열. 풀이1. 처음 생각했던건 단순 브루트포스였다. 하지만 시간 제한이 0.5초였고,질문의 개수만 해도 10^6이라서 각 질문마다 팰린드롬인지 계산한다면무조건 시간초과가 나올 수 밖에 없었다. 2. 다음으로 생각한 건 DP이다.dp배열의 차원과 값을 설정하는 게 좀 시간이 걸렸다.2차원으로 dp배열을 만들경우 모든 원소를 써야 되는 게 아닌가? 라는 고정관념에 빠져 더 힘들었던 거 같다. 결국.. [C++] 백준 9252: LCS 2 https://www.acmicpc.net/problem/9252 LCS 1에서 발전한 문제이다!https://dmoritle.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251-LCS [C++] 백준 9251: LCShttps://www.acmicpc.net/problem/9251 모든 가능한 수열을 다 비교할경우 0.1초의 시간제한으로 인해 틀리게된다.이 문제의 경우 DP를 사용하면 편하게 풀 수 있다! 자, DP이므로 배열의 의미를 잘 지정하dmoritle.tistory.com안 풀어본 분들께서는 위의 포스팅을 참고해주시면 좋을 것 같다! 풀이LCS 1과의 차이점은 LCS인 문자열을 출력해줘야 한다는 것이다.dp배열을 다 구해둔 상태이니 역추적을 하면 될 것 같다. f.. [C++] 백준 14002: 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002 가장 긴 증가하는 부분 수열을 선행했다면 굉장히 쉽게 풀 수 있는 문제였습니다. 풀이int n; cin>>n; for(int i = 1; i >num[i]; dp[i] = 1; } for(int i = 2; i num[j]) dp[i]++; } }먼저 위와 같이dp[i] = i번째 숫자가 끝일 때, 가장 긴 증가하는 부분 수열의 길이로 설정하고,그 값을 구해줍니다. 한 개의 원소로 구성된 수열은 값이 1이기에 초깃값으로 설정해주고,원소의 범위를 늘려가며 가장 긴 증가하는 부분 수열의 길이를 구해줍니다. 조건문의 조건에 대해 살펴보겠습니다.먼저, 증가하는 부분 수열이기에 num[i.. [C++] 백준 2096: 내려가기 https://www.acmicpc.net/problem/2096 왼쪽으로 내려갈 때,가운데로 내려갈 때,오른쪽으로 내려갈 때 3가지의 경우의 수에 대하여 각각의 점화식을 세우면 쉽게 풀 수 있다고 생각되는 문제였습니다. 풀이dp[i][j][k] = i번째 행의 j번째 자리일 때 얻을 수 있는 최댓값 or 최솟값(k로 구분, 0은 최댓값 1은 최솟값) 왼쪽으로 내려갈 수 있는 건,이전 단계에서 왼쪽에 있을 때와 가운데에 있을 때입니다.dp[i][0][k] = dp[i-1][0][k] + dp[i-1][1][k] 가운데로 내려갈 수 있는 건,이전 단계에서 왼쪽, 가운데, 오른쪽입니다.dp[i][1][k] = dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][2][k] 오른쪽으로 내려.. [C++] 백준 17070: 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 dp배열의 값 설정문제에서 (N,N)로 이동시키는 방법의 개수를 물어봤으므로, dp[i][j] = (i, j)까지 이동시키는 방법의 개수라고 가정하고 시작했다. 이 문제는 좌표뿐만 아니라 방향값도 존재하므로 배열의 차원을 하나 늘려방향값도 저장하는 게 좋겠다는 생각이 들었다. 그래서 dp[i][j][k] = k의 방향을 가지는 (i,j)까지 이동시키는 방법의 개수로 가정했다. 처음에 파이프는 가로 방향으로 (1,2)에 끝이 위치하므로 dp[1][2][0] = 1; 다음과 같이 초기값을 설정했고,그 후에 점화식을 생각해보았다. 점화식 구하기dp[n][n][0] = 가로 방향으로 (n,n)까지 이동시키는 방법의 개수이다. 즉, .. [C++] 백준 1005: ACM Craft 문제 이해건물은 짓는 순서는 매 게임마다 주어진다.각 건물에는 건설 시간이 존재한다.건설은 동시에 진행이 가능하고, 건물 순서상 필요한 건물이 모두 건설되었을 때 다음 건물을 건설할 수 있다.특정 건물을 가장 빨리 건설할 때까지 걸리는 최소 시간을 구하여라.T: 테스트 케이스N: 건물의 개수 1 ~ 10^3K: 건물순서 규칙의 총 개수 1 ~ 10^5Di: 각 건물 건설에 걸리는 시간 1 ~ 10^5{X, Y}: 건설 순서W: 백준이가 승리하기 위해 건설해야 하는 건물의 번호 풀이특정 건물을 짓는데 걸리는 최소시간을 구하는 문제이다. 각 건물마다 짓는데 걸리는 최소시간을 DP로 저장해놓고,순서가 주어진 그래프를 위상정렬을 하면 되는 문제이다.즉, DP와 위상정렬에 대해 둘 다 알고있어야 풀 수 있는 문.. 이전 1 2 3 4 5 다음
