알고리즘

[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..

[C++] 백준 2606번 바이러스

그래프 문제. 그래프 이론을 알고있다면 쉽게 풀 수 있는 문제였다. 문제풀이 그래프 구현을 위해 vector와 bfs구현을 위해 queue STL을 사용했다. 정점의 개수와 간선의 개수를 받는 변수를 만들었다. adj_list 벡터를 사용해서 그래프를 구현했고 visit 배열로 방문한 정점인지 체크했다. result 변수로 결과값을 출력했다. 시작점은 어차피 1부터 시작하므로 따로 매개변수로 받아서 시작하진 않았다. 그리고 1번을 큐에 넣고 방문했다고 기록하고 반복문을 큐가 비어있지 않다면 계속 반복하게 했다. 현재 방문중인 정점과 연결된 정점들 중 방문하지 않은(혹은 큐에 들어가있지 않은) 정점들은 큐에 삽입하고 방문했다는 기록을 남긴다. 그리고 결과값에 1을 더해준다. 그래프 이론은 실버 정도의 난이..

[C++] 백준 2579번 계단 오르기

다이나믹 프로그래밍 문제. 처음 이문제를 봤을 때 처음에 백트래킹으로 시도했다가 시간초과가 너무 많이났다. (생각해보면 계단 개수가 최대 300개 인데, 이를 고려하면 경우의 수가 2의 지수승이 어마어마하게 크기 때문에 잘못된 접근이다.) 사실 시간초과 부분에 관련해서 게시물을 찾다가 반복문으로 충분히 해결가능 하다는 답변을 보았고, 얼핏 스쳐가는 코드에서 max 메서드를 보았다. max 메서드는 오래동안 안 써왔어서 생각을 못했는데, max 메서드를 써서 접근하기로 했다. 따라서 이건 포기하고 다이나믹 프로그래밍의 Bottom Up 방식으로 접근하기로 했다. 다시 접근할 때 max 메서드를 오랜만에 써서 그런지 머리가 잘 안돌아갔다. max(A, B)는 A와 B중 큰 값을 return해주는 algori..

[C++] 백준 2667번 단지번호붙이기

그래프 이론 문제. 연결 요소(Connected Components)의 개수를 구하고 각 연결 요소에서의 정점의 개수를 오름차순으로 정렬해서 출력하는 문제. 연결 요소의 개수는 DFS, BFS로 구할 수 있다. 나는 DFS를 이용해서 해당 문제를 풀었다. 문제풀이 먼저 입력받는 정수 n, 그리고 지도를 나타내는 2차원 배열 map(1~25의 idx를 사용하기 위해 26의 크기로 만들었다.) 각 연결요소마다 집이 몇 개가 있는지 세기 위해 house_count라는 정수형 변수를 만들었다. 그리고 해당 정점이 이전에 방문했는지 체크하기 위한 bool형 2차원 배열 visit을 만들었다. house_vec 벡터형 변수로 각 연결요소에서 정점의 개수들을 입력해서 저장했다. DFS 메서드이다. 사실 이 부분에서 ..

[C++] 백준 11399번 ATM

그리디 알고리즘 문제. 그리디 알고리즘이란? 각 단계에서 최선일 것 같은 방법을 선택하는 알고리즘. 어떤 값을 최대화, 최소화하는 문제의 해를 찾는 문제이다. 큰 수 혹은 작은 수부터 각 단계에서 최대한 사용하는 것이다. 매 순간 최선인 방법을 선택하는 알고리즘이지만, 그게 전체적으로 봤을 때 항상 최적의 방법은 아닐 수 있다 ! 처음 접근 방식 이 문제를 처음 봤을 때는, Pi 이런식으로 설명해서 점화식을 유도하는 문제라고 생각했다. 그래서 DP로 풀려고 했는데 특별하게 보여지는 규칙은 없었고 그냥 최종적으로 총 걸리는 시간을 더할 때 Bottom Up 방식과 비슷하게 더하는 것 뿐이였다. 문제에 두번째 예시를 보면 결국 시간이 적게 걸리는 사람부터 정렬했을 때 최소 시간의 합이 된다. 중간에 다른 조..

[C++] 백준 1003번 피보나치 함수

시간 제한과 문제를 보더라도 쉽게 알 수 있는 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍의 Bottom Up 방식으로 문제를 접근했다. F[0] = 1 0 F[1] = 0 1 F[2] = 1 1 F[3] = 1 2 . . . 즉, An = A(n-1) + A(n-2)임을 알 수 있다. 먼저 테스트 케이스 변수, 입력받는 정수 n이 있다. 그리고 pair 자료형의 배열을 사용해서 각 수마다 0이 나오는 횟수와 1이 나오는 횟수를 저장했다. pair 자료형은 {A, B}의 형태로 입력할 수 있다. make_pair(A, B)의 형태로도 입력할 수 있다. 첫번째는 first, 두번째는 second의 형태로 접근한다. 0과 1은 알 수 있으므로 미리 배열에 입력해 놓는다. 각 테스트 케이스마다 n을 입력..

[C++] 백준 9095번 1, 2, 3 더하기

처음 이 문제를 봤을 때 n이 작아서 백트래킹으로 문제를 풀려고 시도했다. 시간제한이 1초이므로 1억번의 연산이 가능한데 이 문제는 n이 아무리 커도 1억번을 넘지 않을거라 생각했다. 문제풀이 테스트 케이스를 입력받고 정수 n을 입력받으며 backTracking 메서드를 구현했다. 그리고 매 케이스마다 1, 2, 3 합의 개수를 나타내는 output 변수도 만들었다. 메인 함수에서는 간단하다. 매 케이스마다 결과값 output 변수를 0으로 초기화하고 backTracking 메서드를 1, 2, 3부터 시작한다. 이렇게 풀면 쉽게 맞출 수 있다. 그런데 이 문제는 백트래킹이 아닌 다이나믹 프로그래밍 문제였다. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍, 동적 계획법은 큰 문제를 작은 문제로 쪼개어서 푸는..