CodeDrive

문제:

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

출력:

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

풀이방법:

dfs와 DP를 같이 사용해서 이 문제를 풀었다. 기본적인 방식은 dfs를 사용해서 조건에 맞게 이동을 하며 최종 목적지까지 탐색을 한다. 그러다가 최종 목적지에 도달하면 재귀를 빠져나오면서 그 경로에 +1을 해주면서 다시 돌아오게 된다. 

이 과정을 가능한 모든 경우에 대해서 수행할 수 있기 때문에 최종적으로는 dp[0][0]에 저장되어 있는 값을 출력해주면 된다.

문제링크:

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

문제:

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력:

첫째 줄에 정수 N, r, c가 주어진다.

출력:

r행 c열을 몇 번째로 방문했는지 출력한다.

풀이방법:

시간 제한이 생각보다 많이 빡세기 때문에, 분할 정복을 사용하더라도 좀 더 효율적인 방법이 필요하다. 따라서 r, c 좌표를 통해서 해당 영역으로 찾아들어가는 방식을 사용하도록 한다.

모든 영역은 2^N-1 영역으로 4등분하며 순서대로 방문하기 때문에 r과 c가 이렇게 나눈 영역에서 어느 곳에 속하는지 알면 된다.

우선 나눠지는 순서대로 왼쪽 위를 0번째, 오른쪽 위를 1번째, 왼쪽 아래를 2번째, 오른쪽 아래를 3번째라고 하자

 1. 0번째 영역에 속하기 위해서는 r과 c가 모두 2^(N-1)보다 작아야 한다. 그리고 0번째 영역의 첫 숫자는 항상 0이기 때문에 시작 값에 대한 변화가 없다.

 2. 1번째 영역에 속하기 위해서는 r은 2^(N-1)보다 작으며, c는 커야 한다. 1번째 영역의 왼쪽 위 첫 숫자는 4^(N-1)*1에 해당한다. (총 숫자는 2^N*2^N= 4^N 개 있으며, 이를 사등분 하면 각 영역당 숫자는 4^(N-1)개 있다.)

 3. 2번째 영역에 속하기 위해서는 r은 2^(N-1)보다 크며, c는 작아야 한다. 첫 숫자는 4^(N-1)*2이다.

 4. 3번째 영역에 속하기 위해서는 r과 c가 모두 2^(N-1)보다 커야 한다. 첫 숫자는 4^(N-1)*3이다.

위 4개 비교를 통해서 각 영역에 들어가기 위해 r과 c를 2^(N-1)보다 크다면 그 값을 빼주고, N=1이 될 때까지 반복한다.

최종적으로는 r과 c는 0아니면 1에 해당하는 제일 작은 Z를 얻을 수 있고, 해당하는 영역의 숫자를 answer에 더해 출력해주면 된다.

문제링크:

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

문제:

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력:

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력:

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

풀이방법:

dfs를 사용해서 이 문제를 풀 수 있다. dfs는 다음과 같이 구성되어 있다.

1. 한 점으로부터 시작해 상하좌우를 탐색한다. (처음은 1행 1열)

2. 상하좌우를 탐색할 때, 아직 방문하지 않았고, 처음보는 알파벳이라면 그 방향으로 다시 dfs를 탐색한다.

3. dfs를 시작하는 순간마다. 현재까지 가지고 있는 알파벳 수를 기억해서 최대 몇칸을 지날 수 있는지 확인한다.

4. 더 이상 이동하지 못하는 경우에 한 dfs를 빠져나오게 되며, 방문 기록과 알파벳 탐색 기록을 지운다.

최종적으로 3번을 통해 기록한 값을 출력하면 된다.

문제링크:

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

문제:

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력:

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

풀이방법:

1. 산술평균 : sum 함수를 통해서 합계를 구하고 N으로 나눈 뒤 round 한다.

2. 중앙값 : 배열을 정렬하고, N//2의 인덱스 값을 출력한다. (항상 홀수 길이를 가지고 있기 때문에 가능)

3. 최빈값 : collections의 Counter를 사용해서 각 값의 출력 횟수를 구하고, most_common으로 빈도수로 정렬한다. 이 때, 최빈값이 여러 개 있는지 확인한 후 적절하게 출력하도록 한다.

4. 범위 : 배열의 최댓값에서 최솟값을 뺀다.

문제링크:

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

문제:

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력:

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

풀이방법:

 3중 배열을 사용하거나 2중 배열 2개를 사용하는 bfs 문제다. 대부분의 bfs 문제들은 방문 여부를 기록하는 2중 배열을 사용하는데, 이 문제에서는 도중에 한 개의 벽을 부수고 이동할 수 있다는 점 때문에 3중 배열을 사용하도록 한다. 3중 배열 중 앞 두 값은 일반적인 좌표 탐색을 위해 사용되고, 맨 마지막 값은 broken으로써 0과 1만을 가지는 값으로 사용한다. 즉, broken이 처음에는 0으로 진행하다가, 부술 수 있다면 broken이 1로 이동하여 시간 손실 없이 bfs를 계속해서 진행할 수 있도록 한다.

 visited에다가 한 step씩 진행하면서 거리를 기록하며, 최종적으로 목표하는 점의 broken의 0과 1을 모두 탐색하도록 한다. 만약 두 값 모두 있다면 둘 중 작은 값으로, 하나만 있다면 그 값을 출력하고 없다면 -1을 출력하면 된다.

