코딩테스트 문제 (9) - 효율적인 화폐구성
문제 화폐의 단위가 배열 $a$로 주어지고 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 $m$원이 되도록 하려고 합니다. 각 화폐를 중복해서 사용할 수 있습니다. $m$원을 만들기 위한 최소한의 화폐개수를 구하는 문제입니다. $m$원을 만들 수 없을 때는 -1을 return합니다. 1. a = [2,3], m = 15 => 5 2. a = [3], m = 4 => -1 풀이 1번 문제부터 생각해보겠습니다. 15를 만드는 경우의 수는 [2,2,2,3,3,3], [3,3,3,3,3],[2,2,2,2,2,2,3] 의 3가지가 있는데 이중 [3,3,3,3,3]이 개수가 제일 적어 답은 5가 됩니다. 먼저, 화폐단위보다 작은 $m$은 조합을 만들 수 없기 때문에 -1을 return합니다. $m$을 만들..
코딩테스트 문제 (8) - 개미 전사
문제 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 침입합니다. 식량창고는 정해진 수의 식량을 저장하고 있고 일직선으로 나열되어 있습니다. 메뚜기 정찰병은 인접한 식량창고가 공격받으면 바로 알아차릴 수 있습니다. 따라서, 개미 전사가 정찰병에게 들키지 않고 식량창고를 털기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 공격해야 합니다. 식량창고가 배열로 주어졌을 때, 개미 전사가 약탈할 수 있는 최대 식량을 구하는 문제입니다. 1. [1,3,1,5] => 8 2. [1,2,3,1] => 4 3. [2,7,9,3,1] => 12 풀이 1번 케이스의 [1,3,1,5]를 생각해보면, 개미가 첫 번째 인덱스를 (1) 약탈한다면 세 번째 인덱스 (1) 이나 네 번째 인덱스밖에 (5) 약탈할 수 없..
코딩테스트 문제 (5) - 가장 큰 수
문제 이름이 가장 큰 수로 되어 있지만 당연하게도 배열 중 가장 큰 수를 찾는 문제는 아닙니다. 이 문제는 항목들을 조합하여 만들 수 있는 가장 큰 수를 출력하는 문제입니다. 문제 1. [10,2] => '210', 2. [3,30,34,5,9] => '9534330' [10,2] 케이스의 경우 10을 추출하는 것이 아닌 두 원소의 조합 '102'와 '210' 중 더 큰 수를 출력해야 합니다. 배열의 원소는 정수입니다. 풀이 [10,2]의 경우 10이 아닌 2가 앞에 위치하도록 정렬해야 합니다. [3,30,34,5,9]의 경우에는 9가 맨 앞에 위치하도록 정렬해야합니다. 이러한 순으로 정렬한 후에 각 원소를 string으로 만들어 join 메소드를 이용해 합치면 될 것 같습니다. 배열의 원소가 정수로 들..
코딩테스트 문제 (4) - 구간 병합
이 문제는 구간들을 원소로 가진 입력 리스트에 대해 겹치는 구간을 병합한 결과를 제출하는 문제입니다. 문제 1. [[2,6],[15,18],[1,3],[8,10]] => [[1,6],[8,10],[15,18]] 입력은 정렬되지 않은 상태로 들어옵니다. 풀이 먼저 입력이 정렬되지 않았으니 시작점 기준으로 정렬해야 할 것 같습니다. 그 후, for 루프를 통해 각 구간을 순회하면서 전 구간의 끝점과 현 구간의 시작점을 비교해서 두 값이 겹치게 되면 병합하면 될 것 같습니다. kaggle.com 의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 난이도: 하 참조 , p497-498 leetcode.com/problems/merge-intervals/
코딩테스트 문제 (3) - 두 배열의 교집합
두 배열의 교집합을 찾는 문제입니다. 중복된 문자는 고려하지 않고 한 문자로 취급합니다. 문제 1. array1 = [1,2,2,1], array2 = [2,2] => [2] 2. array1 = [4,9,5], array2 = [9,4,9,8,4] => [9,4] 풀이 array1과 array2에 대해 이중 for 루프를 돌면서 결과 집합 (파이썬의 set)에 추가하면 될 것 같습니다. 하지만 array 2개의 루프를 수행하니 시간 복잡도는 $O(n^2)$가 되겠네요. 더 작은 시간 복잡도가 걸리는 방법은 뭘까요? array1에 대해서는 그대로 for 루프를 수행하고 for 루프 안에서 해당 array1의 값을 array2에 대해 이진 탐색으로 값을 검색하면 어떨까요? 이진 탐색은 시간 복잡도가 $O(..
