AquaplaneMode

파일명 정렬 0. 문제 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다. 버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되지만, 숫자..

1. 입력 첫째 줄에 가지고 있는 랜선의 개수 N개, 필요한 랜선의 개수 K개가 입력된다.이후 N+1 번째 줄까지 가지고 있는 랜선의 길이가 입력된다. 4 11 802 743 457 5392. 출력 K개 이상의 랜선을 만들 수 있는 랜선의 최대 길이를 출력한다. 200 랜선의 길이가 200일 때, 길이 802의 랜선에서 4개, 길이 743의 랜선에서 3개, 길이 457의 랜선에서 2개, 길이 539의 랜선에서 2개 총 11개 (4+3+2+2)를 만들 수 있다. 랜선의 길이가 201일 때, 길이 802의 랜선에서 3개, 길이 734의 랜선에서 3개, 길이 457의 랜선에서 2개, 길이 539의 랜선에서 2개 총 10개 (3+3+2+2)를 만들 수 있다. 따라서, 랜선 11개를 준비하기 위한 랜선의 최대 길..

문제 출처 1. 입력 첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어진다 4 4 3 2 1 0 0 0 0 0 0 9 0 1 2 3 40 : 빈 공간 1 ~ 6 : 물고기가 위치해 있으며, 위치한 물고기의 크기 9 : 상어의 위치 2. 출력 상어가 이동한 거리를 출력한다. 14 문제에선 시간을 출력하라 하지만, 1초에 1단위거리를 이동하기 때문에 편의상 거리로 치환한다. 3. 풀이 본 문제는 간단히 말해 상어로부터 가장 가까운 먹을 수 있는 물고기를 먹는 문제이다. 즉, 최단거리를 찾는 알고리즘을 요구하고 있기 때문에 BFS로 구현이 가능하다. 다만, 단순히 BFS로 구현하기에는 신경써야 할 조건이 있다. 상어의 크기보다 작은 물고기만 먹을 수 있다..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 문제를 보면 DP (Dynamic Programming) 문제의 일종이라는 것을 알 수 있다. 풀이 방법 1 $x=2$ 가능한 연산은 2로 나눠주는 것과 1을 빼주는 것이 있다. 어떤 연산을 수행하더라도 1이 되기 때문에 연산을 한 번만 수행하면 된다.when $x=2$, step = 1 $x=3$ 가능한 연산은 3으로 나눠주는 것과 1을 빼주는 것이 있다. 3으로 나눌 경우 바로 1이 된다. 1을 빼줄 경..

문제 출처 최소 스패닝 트리란, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 본 문제는 노드들과 노드 간 가중치가 주어졌을 때, 최소 스패닝 트리의 총 가중치 합을 구하는 문제이다. 본 문제를 풀기 위해서 Prim Algorithm을 사용하였다. 풀이 다음과 같은 그래프가 주어졌다고 가정하자. 그래프는 위키피디아 한글 문서의 예제를 사용하였다. 7 11 1 2 7 1 4 5 4 2 9 4 6 6 4 5 15 2 3 8 2 5 7 6 5 8 6 7 11 3 5 5 5 7 9 우선 임의의 노드 하나를 선택한다. 여기서는 1번 노드를 선택하겠다. 1번 노드에서는 2번 노드와 4번 노드에 방문할 수 있다. 이 중 최소값은 4번 노드에 방문하는 5가 되므로 ..

문제 출처 문제 본 문제는 MST(Minimum Spanning Tree)로 분류된다. 즉, 모든 집을 순회할 수 있는 길의 최소값을 구한 후, 그 중 가장 긴 길을 끊어버리면 된다. 풀이 코드 우선 Prim's Algoritm으로 코드를 구현하였다. import sys import heapq as h input = sys.stdin.readline # 0. get input V, E = map(int, input().split()) dic = {} # start : (end, weight) # 1. make a dict for _ in range(E): # edge의 개수만큼 start, end, weight = map(int, input().split()) if start not in dic...

