❓문제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인 다섯 개의..

❓문제https://www.acmicpc.net/problem/1202성능 요약메모리: 107448 KB, 시간: 1752 ms분류자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬 문제 설명세계적인 도둑 상덕이는 보석점을 털기로 결심했다.상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.✍🏻풀이처음에는 각 보석을 최대힙으로 리스트에 넣고, 가방을 무거운 순으로 정렬하였다. 그러나 이런 경우 보석이 무게대로 정렬되어있는 것이 아니기에 큰 가방에 이미 보석이 들어..

❓문제https://www.acmicpc.net/problem/1655성능 요약메모리: 39016 KB, 시간: 228 ms분류자료 구조, 우선순위 큐 문제 설명백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.✍🏻풀이정말 간단하게 보면 반복문..

❓문제https://www.acmicpc.net/problem/1715성능 요약메모리: 36292 KB, 시간: 156 ms분류자료 구조, 그리디 알고리즘, 우선순위 큐문제 설명정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 2..