⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net ⭐️ Idea flow 문제의 요지는 칭찬을 받는 노드의 모든 부하 노드(자식 노드)들에게 칭찬정도를 더하는 것이다. 맨 처음에 생각했던 방법은 input을 통해서 단방향 간선을 연결시키고, 칭찬을 받는 노드와 칭찬 정도를 받을 때 마다 DFS를 실행하여 값들을 구하는 방식이었다. 하지만 당연하게도 이 방법으로 풀었더니 시간 초과가 났다. DFS를 m번(최대 ..
Coding test
⭐️ 난이도 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보다 크거나 같다면, 해당 강의실에서 강의를 이어서 진행할 수 있다는 뜻이다. 강의실을 ..
⭐️ 난이도 Easy ⭐️ 문제 https://leetcode.com/problems/merge-two-binary-trees/ Merge Two Binary Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com You are given two binary trees root1 and root2. 이진 트리 root1과 root2가 주어진다. Imagine that when you put one of them to cover the other, some ..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ⭐️ Idea flow 이 문제를 읽었을 때 어떻게 풀어야 할 지 감이 오지 않아서 주어진 예제를 직접 풀어보면서 규칙을 찾아보려고 했다. 처음에는 제일 작은 수 k개를 찾아서 지우면 되는 줄 알았다. 하지만 무작정 작은 수들만 골라서 지우게 되면 제일 작은 수들을 지우고 난 후, 작은 수가 큰 수 왼쪽(앞)에 있을 수 있다. 예를 들어 k=4 num=4177252841일 때, 제일 작은 수들만 골라서 지우면 477584가 나온다. 이 예..
