백준

❓문제https://www.acmicpc.net/problem/1158성능 요약메모리: 35052 KB, 시간: 2588 ms분류자료 구조, 구현, 큐 문제 설명요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다.N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.✍🏻풀이이 문제는 큐를 잘 알면 빠르게 풀리는 문제이다. 먼..

❓문제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이다.✍🏻풀이오른쪽..