문제https://www.acmicpc.net/problem/3109풀이그리디 + DFS접근법처음 접근은 완전탐색 방식으로 접근했습니다.문제를 해석해보면 왼쪽 열에서 오른쪽 열까지 벽(x)을 제외한 나머지 통로들에 파이프를 설치하여 연결할 수 있는 길의 개수를 구하는 문제입니다.주어진 조건에 의한 행동은 3가지로 다음과 같습니다.오른쪽 상단 대각선오른쪽오른쪽 하단 대각선또한 겹치게 설치 할 순 없다는 조건이 있습니다.탐색해야하는 경우의 수는 그럼 총 N개로 시작 열의 격자칸 개수만큼 탐색을 해야합니다.또한 백트래킹을 통해서 완성된 길에 대해서는 기록을 하고, 끝까지 도달하지 못하는 경우에는 원상복귀를 시켜야 한다고 생각했습니다.위와같은 로직을 구현하기 위해서 처음 0,0에서 탐색을 시작하여 길이 완성될 ..

이번 글의 목적은 피보나치같은 대표적인 예시로 다이나믹 프로그래밍에 대해 뜯어보기 위함이 아닌저만의 접근(풀이)방식에 대해서 정리한 글입니다. 도움이 되셨다면 좋겠네요.도입부알고리즘 문제를 조금 풀어본 사람의 경우, 문제를 풀다보면 “DP로 풀어야하나?” 라는 감이 올 때가 있습니다.예를 들자면, 완전 탐색을 요구하는 문제인데 입력이 굉장히 클 경우, 일반적인 DFS, BFS로 풀 수가 없다고 느꼈을 때입니다. 아마 동전, 배낭문제와 같이 잘 알려진 문제들에 대해서는 곧바로 풀이를 할 수 있겠지만, 이러한 문제들은 코딩테스트에서 잘 나오지 않죠. 심지어 “DP로 풀어야하나?”라는 생각도 들지않게 나올 때도 있습니다.“DP로 풀어야겠다!”라고 생각을 해도 좀처럼 풀리지 않을텐데, 이유는 문제마다 공식이 제..

문제https://www.acmicpc.net/problem/17485 풀이다이나믹 프로그래밍 풀이접근법처음에는 다익스트라로 최소비용 구하면 되는 것 아냐? 라는 생각을 잠깐 했지만 출발지점이 1000개가 될 수 있기에 DP로 풀었다. 문제 조건해당 문제에서 각 원소의 위치에서 할 수 있는 행동은 3가지다.왼쪽 아래중간오른쪽 아래또 다른 조건으로는 이전 행동과 같은 행동을 취하지 못한다. dp로 풀이를 하기로 했으니 각 원소의 위치의 최선의 값을 어떻게 찾을지 생각하는 것 뿐이다.간단하게 생각하면 dp[i][j]는 3가지 이전해 + 현재값 중 최소값을 선택하면 될 것으로 보인다. 그러나 다음해를 구하기 위해서 이전해가 어떤 방향에서 진행된 값인지 알 필요가 있다.이를 위해 3차원 배열로 dp배열을 구성했..

문제https://www.acmicpc.net/problem/3020 풀이누적합을 활용한 풀이접근법N이 최대 200,000, H가 최대 500,000으로 들어오는 것을 조심해야 한다.단순히 O(NH)로 풀게 될 경우 시간초과가 발생하기 때문에 완전탐색 쪽으로는 생각하지 않았다. 그러면 어떻게 각 구간에 대해 효율적으로 탐색할 수 있을까? 처음에 떠올랐던 건 각 구간 별로 입력을 받을 때마다 갱신하면 되지 않을까였다.N개의 입력에서 갱신하는 방법에 대해 생각한 결과 각 구간 별로 누적합 원리를 활용해서 종유석 | 석순 각각에 대해 카운팅 해준 다음, 누적합을 구하는 방식으로 풀이했다.결과에 대해서는 i구간에 대해 종유석[i] + 석순[i]의 합이 개똥벌레가 부숴야하는 장애물의 개수이며, 최소값을 구한 후 ..