[정렬] 병합 정렬 [Merge Sort]
병합 또는 합병 정렬에 대해 알아보자. 이는 분할 정복 방법을 통해 구현한다. (분할 정복은 큰 문제를 작은 문제 단위로 쪼개면서, 쉽게 풀 수 있는 문제 단위로 나눈 뒤 그것들을 다시 합치는 방식이다.) 퀵 정렬과 함께 빠른 정렬에 해당한다. 예를 들어보자. [6, 5, 3, 1, 8, 7, 2, 4] 숫자 1 ~ 8까지 들어있는 배열이 있다. 먼저 하나의 배열을 두 개로 쪼갠다. [6, 5, 3, 1] [8, 7, 2, 4] 그리고 다시 각 배열을 두 개로 쪼갠다. [6, 5] [3, 1] [8, 7] [2, 4] 또다시 각 배열을 두 개로 쪼갠다. [6] [5] [3] [1] [8] [7] [2] [4] 이제 더 이상 배열을 쪼갤 수 없다. 이제 두 개의 배열씩 합친다. 합칠 때는 둘 중에 값이 더..
[프로그래머스][Python] 가장 큰 수
문제를 정리해보자. "주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다." 주어진 정수를 이용해 가장 큰 수를 만들면 된다. 처음에는 완전 탐색을 시도했다. 하지만 시간초과로 실패했다. 두 번째에는 DFS를 시도했다. 하지만 구현에 어려움을 겪어 포기했다. 알고 보니 푸는 방법은 간단했다. 먼저 제한 사항을 보자. 예를 들어 [8, 883] 있다. 원소의 크기가 0이상 1,000 이하이므로, 각 원소를 문자열로 보고 3을 곱해준다. (1,000이 최대여서 4를 곱할 필요가 없다.) [888, 8838838883] 주의해야 할 점은 [0, 0, 0, 0] 같은 예이다. 0000이라는 수는 없다. 0으로..
[프로그래머스][Python] K번째수
조건에 따라서 array[i] ~ array[j]까지 정렬하고, k번째 원소가 무엇인지 찾으면 된다. def solution(array, commands): answer = [] for com in commands: i, j, k = com tmp = sorted(array[i-1:j]) answer.append(tmp[k-1]) return answer print(solution([1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]])) 다른 사람 풀이를 보자. def solution(array, commands): return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands)) lambda를..
