CodeDrive

문제:

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력:

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

풀이방법:

 한 문제에 K번째 수열을 구하는 문제와 주어진 수열이 몇 번째인지 구하는 문제가 합쳐져 있다. 두 소문제는 주어진 수 중 맨 앞의 숫자로 구별되며, 이를 command(c)로 구분해 각 소문제를 풀도록 한다.

 첫 번째 소문제는 K번째 수열을 구하는 문제다. 앞의 자릿수부터 계산하며, 주어진 수 K로부터 만들 수 있는 경우의 수를 빼주며 한자리씩 정해나간다. 즉, 예제의 경우 3번째 수열을 구하는 문제에서 맨 앞자리를 a인 경우의 수는 3!개이다. 따라서 3번째 수열은 0~3!번째 수열에 속할 것이므로, 맨 앞자리는 1인 것을 알 수 있다. 이러한 방법을 계속하여 k번째 수열을 찾는다.

 두 번째 소문제는 첫 번째 소문제의 역으로 구할 수 있다. 팩토리얼을 사용해 k번째 수열을 구했던 것의 역으로 팩토리얼을 더하면서 k를 찾도록 한다.

문제링크:

https://www.acmicpc.net/problem/1722

문제:

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력:

첫째 줄에 AN을 출력한다.

풀이방법:

 문제에서 명확하게 점화식이 주어졌기 때문에 다이나믹 프로그래밍을 사용하도록 한다. 하지만 주어진 조건의 N, P, Q이 매우 크기 때문에 list를 사용해서 구현을 한다면 메모리가 터지는 문제점이 있다. 따라서 최대한 쓰지 않는(비어있는) 값들을 줄이기 위해서 dict 자료형에다가 값들을 mapping 하도록 한다. 빠른 구현을 위해서 defaultdict을 사용해 초기화하는 과정을 간단하게 구현할 수 있도록 했다.

문제링크:

https://www.acmicpc.net/problem/1351

문제:

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력:

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

풀이방법:

 우선순위 큐(heapq)를 사용해서 가방에 최대한 비싼 보석을 그리디하게 넣는다 생각하면 된다. 따라서 보석의 정보들을 무게가 가벼운 순으로 heapq를 통해서 정렬하고, 가방도 오름차순으로 정렬을 한다.

 정렬을 마친 뒤에 가벼운 가방으로부터 시작하여 해당 가방에 넣을 수 있는 보석들을 최대힙으로 다시 구현을 한 뒤에 그 최대힙에서 가장 큰 값을 뽑아 answer에 더해준다. 이와 같은 과정들을 모든 가방에 대해 수행을 하며, 최대힙과 최소힙은 계속해서 누적해서 사용하도록 한다.

문제링크:

https://www.acmicpc.net/problem/1202

ChainMap

collection 모듈에 있는 ChainMap은 공식문서에 따르면 여러 딕셔너리나 다른 매핑을 묶어 갱신 가능한 단일 뷰를 만든다고 한다.

즉, ChainMap은 여러 딕셔너리를 하나의 링크드 형태로 묶으며, 기존에는 여러 dict들을 for를 통해 탐색했던 것을 한 번에 수행할 수 있다고 생각하면 된다.

chainMap에는 다음과 같은 method들이 있다.

1. maps
2. new_child
3. parents

new_child

parents

namedtuple

namedtuple은 지정해준 이름으로 간단한 서브 클래스를 반환한다. 이 서브 클래스는 인덱싱되고 iterable일 뿐만 아니라 attribute 조회로 접근 할 수 있다.

Counter

Counter는 hash 가능한 객체를 세기 위한 dict 서브 클래스다. 요소는 dict의 키로 저장되고 개수는 value로 저장된다. 개수는 0이나 음수도 포함하는 임의의 정숫값이 될 수 있다.

OrderedDict

딕셔너리 순서를 기억하는 Dict으로 옛날 python에서는 이를 활용하는 것이 유용했으며, 이제 내장 dict도 삽입 순서를 기억하기 때문에 덜 중요해졌다.

popitem(last=True)

OrderedDict의 popitem()은 (key, value)를 반환하고 제거한다. last가 True면 LIFO 방식으로, False면 FIFO 방식으로 반환다.

defaultdict

defaultDict은 dict과 유사하지만 key값이 없을 경우에 미리 지정해 놓은 초기(default)값을 반환하는 역할을 한다.
dict의 setdefault 와 유사하지만 더 간단하고 빠르다.

