알고리즘51 BOJ 1520 - 내리막길 https://www.acmicpc.net/problem/1520 접근그래프 탐색에서 내리막길로만 건너가는 문제이다. 이 문제의 핵심은 어떻게 모든 경로의 수를 구하냐가 관건이다.기존 BFS, DFS를 사용 시, 모든 경로를 탐색해야 하므로 500x500인 이번 문제에서 시간초과가 발생한다. 이 문제의 핵심은 Y->X와 Z->X로 갈 때, X의 경로의 수는 Y+Z 임을 이용하면 된다.이를 메모이제이션을 통해 DP[movedX][movedY]가 0인 경우(탐색되지 않은 경우)에는 계속 앞으로 전진하고,DP[movedX][movedY]가 0이 아닌 경우(이미 탐색된 경우)에는 DP[X] += DP[movedX][movedY]를 수행하면 된다. 이대로 수행하게 되면 문제가 발생한다.이미 진행된 경로에 대해서 .. 2024. 8. 16. BOJ 1477 - 휴게소 세우기 https://www.acmicpc.net/problem/1477 접근휴게소 간 거리가 최소가 되는 거리를 찾는 문제이다.최소 거리를 찾는 문제이므로 매개변수 탐색을 통해 해결할 수 있다. 무엇을 기준으로 이분적으로 구분을 하면될까?휴게소 사이 (+ 시작지점과 끝지점 포함)에 새로운 휴게소를 건설한다는 가정하에 N의 거리를 두고 새로운 휴게소가 지어진다고 가정해보자.이렇게 되면 우리는 휴게소 사이에 둘 새로운 휴게소를 두는 지점을 이분적으로 탐색하면 된다. 예제 1번을 예를 들면휴게소 사이에서 어떤 거리 D을 기준으로 새로운 휴게소가 세워진다. 만약 휴게소 사이를 D으로 나누었을 때, 새롭게 세워진 휴게소가 M개가 넘는다면D를 늘려야 하므로 left = mid+1을 하면 된다. 반대로 새롭게 세워진 휴게.. 2024. 7. 12. BOJ 17404 - RGB 거리 2 https://www.acmicpc.net/problem/17404 접근기존 RGB 거리 문제에서 첫 번째 집과 마지막 집의 색을 고려하는 조건이 추가된 문제이다.DP를 이용하여 풀게되면 마지막 집을 칠할 때, 첫번째로 어떤 집을 선택했는지 알 수 없다.따라서, 첫 번째 집을 칠할 색을 저장하고 마지막 집의 색을 고려해야 한다. 첫 번째 집을 고르는 경우를 for문을 통해 선택하고, 기존 처럼 진행하면 된다.그러나 여기서 문제되는 부분이 있다. 첫 번째 집을 Red를 선택한다고 가정해보자.dp[1][1] = arr[1][1];for (int i = 2; i 위 코드에서 dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + cost[i][1];을 하는 순간 dp[1][1] 대신.. 2024. 7. 1. [수학] 분할정복을 이용한 거듭제곱 수학적 정의를 이용하여 거듭제곱을 하는 방법이다.기존 거듭제곱의 경우, 모두 곱하기 때문에 O(N)의 시간이 걸리지만,분할정복을 이용하면 O(LogN)에 결과 도출이 가능하다. 그냥 단순하게 2, 3등분하여 한방에 구한다는 뜻이다. 재귀함수와 반복문 두 가지 방법으로 구현이 가능하다. 반복문의 경우 코드를 먼저 보자.void powFunc(int a, int b) { int res = 1; while(b) { if (b % 2 != 0) { res *= a; } a *= a; b /= 2; } cout - 2, 3 등분으로 나누기 위해 b가 1이상일 동안 이루어진다.- 만약 홀수인 경우, (위 식 그림에서) 마지막에 C가 추가적으로 곱해지기 때문에, 초기에 곱한다.- 짝수의 경우, 마지.. 2024. 5. 1. BOJ 3109 - 빵집 3109번: 빵집 (acmicpc.net) 접근방법이번 문제는 그래프 탐색을 통해 오른쪽, 오른쪽 대각 위, 오른쪽 대각 아래 이렇게 총 3가지로 이동하며 마지막 열에 도달하는 문제이다.이 과정에서 발생하는 문제는 다음과 같다. 1. 어떻게 하야 가장 많은 파이프가 지나갈 수 있도록 배치할 수 있을까?2. 도착점까지 연결하는 파이프는 하나여야 한다. 먼저 1번부터 해결해보자.예제 1번을 보자 5 5.xx....x..........x....x. 여기서 0,0 에서 출발한 파이프 라인은 최대한 위쪽을 붙어서 이동해야 한다. 5 51xx.1.1x1...1.....x....x.이런게 1의 경로를 따라 이동해야 하므로, 움직이는 순서는 -1, 0 ,1 이어야 한다. (중요) 이제 2번째 문제인 "도착점까지 연결.. 2024. 4. 30. BOJ 2531 - 회전 초밥 2531번: 회전 초밥 (acmicpc.net) 접근 방법초밥을 연속 K를 먹었을 때, 먹을 수 있는 가장 많은 가짓 수를 선택하는 문제이다.이 문제에서 주의 깊게 봐야할 것이 쿠폰이다. 처음에 쿠폰이 해당 쿠폰의 초밥을 먹을 때, 추가로 1개를 더 먹는 거라고 착각했다.그러나 이 문제에서 " 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다." 를 고려하지 않은 문제풀이이다. 따라서, 해당 쿠폰의 초밥을 안 먹은 경우 가지 수를 1가지 추가하고 슬라이딩 윈도우를 하면 된다. 코드#include #include #include #define ll long longusing namespace std;int n, d, k, c;vector v;int selec.. 2024. 4. 29. 이전 1 2 3 4 ··· 9 다음
