전체 글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. [백준/12100/C] 2048(Easy) 크게 3개의 파트로 나누어서 생각해보아야한다.1. 좌/우/상/하의 이동을 어떻게 구현할 것인지?2. 탐색알고리즘을 어떻게 전개할것인가?3. 최댓값을 판단하는 알고리즘은? 2,3은 문제의 태그를 보면 알 수 있다싶이 브루트포스로 해결할 수 있다.처음에 시간복잡도가 브루트포스를 커버해줄 수 있는지 의문을 가졌지만 GPT님이 계산해주셔서 그냥 그런갑다 납득했다.. 1.에 대한 해결로는 좌/우로 이동할 때는 temp배열에 변동된 각 행을, 상/하로 이동할 때는 temp배열에 변동된 각 열을 저장해줄 것이다. 좌측으로 미는것을 구현해보자면 이러하다 : board[i][j]가 0이 아닐때 temp에 받을 것인데,a) 만약에 temp[idx]가 0이면 그냥 입력받고(게임을 생각해보자, 아무것도 없는 부분은 그냥 스.. 2025. 6. 28. [백준/1005/C] ACM Craft 필독 : https://eigenarea.tistory.com/66 [백준/2252/C] 줄 세우기위상정렬의 가장 standard한 문제가 뭔지 묻는다면 난 이 문제를 꼽는다.이 문제는 위상정렬 그자체이며 위상정렬을 입문한다면 가장 먼저 풀어봄직한 문제이기도 하다. 위상정렬의 이론에 대한eigenarea.tistory.com 이 문제는 위상정렬의 아이디어에서 조금만 더 생각해보면 구현해낼 수 있다.각 노드를 만드는 시간을 graph[i].time에다가 저장했다고 생각해보자.요점은, 결국 pop해줬을 때의 노드(prev)의 다음 노드(cur)까지 도착하는 시간을 찾으면 되는데 결국 그 시간은 기존의 시간 res[cur->idx]와 pop해준 원소까지의 시간과 그 다음노드를 만드는데 걸린 시간을 합한 res.. 2025. 6. 27. [백준/2252/C] 줄 세우기 위상정렬의 가장 standard한 문제가 뭔지 묻는다면 난 이 문제를 꼽는다.이 문제는 위상정렬 그자체이며 위상정렬을 입문한다면 가장 먼저 풀어봄직한 문제이기도 하다. 위상정렬의 이론에 대한 좋은 설명(필독):https://m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 ...blog.naver.com이 블로그의 내용에 첨언하자면, 위상정렬은 말그대로 그래프의 위상(topology)를 보존해서 정렬로 보내주는게 아니다.그러나 그래프의 일부 정보가 훼손되더라도, 순서관계만은 보존이 된다는 점이 이 알고리즘의 요지이다.그래서 내가 보기에는 위상.. 2025. 6. 27. 이전 1 2 3 4 ··· 8 다음 반응형