⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net ⭐️ Idea flow 문제의 요지는 칭찬을 받는 노드의 모든 부하 노드(자식 노드)들에게 칭찬정도를 더하는 것이다. 맨 처음에 생각했던 방법은 input을 통해서 단방향 간선을 연결시키고, 칭찬을 받는 노드와 칭찬 정도를 받을 때 마다 DFS를 실행하여 값들을 구하는 방식이었다. 하지만 당연하게도 이 방법으로 풀었더니 시간 초과가 났다. DFS를 m번(최대 ..
Coding test/Baekjoon
⭐️ 난이도 Gold 2 ⭐️ 문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net ⭐️ Idea flow 문제를 해결하려면 우선 각 노드가 격자에서 몇 번째 행, 몇 번째 열인지 알아야 한다. 문제를 읽어보면 먼저 "같은 레벨(level)에 있는 노드는 같은 행에 위치한다"라는 말이 있다. 따라서 행을 구하는 것은 별 문제가 없다. (level이 곧 행이 되기 때문에) 문제는 몇 번째 열인지 구하는 것인데, 문제에서 주어진 ..
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net ⭐️ Idea flow 문제를 요약하자면 다음과 같다. 1. 간선의 정보인 노드의 번호 두 개가 m번 주어진다. 2. 게임을 진행하다가(간선을 추가하다가) 3. 싸이클이 완성되면 몇 번째 차례에서 완성이 되었는지 return 다른 그래프 문제들과는 다르게 간선을 미리 연결시켜놓고 문제를 푸는 것이 아니라, 간선을 연결시키면서 사이클이 완성되었는지의 여부를 ..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ⭐️ Idea flow N개의 강의에 대해서 각각의 시작 시간과 끝나는 시간이 주어졌을 때, 강의실을 얼마나 적게 사용할 수 있는지 구해야 하는 문제이다. 문제 지문에서 "Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다"고 주어져있다. 이 말은, i번째 강의의 시작시간 Si가 k번째 강의의 끝나는 시간 Tk보다 크거나 같다면, 해당 강의실에서 강의를 이어서 진행할 수 있다는 뜻이다. 강의실을 ..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ⭐️ Idea flow 이 문제를 읽었을 때 어떻게 풀어야 할 지 감이 오지 않아서 주어진 예제를 직접 풀어보면서 규칙을 찾아보려고 했다. 처음에는 제일 작은 수 k개를 찾아서 지우면 되는 줄 알았다. 하지만 무작정 작은 수들만 골라서 지우게 되면 제일 작은 수들을 지우고 난 후, 작은 수가 큰 수 왼쪽(앞)에 있을 수 있다. 예를 들어 k=4 num=4177252841일 때, 제일 작은 수들만 골라서 지우면 477584가 나온다. 이 예..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net ⭐️ Idea flow 그리디(Greedy) 알고리즘을 사용해서 풀어야하는 문제였다. 전체적인 알고리즘은 다음과 같다. 1. 시작하는 시간을 기준으로 강의 정보(lecture)를 정렬한다. 2. 처음 시작하는 강의(lecture[0])의 끝나는 시간을 우선순위 큐에 push한다. 여기서 우선순위 큐는 작은 수의 우선순위를 더 높게 잡는다. 3. 인덱스 1부터 시작하는 반복문을 실행한다. 3-1. i번째 강의의..
