백준

[C++] 백준 1874번 스택 수열

자료구조를 이용해서 푸는 문제. 스택 ADT에 대한 이해가 잘 돼있다면 쉽게 머리속에 그려낼 수 있다. 접근 방법 우선 예시로 주어진 테스트 케이스 1번 [4, 3, 6, 8, 7, 5, 2, 1]을 이용해서 살펴보자. 입력은 오름차순으로 이루어지므로 1, 2, 3, ...의 순서로 입력된다. 입력을 받을때마다 다음의 상황을 고려한다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 같다면 스택에 push한 후 pop한다. 이 때 수열에 넣어야하는 수와 스택에 있는 수가 같다면 계속해서 pop해준다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 다르다면 스택에 push만 한다. 예시상황으로 한번 살펴보겠다. 1 : 스택에 push하면 스택이 { 1 }의 상황이고 수열 [4, 3, 6, ..

[C++] 백준 10844번 쉬운 계단 수

다이나믹 프로그래밍 문제. 생각보다 너무 어려워서 이틀동안 계속 머리에 담아두다가 구글링의 도움을 받고 풀었다. 접근 방법 먼저, N자리 수는 N이 1일때는 1~9 2일때는 다음과 같다. 맨 앞자리가 1일때 : 10, 12 맨 앞자리가 2일때 : 21, 23 ... 맨 앞자리가 9일때 : 98 3일때는 다음과 같다. 맨 앞자리가 1일때 : 101, 121, 123 맨 앞자리가 2일때 : 210, 212, 232, 234 ... 맨 앞자리가 9일때 : 987, 989 따라서 다음과 같은 정리가 가능하다. 마지막 숫자가 0이라면 다음으로 갈 수 있는 수는 1 뿐이다. -> 마지막 숫자 앞의 수가 1인 경우만 마지막 숫자가 0이 가능하다. 마지막 숫자가 9라면 다음으로 갈 수 있는 수는 8 뿐이다. -> 마지..

[C++] 백준 9461번 파도반 수열

다이나믹 프로그래밍 문제. 친절하게 P(1)부터 P(10)까지의 값이 모두 주어졌다. DP는 Bottom Up 방식으로 풀면 주어지는 값이 많으면 많을수록 유추하기 쉽기 때문에 풀기 쉽다. 문제풀이 주어지는 값들의 규칙을 찾아보면 점화식을 바로 찾을 수 있다. n>=4일때, An = A(n - 2) + A(n - 3) 이다. 코드가 짧다. n이 4부터 시작하므로 1, 2, 3값은 초기화를 미리 시켜준다. 그리고 자료형은 long long으로 해주어야 오버플로우가 나지 않는다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creating ..

[C++] 백준 11727번 2xn 타일링 2

다이나믹 프로그래밍 문제. 처음에 이 문제를 풀 때 점화식을 잘못잡아서 계속 답이 이상하게 나왔었다. 그래서 어떤 방식으로 푸는지 구글링의 도움을 좀 받았는데, 역시 점화식을 구해서 푸는 방식이였다. 이런 문제 유형도 있음을 알아두어야 될 것 같다. 문제 접근 방법 먼저 An을 구할 때, A(n-1)에서 한 칸만 더 추가되는 방식이다. 이 때 2x1이 추가되는 것과 마찬가지 이다. 따라서 A(n-1)에서 2x1을 추가한 것 A(n-2)에서는 2 x 1 두개 추가한 것 : 그러나 이 방식은 A(n-1)에서 2x1을 추가한 것에 포함되어 있다. 1 x 2 두개 추가한 것 2 x 2 추가한 것 A(n-3)부터는 어차피 이미 다 포함되어 있으므로 생각할 필요가 없다. 따라서 점화식은 An = A(n-1) + 2..

[C++] 백준 10773번 제로

0을 부르면 최근에 적은 값을 지우고 아니라면 값을 넣는 문제. 최근에 있는 값을 빼야한다. -> 스택 문제 스택 자료구조를 쓰면 쉽게 풀 수 있다. 쉽게 맞출 수 있는 문제라 생각한다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creating an account on GitHub. github.com 코드는 위에서 확인이 가능하다.

[C++] 백준 2193번 이친수

DP 문제 이런 류의 DP 문제는 항상 1부터 차례대로 해 보면서 점화식을 세우는 것이 중요하다. 시도 방식 & 문제 풀이 점화식을 구해서 코드로 구현했다. 규칙성이 바로 보이므로 점화식을 찾는데는 문제가 없었다. 근데 여기서 N이 90이 되면 엄청나게 큰 수가 된다. 따라서 dp배열을 int가 아닌, long long형태의 배열로 만들어 주는 것이 중요하다. 처음 시도는 TOP DOWN방식의 재귀형태로 시도했는데, 시간초과가 났다. 그리고 위 방식대로 풀었는데, OVERFLOW가 나서 틀렸습니다 가 나왔다. 자료형을 바꾸고 나서는 바로 맞출 수 있었다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kim..

[C++] 백준 2156번 포도주 시식

다이나믹 프로그래밍 문제. 처음 문제를 보고 예전에 풀었던 계단 오르기와 비슷한 문제라고 생각했다. [C++] 백준 2579번 계단 오르기 다이나믹 프로그래밍 문제. 처음 이문제를 봤을 때 처음에 백트래킹으로 시도했다가 시간초과가 너무 많이났다. (생각해보면 계단 개수가 최대 300개 인데, 이를 고려하면 경우의 수가 2의 지수 kimyunseok.tistory.com 그런데 막상 문제를 풀어보니 엄청 많이 틀렸고, 반례들을 통해 잘못된 점을 알게됐다. 문제 접근방식 우선 조건으로 주어지는 건 간단하다. 최대한 많은 양을 먹어야 하고 3잔을 연속으로 먹는 건 불가능하다. 천국의 계단 같은 경우는 어차피 +1 아니면 +2였기 때문에 이 문제도 똑같은 방식으로 접근했다. 이 두 개 조건을 가지고 문제를 풀려..

[C++] 백준 1912번 연속합

DP 문제. 수를 연속해서 선택하는데, 어떤 경우에 해당하는 번째의 수가 최대값을 가지게 되는지 구하는 문제이다. 문제에 접근한 방식 문제를 읽어보고, DP Bottom Up 방식으로 접근을 시도했다. 값을 더했을 때 계속 양수인 경우, 계속해서 더해주면 그게 구할 수 있는 가장 큰 합이 된다. 값을 더했을 때 음수가 나오는 경우, 그 값을 더하지 않는 것이 더 큰 값이므로 더이상 더해주지 않고 새로 시작한다. 따라서 점화식은 최대값이 An이고, 현재 수가 Bn을 나타낼 때 An = max( A(n-1) + Bn, Bn)이 된다. 이렇게 두 개를 고려하고 문제를 접근하면 된다. 자세하게 고려하고 풀지는 않았는데, 지금 보니 왜 저렇게 생각했는지 풀었으면 더 좋았을 것 같다. 문제풀이 최대값을 갱신시켜 주..

[C++] 백준 1932번 정수 삼각형

다이나믹 프로그래밍 문제. 경우의 수를 나눠서 Bottom Up 방식으로 문제를 해결하면 된다. 처음에 그림을 보고 트리 -> 그래프 탐색인 줄 알았는데 문제를 읽어보고 그림을 그려보니까 다이나믹 프로그래밍이란 것을 알았다. 그림을 보면 각 노드에서 아래로 내려오면서 그 노드의 최대값을 갱신해 나가면 된다. 이 때 방향을 보면 맨 첫번째 노드는 각 전단계의 첫번째 노드에서만 온다는 것을 알 수 있다. 그리고 마지막 노드는 전단계의 마지막 번째의 노드에서만 온다는 것을 알 수 있다. 첫번째, 마지막 둘 다 아니라면 전 단계의 왼쪽, 오른쪽 노드에서 온다는 것을 알 수 있다. 점화식을 세우면 다음 그림과 같다. dp[i][j]는 i, j의 최대값을 저장하는 배열이고 triangle[i][j]는 i, j의 가..

[C++] 백준 1697번 숨바꼭질

그래프 탐색 문제인 줄 몰랐던 그래프 탐색 문제. 알고보니 모든 정점들이 서로 연결돼 있던 그래프였다는 것을 문제에서 설명해 주고 있었다. 이 사실을 질문 검색 게시판을 보다가 알게되었다. 처음 이문제를 보았을 때 수학 문제인 줄 알았다. 그래서 경우의 수를 나눠서 구현해야 하는 줄 알고 그렇게 시도했다. 결과는 틀렸습니다가 나왔다. 그래서 어떻게 풀어야 할까 고민하면서 질문 검색 게시판을 보았다. 두번째 시도 게시판에서 보니 사람들이 그래프 탐색으로 많이 풀었다는 사실을 알게되었다. "이 문제를 어떻게 그래프 탐색으로 풀까..?" 고민하던 찰나에 머리에 다익스트라와 비슷한 알고리즘이 스쳐지나갔다. 게시판 검색 안했다면 아마 생각 못하지 않았을까 생각한다. 정말 많은 문제를 풀어봐야 겠다고 생각했다. D..