https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 둘째 줄부터 입력되는 땅 높이의 좌표는 중요하지 않고 각각의 땅의 높이의 개수가 중요하다. 그렇기 때문에 땅의 높이들을 따로 저장하지 않고, 바로 dict에 (key = 땅의 높이, value = 개수) 저장해준다. 땅의 높이의 범위는 0~256로 작은 범위라서 전체를 탐색해도 되지만, 시간을 줄이기 위해서 범위를 제한해주었다. 생각을 해보면 고르게 되는 땅의 높이는 입력된 땅의 높이 범위..
[BOJ] 12865 : 평범한 배낭
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 이 문제는 0/1 knapsack 문제로, DP (Dynamic Programming)을 이용하는 대표적인 문제이다. DP는 쉽게 말하자면 구하기 힘든 큰 범위의 문제를 여러 개의 작은 범위로 나누어서 구하는 것이다. 문제를 풀면서 구해야하는 값들을 미리 구해놓은 값으로 가져다 쓰기 때문에 메모리의 낭비를 줄일 수 있다. 배낭..
https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 문제를 잘 읽어보면 Priority Queue를 이용해서 문제를 풀이하면 된다. 하지만 나는 문제를 보고 Circular Queue가 생각이 났다. 배열에 나머지 연산을 이용하여 Circular Queue를 구현하고 최댓값을 갱신하여 문제를 풀었다. Queue는 FIFO (First In First Out) 방식으로 먼저 온 데이터가 먼저 나가게 된다. 문제에서 우선순위가 밀리는 수가 나오면 다..