https://programmers.co.kr/learn/courses/30/lessons/42861?language=java 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다. 연결할 노드 A, B와 비용 c가 들어있는 costs 배열이 주어졌을때, 비용 c 를 들여 노드 A, B 를 연결해야 하는지를 판단하는 부분이 핵심입니다. 만약 두개의 노드가 이미 직접적으로든/ 혹은 우회적으로든 연결되어 있다면, 굳이 추가 비용을 들여 A,B 를 연결할 필요가 없습니다. 반면 노드 A, 노드 B 가 서로 다른 노드와는 ..
https://programmers.co.kr/learn/courses/30/lessons/42885?language=java 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다. 한번 배를 띄울때 최대한 무게를 많이 채우는 과정을 계속 반복해 나가면 전체적으로 최적해를 구할 수 있습니다. 사람을 몸무게 순서로 정렬하고, 몸무게가 적게 나가는 순서대로 배에 태울 사람을 선택합니다. 몸무게가..
https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다. 이 문제에서 쟁점은 크게 세가지 입니다. 부분적인 최적해가 전체적인 최적해가 될 수 있는가 부분적인 최적해를 어떻게 구할 것인가 부분적인 최적해를 구할때 시간복잡도 최소화 1. 부분적인 최적해 정의 전형적인 Greedy 문제로서 난이도는 평이한것 같습니다. 우선 부분적인 최적해를 어떻게 설정해야지 전체적인 최적해가 될 수 있을지에 대해 생각해보면, k = 1, 2, 3, 4, .... 처럼 제거하는 숫자의 개수를 증가시켜 가는 방식으로 부분..
https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr Greedy 알고리즘은 부분적인 최적해를 계속 확장 시켜서 전제적인 최적해를 찾는 알고리즘 입니다. 특정 위치에 도달해서 알파벳을 만들때 조이스틱을 몇번 위아래로 움직여야 하는지는 정해져 있습니다. 결정해야하는 부분은 오른쪽으로 가느냐 왼쪽으로 가느냐 입니다. 이때 이미 알파벳이 완성된 부분으로 가는 것이 최적해를 찾는데 도움이 되지 않기 때..