❓문제https://www.acmicpc.net/problem/1068성능 요약메모리: 34936 KB, 시간: 64 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리문제 설명트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다.트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다.예를 들어, 다음과 같은 트리가 있다고 하자.현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다.이제 리프 노드의 개수는 1개이다.✍🏻풀이인접 리스트나 사전형을 활용하여 각 노드 별 ..

❓문제https://www.acmicpc.net/problem/1966성능 요약메모리: 34924 KB, 시간: 68 ms메모리: 32412 KB, 시간: 52 ms메모리: 32412 KB, 시간: 48 ms분류자료 구조, 구현, 큐, 시뮬레이션 문제 설명여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인..

❓문제https://www.acmicpc.net/problem/2800성능 요약 메모리: 32412 KB, 시간: 36 ms분류비트마스킹, 브루트포스 알고리즘, 자료 구조, 스택, 문자열 문제 설명어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2,..

❓문제https://www.acmicpc.net/problem/14940성능 요약메모리: 41932 KB, 시간: 488 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색문제 설명지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.✍🏻풀이이 문제는 BFS이다. 문제에서 2는 목표지점이다. 그리고 우리가 구해야 하는 것은 각 갈 수 있는 땅 위에서 목표지점까지의 거리를 구하는 것이다. 그러므로 출발지를 목표지점으로 두면 된다.목표지점이 정확히 (0, 0)에서 주어진다는 보장이 없으므로 우리는 목표지점을 찾아야 한다. 그리고 목표지점을 찾아 각 거리를 계산하면 된다. 이 때, 방문한 곳인지를 표시하는 동시에 거리를 계산하..

❓문제https://www.acmicpc.net/problem/17298성능 요약메모리: 205056 KB, 시간: 1140 ms분류자료 구조, 스택 문제 설명크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.✍🏻풀이오른쪽..

❓문제https://www.acmicpc.net/problem/2493성능 요약메모리: 115756 KB, 시간: 560 ms분류자료 구조, 스택 문제 설명KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의..