탐욕법
-
프로그래머스 Lv.3) 섬 연결하기알고리즘/프로그래머스 고득점 Kit 2020. 6. 5. 18:41
고득점 Kit - Greedy(탐욕법) 섬 연결하기 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 find - union가 부족하다고 판단되서, 다시 감을 잡고자 다시 풀었다. 풀이 방법은 처음 풀었을 때와 크게 차이점이 없었고, find 메소드와 union메소드만 잘 짜준다면 find - union문제는 무리 없이 풀 수 있을 것 같다. 로직 1. parents 배열을 선언 및 초기화한다. 2. 두 섬의 번호와 비용을 담을 class Island 를 선언한다. 3. 주어진 연결 정보를 담은 배열을 순회하면서, Island 변수를 만들어 우선순위 큐에 담아준다. ( 비용 오름차순 정렬) 4. Queu..
-
프로그래머스 Lv.2) 큰 수 만들기 (Greedy)알고리즘/프로그래머스 고득점 Kit 2020. 6. 3. 18:13
큰 수 만들기 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 고득점 Kit 중 greedy에 해당하는 문제다. 이 문제는 전에 풀었었는데, 다시 풀기에 실패한 문제다. Lv2지만 체감상 Lv3였다.. 도저히 모르겠어서 전에 풀었던 코드를 봤는데, 내 머릿속에서 나온 코드가 아닌 것 같다. 그래서 다른 분들의 풀이를 보고 다시 풀었다. 두 풀이 모두, 탐색 범위를 변경해가면서 가장 큰 갑을 넣어주는 로직이다. 가장 큰 값을 찾았을 때, 앞에 있는 수를 모두 지울 수 있다면 답에 더해주고, 아니면 범위를 재설정하는 방법이다. count를 소진할 때 까지 진행하면서, 답을 찾는다. start, end 그리고 max와 maxIdx를 설정해주는 이유는, 완전탐색의 경우 시간초과가 뜨기 때..