코딩테스트 문제 (11) - 비밀 지도
카카오 2018년 블라인드 코딩테스트 1번 문제입니다. 바로 문제부터 보겠습니다. 문제 1. array1 = [9,20,28,18,11], array2 = [30,1,21,17,28] => ['#####','# # #','### #','# ## ','#####'] 2. array1 = [46,33,33,22,31,50], array2 = [27,56,19,14,14,10] => ['######','### # ','## ## ',' #### ',' #####','### # '] 풀이 지도의 각 위치마다 두 개의 지도에서 어느 하나라도 '#' 이 있을 경우 '#'이고 모두 공백일 경우 공백으로 처리하는 부분에서 OR (|) 오퍼레이션을 사용하는 것을 알 수 있습니다. 파이썬의 bin은 정수를 이진화를 시켜줍..
코딩테스트 문제 (10) - 배열의 K 번째 큰 요소
제목 그대로 주어진 배열이 있을 때, 배열의 K 번째 큰 요소를 return하면 되는 문제입니다. 문제 1. array=[3,2,3,1,2,4,5,5,6], K=4 => 4 풀이 주어진 배열의 우선순위를 기반으로 가장 큰 값부터 K번 추출하면 되는 간단한 문제입니다. 힙을 사용해 쉽게 구현할 수 있습니다. kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다. 홍머스 정리 힙, heapq 난이도: 하 참조 , p456-457
코딩테스트 문제 (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) 약탈할 수 없..
