분류 전체보기54 [백준/1113/C] 수영장 만들기 첫번째 시도 : DFS를 통해서 사방에 대해 0이면 넘쳤다는 신호와 함께 돌아오고 아니면 재귀를 진행해서 채워진 부분의 높이를 1더하는 방식으로 구현 문제점은 각 위치에 대해서 한번씩밖에 실행했기 때문에 최대값을 구할 수 없음.#include int pool[52][52], N, M, cnt, isahure, tmpcnt;void copy(int src[52][52], int dst[52][52]) { for (int i = 0; i pool[x][y+1] ){ jitkou(x,y+1); if (isahure) return; } if (pool[x][y] > pool[x][y-1]){ jitkou(x,y-1); if (isahure) .. 2025. 7. 1. [백준/2263/C] 트리의 순회 이 문제에 착안해야할 점은, 중위순회를 돈다면, L-------- M R------- (L은 M기준 왼쪽 트리, R은 M기준 오른쪽 트리)의 배열이 될 것이고,후위순회를 돈다면 L-------- R------ M이 될 것이다. 각 순회의 결과로 얻을 수 있는 부분은, 후위 순회는 지금 당장의 M이 무엇인지를 알아낼 수 있고, 중위 순회는 M의 위치를 탐색해서 L과 R트리의 크기를 알아낼 수 있다는 점이다. 그렇게 알아낸 결과로 왼쪽트리와 오른쪽트리에 대해서 재귀를 해주면 해결. #include int in[100000], post[100000]; int size;int search(int k, int left, int right) { for (int i = left; i 0) pref.. 2025. 6. 29. [백준/11049/C] 행렬 곱셈 순서 이 문제에 대해서 착안해야할 지점은 이것이다.dp를 어떻게 구현해야할 것인가? 생각보다 단순한데, dp[i][j]를 i번째 행렬에서 시작해서 j번째 행렬까지의 행렬곱의 계산횟수의 최솟값으로 생각해볼때, dp[i][j]의 값을 모든 i와 j사이의 k에 대해서 dp[i][k] + dp[k][j] + size[i]*size[k]*size[j]의 최솟값으로 잡아주면 된다.이는 매우 단순한 발상인데, 미리 곱한 결과값인 dp[i][k] dp[k][j]의 결과물은 (size[i]*size[k]), (size[k]*size[j]) 행렬일 것이기 때문이다. 이걸 행렬곱의 길이 (len)을 2부터 N까지 키워주면 dp[0][N]을 얻어낼 수 있다.#include #define INF 2147483647int N;int.. 2025. 6. 28. [백준/12094/C] 2048(Hard) 필독 : https://eigenarea.tistory.com/68 [백준/12100/C] 2048(Easy)크게 3개의 파트로 나누어서 생각해보아야한다.1. 좌/우/상/하의 이동을 어떻게 구현할 것인지?2. 탐색알고리즘을 어떻게 전개할것인가?3. 최댓값을 판단하는 알고리즘은? 2,3은 문제의 태그를 보eigenarea.tistory.com Easy문제와의 차이점은 실행횟수가 10번으로 늘어 브루트포스만으로는 해결해야할 분기가 기하급수적으로 늘어버렸다는 것이다.(대충 Easy문제의 1024배정도..?) 그래서 우리는 이러한 점에 착안해보아야한다.1. 움직여서 이동하지 않는 분기는 pruning(가지치기)해준다.2. 아무리 증가해도 max가 될 수 없는 분기도 pruning해준다. 1번은 단순하다. 그냥 .. 2025. 6. 28. 이전 1 2 3 4 ··· 14 다음 반응형