문제링크:

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

문제:

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력:

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력:

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

풀이방법:

 다익스트라 알고리즘을 사용하는 기본적인 문제다. dp를 inf 값으로 초기화한 뒤 주어진 시작점으로부터 다익스트라 알고리즘을 사용해서 최단 경로 알고리즘을 구하면 된다. 다익스트라 알고리즘에 대한 설명은 다른 게시글에서 업로드 할 예정이다.

문제링크:

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

문제:

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력:

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력:

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

풀이방법:

 문제 설명을 어렵게 했지만 결국 입력으로 주어진 좌표를 작은 순으로 인덱스를 할당하면 되는 문제다. 이 때, 같은 값은 같은 인덱스로 설정해야 한다.

 그래서 우선 수를 정렬하기 위해서 set, list, sorted를 순서대로 사용하고, 이렇게 얻은 값은 이제 새로운 좌표가 된다. 이제 입력에다가 새로 얻은 좌표를 다시 할당하고 출력하도록 한다.

문제링크:

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

문제:

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력:

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

풀이방법:

for(bfs) 방법을 사용해야 하는 방법으로 시간이 많이 필요한 문제라 생각했고, pypy3으로 통과했다. 지도의 모든 L에 대해서 bfs를 수행한다. 각 bfs에서는 해당 L로부터 가장 멀리 갈 수 있는 거리를 찾는다.

문제링크:

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

문제:

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력:

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

풀이방법:

 일반적인 브루트포스 방법을 사용하면 시간초과가 날 수 있기 때문에, 비트마스킹이라는 방법을 사용했다. "anta", "tica"에서 사용되는 "a","n","t","i","c"를 제외하고 나머지 알파벳에 대해서 20개의 비트가 있다고 가정하고, 사용하면 1을 올리고, 사용하지 않으면 0으로 냅두는 방법을 사용한다. 

 항상 5개의 알파벳은 사용해야 하기 때문에, k가 5보다 작으면 읽을 수 있는 단어가 없다. 이외의 경우에는 가능한 알파벳에서 k-5개의 알파벳을 뽑은 뒤(가능한 모든 조합에 대해), 비트마스킹을 통해 갯수를 세고, 그 중 최댓값을 반환하도록 한다.

문제링크:

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

Functools

Functools module은 high-order-function(고차원 함수)를 위해 고안된 것으로 다른 함수에 적용하거나 다른 함수를 반환하는 모듈이다. Functools에는 다음과 같은 함수들을 제공한다.

1. lru_cached
2. cmp_to_key
3. total_ordering
4. partial
5. reduce

1. lru_cached

@functools.lru_cache(maxsize = 128 )

lru_cache(user_function)

lru_cache는 함수의 리턴 결과를 캐시해 주는 데코레이터이며, 최종 요청 이후에는 캐시된 결과를 리턴한다. maxsize는 캐시할 수 있는 최대 갯수를 의미하며, Least Recently Used(LRU)를 사용하기 때문에 최근에 참고되지 않은 데이터가 교체된다.

다음과 같이 재귀를 사용해서 factorial을 구하는 함수가 있다고 하자.

Jupyter의 timeit 매직함수를 사용해서 n이 10일 때, 20일 때 시간을 측정해보도록 한다.

이번에는 functools의 lru_cahce를 데코레이터로 설정해서 factorial을 재정의하고, 다시 한 번 10, 20일 때 시간을 측정해보도록 한다.

내부적으로 각 factorial의 값을 캐시하고 있기 때문에, 시간 단축이 많이 발생한 것을 알 수 있다.

2. cmp_to_key

sorted와 같은 정렬 함수의 key에 함수로 정렬을 하기 위해서 사용한다. 이 때 사용하는 함수는 두 개의 인수를 받아야 하고, 그들을 비교해서 작다면 음수, 같으면 0, 크다면 양수를 반환하도록 해야 한다.

예시는 다음 문제를 사용하도록 한다.

https://codedrive.tistory.com/429

3. total_ordering

@total_ordering 데코레이터를 사용하면, 사용자 정의 객체, 즉 class끼리 비교하거나 정렬할 수 있다. 다음 블로그 글이 잘 설명하고 있는 것 같아 참조한다.

https://velog.io/@doondoony/Python-total-ordering-decorator

4. partial

 partial은 한 함수의 특정 인자를 위한 함수를 만들기 위해 사용한다. 숫자나 문자열을 정수(integer)로 변환해주는 파이썬 내장 함수 int(x, base=10)을 재활용하여, 이진수로만 변환해주는 새로운 함수를 만들 수 있다.

 기존에 int 내장 함수는 위와 같이 작동한다. partial을 사용해서 각 진수로 변환할 수 있는 새 함수를 정의하도록 한다.

이처럼 partial은 여러 인자를 받는 함수를 하나의 인자를 고정시켜서 새로운 함수로 정의하고자 할 때, 사용한다.

5. reduce

reduce는 반복가능한 객체(iterable)에 함수를 순차적으로 적용한다. 단, 각각의 객체에 적용하는 것이 아닌 누적형식으로 적용한다.

즉 위 예시는 15 = (((1+2)+3)+4+5) 와 같은 방식으로 적용되어 계산된 것과 같다.

Reference

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