문제 수열 A가 주어졌을 때, 가잔 긴 증가하는 부분수열을 구하는 문제이다. 풀이 본 문제는 LIS 알고리즘을 사용하여 풀었다. 또한, 본 문제를 풀기 위해 두 가지의 배열을 사용하였다. lis_arr : 이분 탐색을 사용하기 위한 배열 lis_total : LIS를 구하기 위해 사용한 배열 가령 [10, 20, 10, 30, 20, 50]가 입력값으로 주어졌다고 해보자. 처음 input인 10은 lis_arr.top인 -inf보다 크다. 그러므로 뒤에 붙여준다. lis_arr의 첫 번째 index에 들어갔기에 lis_total도 (10, 1) 꼴로 업데이트 해준다. 두 번째 input인 20은 lis_arr.top인 10보다 크다. 그러므로 뒤에 붙여준다. lis_arr의 두 번째 index에 들어갔기..

문제 자연수 $N$개로 구성된 배열이 있다. 시작지점 $S$와 끝 지점 $E$가 주어질 때, 두 지점을 포함한 구간의 자연수가 팰린드롬을 이루는지를 출력한다. 풀이 팰린드롬은 좌우대칭인 문자열이다. 임의의 팰린드롬을 $P$라고 가정하자. 만약 $P$ 좌우에 붙는 문자가 같은 문자라면, 새로운 팰린드롬 $xPx$ 역시 팰린드롬이라고 말할 수 있다. 즉, 범위가 주어질 때마다 해당 범위에서 앞뒤로 1씩 뺀 값이 팰린드롬인지 알 수 있다면, 새로이 팰린드롬인지 아닌지 확인하는 과정을 생략할 수 있다는 의미이다. 코드 # 팰린드롬? import sys input = sys.stdin.readline len_nums = int(input()) # 수열의 크기 nums = list(map(int, input().s..

문제 건물의 건설 순서와 시간이 주어졌을 때, 특정 건물을 짓기 위해 걸리는 시간 구하기 풀이 본 문제는 위상 정렬 (Topology Sort)과 *동적 계획법 (Dynamic Programming) *문제이다. 위상 정렬이란, 유향 그래프 (Directional Graph)의 꼭짓점을 변의 방향을 거스르지 않고 나열하는 것을 의미한다. 일반적인 위상정렬 알고리즘은 다음과 같이 실행된다. 부모 노드가 존재하지 않는 노드를 queue에 넣는다. queue에서 원소를 하나씩 빼면서, 해당 노드로부터 갈 수 있는 모든 노드들에 대한 연결을 제거한다. 앞선 과정을 반복한다. 그러나 본 문제는 건설 순서를 묻는 것이 아니라, 특정 건물을 짓기 위해 필요한 최소 시간을 구하는 것이기 때문에, 여기서 추가적인 접근을..

문제 두 선분의 교점이 존재할 때, 두 선분은 같은 집합으로 매핑된다. 다수의 선분이 주어질 때, 집합의 개수와 크기가 가장 큰 집합에 속한 선분의 개수를 출력한다. 풀이 본 문제를 풀기 위해서는 우선 CCW(Counter-Clock Wise) 알고리즘을 알아야 한다. CCW 알고리즘을 간단히 정리하자면 다음과 같다. 좌표평면 위에 세 개의 점 A, B, C가 있다고 가정하자. 점 A는 (ax,ay), 점 B는 (bx,by), 점 C는 (cx,cy)처럼 표현할 수 있다. 벡터의 외적을 활용하여 CCW를 $$ CCW(A,B,C) = (x_ay_b+x_by_c+x_cy_a)-(x_by_a+x_cy_b+x_ay_c) $$ 처럼 표현할 수 있다. 세 점을 순서대로 연결했을 때의 선이 왼쪽(반시계방향)으로 치우쳐..