빵똥

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..

취업을 준비하기 위해 구인 광고를 보다 보니 낯설지만 많은 회사가 원하는 경험이 있었는데 바로 MSA 경험이었다. (도메인 주도 설계는 MSA를 위한 설계 방법 중 하나로 포함했다) 다른 것과는 다르게 특정 기술로 보이진 않아 궁금증이 생겨 찾아보기 시작했다. MSA를 설명하기 전 기존의 방법인 모놀리틱 아키텍처를 그림으로 간략하게 그려보자면 아래와 같다. 모든 도메인이 묶여있고 하나의 DB만을 바라보고 있어 하나의 서비스에 대해서만 배포 및 테스트를 수행하면 되고 트랜잭션 또한 DB가 하나이니 서비스의 규모가 크지 않은 경우에는 MSA보다는 더 효율적이라고 할 수 있다. 만약, 서비스 규모가 커져 다음과 같은 상황이 발생한다면? 위 그림에서의 보이는 단점을 몇 가지만 살펴보자. 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번을 그림으로 보면 말단..