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

문제 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 문제 지문 파악하기 구르미의 알고리즘 풀이 문제 지문 파악하기 이번에도 문제의 입력을 통해서, 문제를 파악해보도록 하겠습니다. 다음은, 문제의 첫 번째 입력입니다. 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 문제 지문 파악하기 강사님의 알고리즘 풀이 구르미의 알고리즘 풀이 문제 지문 파악하기 문제에 따르면, 입력 numbers에 대해서 해당 문자열이 가장 큰 수를 만들게끔 k개를 빼야 합니다. 예제 입력을 살펴보죠. numbers = "4177252841" k = 4 어떻게 가장 큰 수를 만들 수 있을까요? 먼저, 일단 숫자가 나오면 저장합니다. 그리고 그 보다 큰 숫자가 나오면 저장했던 수를 빼보면 어떨까요? 자 시작해봅시다. 처음 숫자인 4를 넣습니다. collected = ["4"] ( k = 4 ) 그 후 1을 넣습니다. 1은 4보다 작기 ..

이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다. 문제 URL 체육복 Contents 문제 지문 파악하기 강사님의 알고리즘 풀이 구르미의 알고리즘 풀이 문제 지문 파악하기 이 문제는 얼마나 많은 학생들이 체육복을 입을 수 있느냐를 물어보는 문제입니다. 제일 중요한 것은 이것입니다. reserve에 있는 학생들, 그러니까 여벌이 존재하는 학생들은 자신의 앞,뒷 번호 학생에게 체육복을 전달할 수 있다. reserve, lost에 둘 다 들어있는 학생들은 체육복을 빌려주지 않는다. (어찌보면 당연한 것) "탐욕법"은 말 그대로 그 상황에서 제일 최적의 해를 선택하는 알고리즘 패러다임입니다. 먼저 일련의 예를 들어봅시다. 입력 : n = 5 ..