분류 전체보기 (69) 썸네일형 리스트형 [C++] 백준 2252: 줄 세우기 문제 이해- N명의 학생들을 키 순서대로 줄을 세우려고 한다.- 단 키를 각각 재는 것이 아닌 비교하여 순서를 정한다.- M: 키를 비교한 횟수 (1 ~ 100,000, 10^5)- N: 학생 수 (1 ~ 32,000, 10^4)- 답이 여러가지일 경우 아무거나 출력한다. 문제 풀이학생들의 키의 순서를 비교한 값이 나와있는 이 문제는특정 조합의 순서가 정해져 있는 그래프의 전체 순서를 결정하는 문제이다. 즉, 위상 정렬을 사용하면 쉽게 풀 수 있는 문제이다. 전체 코드#include #include #include #include using namespace std;int n, m;vector v[32005];int inDegree[32005];queue q;int main() { ios_ba.. [C++] 백준 2011: 암호코드 https://www.acmicpc.net/problem/2011 문제 풀이DP로 푼 문제이다. 출력에서 원하는 값을 dp배열의 값으로 설정하여,dp[i] = i번째 숫자까지 읽을 수 있는 해석의 가짓수로 진행했다. 예제를 통해서 문제를 풀어보자.쉽게 123으로 예시를 들겠다. 1. dp[1]의 값은 무엇일까?당연히 하나의 숫자만 존재하므로 해석의 가짓수도 A로 하나만 존재한다.즉, dp[1] = 1이다. 2. 그럼 dp[2]는?1과 2를 따로 구분하여 인식하거나, 12를 하나의 숫자로 인식하는 두 가지 경우가 존재한다. 먼저 첫 번째 경우이다.사실 각각의 숫자를 개별로 인식한다면 가짓수는 늘어나지 않는다.즉 dp[i] = dp[i-1]이라는 뜻이다.이때 숫자가 하나 있을 경우 즉, dp[0]의 .. [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] 오른쪽으로 내려.. 이전 1 2 3 4 5 6 ··· 9 다음
