빵똥

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/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 접근 최초 접근 방법을 생각해내기까지 시간이 오래 걸렸지만 알아낸 이후부터는 비교적 쉽게 풀어낸 문제다! 저번 오리 문제와 마찬가지로 루트에서부터 내려가는 것이 아닌 공통 조상을 찾아야 하는 두 노드로부터 시작해보자! 예제 속 두 개의 케이스 중 첫 번째 케이스를 그림으로 보면 다음과 같다. 이 때, 순서에 상관은 없지만 7이 먼저 루트를 ..

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/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 1. 접근 DFS로 접근 시 인접 리스트를 사용하니 O(V + E) == O(500,000 + 499,999) = 1,000,000로 시간 초과 없이 풀 수 있다! 게임의 규칙을 살펴보면 각 말단 노드의 개수 = 말의 수이며 한 턴에 한 번씩 현재 노드의 부모 노드로 이동한다. 또한 게임에서 이기려면 순서가 먼저인 성원이 차례에 마지막 말을 루트로 이동시켜야 한다. 예제 3번을 그림으로 보면 말단..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1. 접근 문제를 풀기 전 시간 복잡도를 구하자! V + E를 T만큼 반복하는데 T는 제시되어 있지 않다! n과 m이 그리 크지 않으니 T도 상식적인 선 안에서 제시되니 일반적인 DFS로 접근해보자! 문제의 조건을 살펴보면 트리의 조건을 제시해주고 해당 조건을 만족하는 개수를 이 형식에 맞춰서 출력해주면 된다. 조건에서 제시된 트리의 기준은 정점이 n이라고 가정했을 때 간선이 n..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 1. 접근 최대 입력값에 따른 시간 복잡도는 다음과 같다. 칸의 갯수 = H * N * M = 1,000,000로 시간제한안에 여유있게 풀 수있다! 문제의 조건을 살펴보자 익은 토마토 기준으로 상,하,위,아래,좌,우 총 여섯 방향으로 토마토는 익어가며 토마토가 비어있는 칸도 있다. 첫 번째 입력 예제를 그림으로 보면 토마토가 잘 익어가다가 비어있는 칸으로 인해 모두 익지 못..

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 1. 접근 배열의 최대 크기는 50으로 50 * 50칸을 두 번만 방문하면 되니 약 2,500번만에 풀 수 있는 문제다! 문제의 조건을 살펴보자면 땅은 . * X D S로 총 다섯개로 나눌 수 있으며 물과 고슴도치는 매번 위, 오른쪽, 아래, 왼쪽 총 네 방향으로 이동이 가능하며 물은 벽과 비버굴을 통과할 수 없고 비버는 벽과 물 웅덩이를 통과할 수 없다. 다음과 같은 배치가 있다고 가정했을 때 최단 거리는 ..