빵똥

https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 1. 접근 주어진 그래프를 위상 정렬을 하되 문제 속 조건인 Strahler의 순서를 구하는 조건을 참고하여 푸는 문제입니다. 입력의 간선 정보로 각 노드의 진입 차수를 저장하고 방문시마다 감소시키며 순서를 카운트하고 가장 큰 순서를 출력하면 되는데 기본 위상 정렬에서 조건을 조~~ 금 추가했다고 바로 오랫동안 삽질했습니다... 기본적으로 위상 정렬을 수행하는 코드에 스트롤러 순서를 정하는 부..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1. 접근 문제 속 입력을 그래프로 만들어 위상 정렬하는 문제입니다. 처음에는 input으로 어떻게 그래프를 만들어야 하나 고민이 많았던 문젠데 예제 입력을 그림으로 그려보니 바로 이해가 되서 풀었던 문제입니다. 예제 입력의 두 번째 줄부터 간선 정보라 생각하고 그래프로 그려보면 다음과 같습니다. 입력 받은대로 단방향 그래프를 그리고 자신에게 향하는 간선이 없는 노드를 차례대로..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 접근 문제 속 요구사항은 일부 학생들의 키 비교 입력을 기준으로 전체 학생들을 줄 세우면 되는 문제입니다. 하단 알고리즘 분류를 보시면 알겠지만 그래프를 활용한 문제인데 직접적으로 그래프라고 알려주진 않습니다. 또한, 위 문제는 위상 정렬을 활용한 문제로 해당 알고리즘을 모르신다면 간단하게 보고 오시는 걸 추천드립니다! 앞서 그래프를 활용해야 한다고..

https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 1. 접근 먼저 문제를 살펴보겠습니다. 문제 속 지문을 살펴보면 요구사항은 두 가지로 보입니다. 특정 직원을 칭찬하면 칭찬받은 직원의 부하 직원들도 같이 칭찬받는다. 칭찬에는 수치가 있으며 모든 칭찬이 끝나면 모든 직원들에 대해 누적 칭찬 치를 출력한다. 예제 입력을 예시로 각 직원을 노드로, 상하 관계를 부모 자식 관계로 나타낸 트리로 보면 다음과 같습니다. 그림을 보며 위 요구사항을 다시 정..

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 1. 접근 특이하게 힌트가 주어진 문제다. 트리의 정의에 대해 잘 모르시는 분은 힌트의 앞부분부터 읽고 이해한 후 문제에 접근하는 게 맞고 그게 아니라면 5번을 정점으로 트리 그림부터 보면 이해가 편하다. 문제는 간결하고 힌트는 이론부터 설명하기에 복잡해질 수 있는데 간단히 생각하기 위해 예제 입력을 하나하나 그림으로 뜯어보자. 첫째 ..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 접근 일반적인 트리에서는 노드 제거 시 규칙(?)에 따라 자식 노드가 그 자리를 대체하는 방식이지만 문제에선 제거된 노드는 빈 채로 두어 가지 않는다. 즉, 입력 단계에서 루트가 -1로 주어지는 것만 염두에 두고 평소처럼 자식 노드들을 인접 리스트를 생성하되 마지막 입력인 지울 노드만 별도로 받았다가 탐색 전 경로를 끊어버리면 된다. 예제 입력 2번을 그림으로 보자 (1번 노드를 지울 ..

https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 1. 접근 간선 정보를 어떻게 받을까 고민을 많이 했던 문제다... 사이클 되는 그래프의 경우는 일반적인 간선 입력처럼 받으면 되지만 트리 문제의 경우는 그냥 냅다 특정 노드의 부모는 누구인가? 를 저장하여 찾아가는 게 제일 간단한 것 같다. 입력에서 각 노드의 부모만 잘 입력받았다면 이제 찾아야 할 것은 딱 하나다. 예제 입력 1번을 예시로 위 조건을 그림으로 표현하면 다..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 1. 접근 가장 기본적인 탐색이 각 노드마다의 거리를 누적하여 x ~ y까지 몇 번 이동해야 하는가? 를 물었다면 이번엔 각 간선마다 비용이 있어 그 비용을 누적하면 되는 문제다! DFS를 활용하여 각 정점까지의 거리를 누적하는 방법과 다익스트라 알고리즘을 활용하는 두 가지의 방법이 있는데 둘 다 구현해보도록 하자! 그림으로 살펴보자! 2번 정점에서 출발할 때의 예시이다. 그림 속 표를 글로 쓰면 2번 정점에서 1번 정점까지의 비용 = 2 2..

https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N 오리가 원하는 땅으로 접근을 했으나 강사님의 스켈레톤 코드에서 오리의 땅 -> 루트로 가는 방법이 더 간단히 찾을 수 있다는것에 힌트를 얻어 접근해 보았다. 그래프를 생성하지 않고 각 오리의 원하는 땅에서부터 시작해 루트까지 가려면 현재 노드의 부모를 찾아가는 방법을 찾아야 했는데 힌트는 문제에 있었다! 문제의 예제 트리를 이진법으로 변환하여 접근한다면 현재 노드에서 오른쪽으로 한 칸 시프트 하면 부모의 노드가 된다. 100(4) -> 10(2) -> 1 101(5) -> 10(2) -> 1 110(6) -> 1..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 접근 트리의 개념을 코드로 구현해내는 가장 기본적인 문제가 아닐까 싶다. 자료구조 2번에 트리에 대해서 간단히 정리해두었으니 모르는 분은 한 번 보고 오셔도 될 것 같다! https://dhbang.tistory.com/14?category=905670 자료구조 - 2 트리 1. 트리의 개념 트리는 데이터 간의 관계를 나타내는 비선형 자료구조로 특정 조직의 조직도를 대표적인 예로 ..