deque

deque는 double-ended-queue의 약자로 stack과 queue를 일반화한 것이다. deque는 메모리적으로 효율적이기 때문에 양쪽 끝에서 append와 pop이 모두 O(1)의 성능을 지원한다. deque는 다음과 같은 메서드를 지원한다.

1. append
2. appendleft
3. clear
4. copy
5. count(x)
6. extend
7. extendleft
8. index
9. insert
10. pop
11. popleft
12. remove
13. reverse
14. rotate

이 중 자주 쓰이는 것들만 살펴본다.

deque를 사용해서 iterable한 객체를 deque 객체로 만들 수 있다.

https://docs.python.org/ko/3/library/collections.html

문제:

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번은 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. N은 100,000보다 작거나 같은 자연수이고, 김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

출력:

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 만약 서로 대결하지 않을 때는 -1을 출력한다.

풀이방법:

 주어진 조건에 따라 수행하게 하는 구현문제다. 앞에서부터 순차적으로 두 사람을 뽑은 뒤에 각 사람이 k와 l인지 확인하고, 둘 중 하나에 해당하면 그 사람이 무조건 이기게 한다. 만약 각각 k와 l에 해당하면 반복문을 중단시킨다.(만약 둘다 아니라면 먼저 들어온 사람을 이기게 한다.) 

문제링크:

https://www.acmicpc.net/problem/1057

문제:

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 

다음과 같은 N=6인 경우 지도를 살펴보자.

이때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 파란색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력:

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

풀이방법:

check 함수를 사용해서 가로에 대해서 먼저 체크하고, 행과 열을 바꿔 세로에 대해서 체크하도록 한다.

check 함수 내에서는 현재값과 다음값의 높이 차이에 대해서 확인하고, 같다면 그대로 넘어간다. 만약 차이가 1보다 크다면 경사로를 놓을 수 없는 경우이기 때문에 0을 반환한다.

 만약 1 혹은 -1만큼의 차이가 나면 그 위치로부터 L의 경사로를 놓을 수 있는지 확인한다. 이 때 확인해야 하는 것은 낮은 지점의 높이가 L개 만큼 연속되는지, 이미 경사로가 놓아져 있는지 확인해야 한다. 이 과정이 모두 확인되면 visited배열에 경사로를 놓으며 넘어가고 그렇지 않다면 0을 반환하도록 한다. 이렇게 끝까지 탐색했는데 문제가 없는 경우라면 answer에 1을 더하도록 한다.

 모든 탐색을 마친 뒤에 answer 값을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/14890

문제:

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력:

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력:

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

풀이방법:

 양 끝점을 제외한 칸에서부터 왼쪽과 오른쪽을 각각 탐색해서 가장 낮은 위치를 찾아내고, 왼쪽의 가장 낮은 위치와 오른쪽의 가장 낮은 위치 더 낮은 값이 해당 칸에 빗물이 고인 수치다. 이 과정을 모든 칸에 진행하면서 값을 누적시키면 최종 답을 구할 수 있다.

문제링크:

https://www.acmicpc.net/problem/14719

문제:

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력:

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력:

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

풀이방법:

 투 포인터를 양쪽 끝값에 두고, 하나씩 이동시키면서 0에 가장 가까운 용액을 만들어 나가도록 한다. 포인터에 있는 값을 비교하고, start 값이 크다면 start를 이동하고, end가 크다면 end를 이동시키도록 한다. 이렇게 생성되는 용액의 특성값과 포인터 값들을 min_heap 정렬해두고, 모든 탐색을 마친 뒤에 min heap의 첫 값을 가져와서 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/2470

문제:

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력:

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

풀이방법:

시간 제한이 매우 엄격하게 정해져 있기 때문에 max_heap과 min_heap를 두 개를 사용해서 중간값을 구하도록 한다. 기본적인 아이디어는 양쪽에 채워나가면서 heap으로 정리했을 때, 가운데 값을 기준으로 정렬되는 것을 이용한다. max_heap에는 중간값보다 낮은 값들을 채워나가고, min_heap은 중간값보다 큰 값이 채워지도록 하게 한다. 개수가 짝수개인 경우 두 수 중에 작은 수를 말해야 하기 때문에 max_heap에 있는 값을 출력하도록 한다.  

문제링크:

https://www.acmicpc.net/problem/1655

문제:

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력:

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

풀이방법:

문제링크:

https://www.acmicpc.net/problem/2110