⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net ⭐️ Idea flow 올바른 괄호 쌍을 지워야 한다는 부분에서 이전에 스택을 이용해서 풀었던 문제가 생각났다. 하지만 괄호의 제거함으로써 얻을 수 있는 모든 수식을 얻어야 하고, 이는 괄호 쌍의 모든 조합을 찾아야 한다는 뜻이다. 모든 조합을 찾기 위해서는 백트래킹(DFS)가 적절하기 때문에 이를 활용하기 위해서는 괄호쌍에 대한..
C++
⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net ⭐️ Idea flow 문제의 요지는 칭찬을 받는 노드의 모든 부하 노드(자식 노드)들에게 칭찬정도를 더하는 것이다. 맨 처음에 생각했던 방법은 input을 통해서 단방향 간선을 연결시키고, 칭찬을 받는 노드와 칭찬 정도를 받을 때 마다 DFS를 실행하여 값들을 구하는 방식이었다. 하지만 당연하게도 이 방법으로 풀었더니 시간 초과가 났다. DFS를 m번(최대 ..
⭐️ 난이도 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 ..
