구르미의 개발 이야기 구르미의 개발 이야기

문제 URL 섬 연결하기 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 이 문제는 결론부터 말하면 "가중치 그래프에서 최소 신장 트리(이하 'MST')"를 만드는 문제입니다. 가중치가 있는 그래프에서 최소 신장 트리를 만드는 방법은 크게 2가지가 있습니다. 프림 알고리즘 크루스칼 알고리즘 저는 여기서 "크루스칼 알고리즘"을 통해서 가중치 그래프를 MST로 만들 것입니다. MST와 크루스칼 알고리즘의 자세한 설명은 다음을 참고하세요. MST와 크루스칼 알고리즘 먼저, 문제의 입력을 통해서 그래프를 만들어야 합니다. 문제의 예제를 기준으로 만들어보겠습니다. 입력: n = 4 costs = [ [0,1,1], [0,2,2], [1,2,5], [1,3,1], [2,3,8] ] 문..

문제 URL 저울 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 자 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 입력입니다. 입력 : weight = [3, 1, 6, 2, 7, 30, 1] 다음 무게를 지닌 추들로 측정할 수 없는 최소 무게를 찾아야 합니다. 먼저 손으로 풀어봅시다. 무게 = 1 w = 1 // 무게 1짜리 1개 이 때는 무게 1인 추 1개로 측정이 가능합니다. 무게 = 2 w = 2 = 1 + 1 // 무게 2 짜리 1개, 무게 1짜리 2개 무게 2는 무게 1짜리 추 2개 혹은 무게 2짜리 추 1개로 측정이 가능합니다. 무게 = 3 w = 3 = 1 + 2 // 무게 3짜리 1개, 무게 1짜리 1개 + 무게 2짜리 1개 무게 3은 무..

문제 URL 단속카메라 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 입력입니다. 입력 : routes = [ [-20, 15], [-14, -5], [-18, -13], [-5, -3] ] 이 경우 0번부터 3번까지의 차량을 그림으로 나타내면, 다음과 같습니다. 이 때, -5 지점에 카메라를 설치하면, 1번, 3번 차량을 감시할 수 있습니다. 이제 -15 지점에 카메라를 세우면 0번, 2번 차량을 감시할 수 있습니다. 뭐 문제에서는, -15라고 했지만, 사실 0번과 2번만 겹쳐있는 -18부터 -13 중 어느 곳에 설치하더라도 괜찮습니다. 이렇게 해서 최소 2대의 카메라로 모든 차량을 감시할 수 있습..

문제 URL 구명보트 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 문제의 첫 번째 입력입니다. people = [70, 50, 80, 50] limit = 100 여기서 70kg인 사람을 먼저 내보낸다고 합시다. 구명 보트의 최대 무게 limit이 30kg가 빕니다. 그러나 무인도에 남은 인원 중 30kg 이하인 사람은 없습니다. 그럼 70kg인 사람 한 명만 나갑니다. people = [50, 80, 50] // 70kg 사람 나감. limit = 100 (100 >= 70) answer = 1 // 필요 보트 개수 이제 50kg인 사람을 내보냅시다. 이 때 limit에 비해 구명보트는 50kg인..

문제 URL 조이스틱 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 구르미의 알고리즘 풀이 다음을 코드로 나타내면 다음과 같습니다. 먼저 PYTHON 코드입니다. PYTHON 코드 def solution(name): LUT = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,12,11,10,9,8,7,6,5,4,3,2,1] answer = 0 for c in name: answer += LUT[ord(c) - ord('A')] n = len(name) left_or_right = n-1 for i in range(n): _next = i + 1 while _next < n and name[_next] == 'A': _next += 1 left_or_right =..

문제 URL 카펫 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다. 입력: brown = 10 red = 2 이 때, 만들 수 있는 직사각형은 문제의 그림처럼 빨간색 타일이 2x1 형태로 잡혀 있는 형태입니다. B B B B B R R B B B B B 따라서, [4, 3] 형태를 반환해야 합니다. 이번엔 두 번째 입력을 살펴봅시다. 입력: brown = 8 red = 1 이번엔 다음과 같이 빨간색 타일이 1x1 형태로 잡혀있을 때, 가장 큰 가로, 세로인 3x3인 사각형이 됩니다. B B B B R B B B B 이번엔 세 번째 예제입니다. 입력: brown = 24 red = 2..

문제 URL 숫자 야구 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다. 입력: baseball = [ [123, 1, 1], [356, 1, 0], [327, 2, 0], [489, 0, 1] ] 여기서, 정답이 될 수 있는 경우의 수를 구합니다. 어떻게 구할 수 있을까요? 실제로 알아보기 위해서는 야구 게임을 해보는 수밖에 없습니다. 먼저, 야구게임에서 만들 수 있는 수들은 123 ~ 987까지 각 자릿수가 겹치치 않는 수들입니다. candidate = [123, 124, 125, ... , 987] //각 자릿수는 겹치지 않습니다. 이제 1Round를 시작해보죠. request..

문제 URL 소수 찾기 Contents 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 첫 번째 입력입니다. 입력: numbers = "17" numbers를 통해서 만들 수 있는 문자열의 모든 경우의 수는 다음과 같습니다. permutations = [ "1", "7", "17", "71" ] 각각 numbers에서 1개를 선택했을 때, 만들 수 있는 경우의 수와 2개를 선택했을 때 만들 수 있는 경우의 수를 합쳐진 것을 알 수 있습니다. numbers에서 1개를 선택했을 때 만들 수 있는 경우의 수: ["1", "7"] numbers에서 2개를 선택했을 때 만들 수 있는 경우의 수: ["17", "71"] 이 경우..