dfs 검색 결과

해당 글 5건
bfs나 dfs에서 component를 왜 구하는지 알아보고 응용해 봅시다.

오랫만입니다. 가희와 함께 하는 3회 코딩 테스트 때문에 작년 연말부터 글이 꽤 뜸하게 올라왔습니다. 이것이 어제 끝났으니, 문제들을 하나 하나씩 리뷰해 보도록 하겠습니다. bfs나 dfs를 배우다 보면, 방향성이 없는 (다시 말해서, 양방향 간선만 있는) 그래프에서Component 라는 것이 나오게 됩니다. 이 문제가 대표적인 예입니다. 이것을 bfs나 dfs로 찾을 수 있다고 하는데요. 이것을 왜 찾을까, 찾아서 어디에 써 먹을 건지. 이 두 가지 의문에서 나온 것이 제가 출제한 가희와 베개 문제입니다. 아래 그림을 보면 Component는 2개가 있어요. 여기에 있는 간선들은 양방향으로 연결된 친구들입니다. 1번에서 bfs를 돌려 봅시다. 1번을 큐에 넣어볼까요? 그러면 큐에는 1만 들어가 있을 거..
자료알고/알고리즘 2022. 1. 24. 16:10
bounding box를 이용해서 가희와 거북이 인형을 풀어봅시다.

가희와 거북이 인형은 그리 어렵지 않아 보이는 bfs, dfs입니다. 그런데, 거북이 컴포넌트가 최대 10^6-1개까지 올 수 있어서, 자칫하다가는 시간초과가 날 수 있습니다. 그래서, 1달 전에 여행가면서 예약했던 글에는 상대 속도의 개념을 이용하자는 내용이 있었습니다. [관련글] 상대 속도를 응용한 문제들을 풀어 봅시다. 그런데, 제가 설명을 누락한 부분이 있는데, 바로 bounding box 부분입니다. 예제를 가지고 설명해 보겠습니다. 우리는 거북이의 맨 위에, 맨 위에 있다면 가장 좌측에 있는 이 부분을 기준 좌표로 가지고 돌렸습니다. 거북이 컴포넌트들이 처음에 이 위치에 있다고 해 보겠습니다. 이 상태에서 오른쪽으로 거북이가 이동할 수 있을까요? 아닙니다. 이동하면, 컴포넌트 하나가 맵 바깥을..
구현 2021. 8. 31. 04:58
여러 트릭에 응용되는 트리에서의 dfs ordering을 알아봅시다.

ps를 하시다 보면, 이런 말은 한 번쯤 들어보셨을 겁니다. 트리를 일렬로 펴기, 트리를 구간으로 바꿔서 풀기. 자동차 공장 트릭. 이들의 기반이 되는 것은 dfs ordering입니다. 그리고 이를 응용해서, HLD, LCA와 같은 것에도 쓸 수 있습니다. 이 글에서는 HLD, LCA는 다루지 않을 겁니다. 대신에, 트리를 구간으로 바꾸기 위해서 사용하는 전처리에 대해서 알아보도록 하겠습니다. 먼저, 예시로 쓰이는 트리는 아래와 같습니다. 여기서, 이런 쿼리들이 들어온다고 생각해 보겠습니다. 3을 root로 하는 서브 트리에 속한 노드들에 +3을 더한다. 혹은 xor 3을 한다. 이런 것들이 들어올 수 있어요. 트리를 구간으로 어떻게 펴는 것이 가능할까요? 해당 쿼리에서 중요한 것은 부모와 거기에 딸려..
자료알고/알고리즘 2021. 3. 7. 20:31
백준 최소 환승 경로 : 허브와 노드를 생각하자.

백준에는 5214번 환승 문제와, 2021번 최소 환승 알고리즘을 구하는 문제가 있습니다. 이 두 문제 중에서 후자를 풀어보겠습니다. 역의 갯수 n과 노선 갯수 L은 둘 다 10만 이하라는 조건은 꽤 무시무시하게 다가옵니다. 각 노선 길이의 합은 100만을 넘지 않는다는 조건을 잘 이용해 봐야 할 듯 싶네요. 여기서 핵심은 '환승을 한다'는 것을 어떻게 그래프로 표현을 할 것인지입니다. 학교 과제에서도 왕왕 나오는 편이니, 이야기를 해 보도록 하겠습니다. 노선 1과 노선 2가 만나는 환승 역 j를 생각해 봅시다. 그래프는 요렇게 그려질 수 있습니다. 여기서 핵심은, j번 역을 통해서 노란색에서 파란색으로, 혹은 파란색에서 노란색 노선으로 건너갈 수 있다는 것입니다. 3개 노선이 만나는 j역이면 어떨까요?..
자료알고/알고리즘 2021. 2. 7. 01:48
dfs 심화편 : 깊이 우선 탐색의 단점을 어떻게 보완하는가?

dfs, 그러니까 깊이 우선 탐색의 단점은 크게 2가지입니다. 해가 없는 경로에 깊이 빠진다. 그렇기에 유한 시간 내에 끝나지 않을 수도 있다. 그리고, 해를 구했을 때, 그것이 최적이 아닐 수도 있다. 이 2가지 때문에, 보통 최단 거리를 구할 때에는 사용하지 않아요. 그런데, 이걸 잘 보완하면 절찬리에 써먹을 수도 있어요. 절찬리에 잘 써먹을 수 있는 문제 중에 하나를 예로 들어봅시다. 어떠한 세제곱 수를 k개 더해서 n을 만들어야 합니다. k값은 최소가 되어야 합니다. 예를 들어서, 43은 3^3 + 2^3 + 2^3으로 만들 수 있습니다. 물론 1^3을 43개 써서 만들 수도 있지만, 43개보다 작게 만들 수 있는 방법이 존재하기 때문에, 답이 될 수 없습니다. 이 문제는 어떻게 풀어야 할까요? ..
자료알고/알고리즘 2019. 6. 28. 01:14