문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 이 문제의 경우 효율성 검사가 들어가있다. 그 의미는 무엇이냐? 완전탐색이나 다중 for문과 같은 방식은 out이라는 뜻! 필자의 경우 다이나믹 프로그래밍(Dynamic Programming) 기법을 사용하였다. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍이란 복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 것을 의미한다. 한마디로 하나의 큰 문제를 여러개의 작은 단위로 쪼갠다는 뜻이다. 분할 정복 알고리즘(Divide and..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 이 문제는 '서로소 집합'과 '크루스칼 알고리즘'을 알고 있으면 손쉽게 풀 수 있다. https://born2bedeveloper.tistory.com/29 [JAVA] 서로소 집합(Disjoint Sets)과 연산(Union & Find) 서로소(Disjoint) 서로소(disjoint)는 공통으로 포함하는 원소가 없는 두 집합의 관계다. 서로소 집합(Disjoint Sets)과 연산(Union & Find) 서로소 집합은 위 그림처럼 서로소 집합..

최소 비용 신장 트리 크루스칼 알고리즘은 최소 비용 신장 트리를 찾는 알고리즘이다. 최소 비용 신장 트리(MST) 란? Minimum Spanning Tree의 약자로 '최소 연결 부분 그래프'를 의미한다. 정점 N개를 가지는 그래프에서 (N - 1)개의 간선을 연결해야 한다. 연결한 간선의 가중치 합이 가장 최소가 되는 그래프 모든 정점이 연결되어야 하나, 싸이클이 되면 안된다. 그림을 통해 이해해보자. A : 간선이 6개이므로 정점 - 1개를 가져야 하는 신장트리 법칙에 위배되며, 그래프가 순환(싸이클)하고있으므로 연결그래프다. B : 간선은 4개지만, 간선끼리의 가중치 값이 8 + 5 + 4 + 3 + 2 = 22이므로 최소 신장트리가 아닌 신장트리의 일부다. C : 간선이 4개이며, 싸이클이 없고..

서로소(Disjoint) 서로소(disjoint)는 공통으로 포함하는 원소가 없는 두 집합의 관계다. 서로소 집합(Disjoint Sets)과 연산(Union & Find) 서로소 집합은 위 그림처럼 서로소 집합끼리 나눠진 원소를 처리하기 위한 자료구조이다. 서로소 집합은 크게 두 가지 연산을 기반으로 구현된다. Union : 서로 다른 두 개의 집합을 병합한다. Find : 원소가 어느 집합에 속해있는지 찾는다. 그렇다면 어느 집합에 속해있는 지는 어떻게 판단할까? 원소 1, 2, 3, 4가 있을 때, 각 원소가 가리키는 대상의 '집합'이 자신이 속한 '집합'이라고 간주한다. 따라서 원소 2가 1을 가리키고 있다면, 원소 2는 1의 집합에 속한 원소라고 할 수 있다. 서로소 집합의 두 연산을 빗대 Un..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 이 문제를 보고 처음 생각한 로직은 이랬다. 1. people 무게 오름차순으로 정렬 2. 가벼운 사람부터 구명보트에 limit넘기지 않도록 최대한 때려 넣기(?) 그런데 자꾸 테스트케이스가 오류가 나서 살펴보니... 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 ..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 이 문제를 보고 처음에 필자는 이렇게 생각했었다. '조합을 이용해서 숫자를 다 뽑은 다음에, 가장 큰 수를 뽑으면 되지 않을까?' 결과는? 무수한 런타임 에러의 환영을 받았다 ㅎㅎ.. number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. 해당 제한사항 때문에 문자에서 int로 변환하는 과정에서 메모리 초과 이슈로 펑펑 터질 수밖에 없는 것이다^^.. 완전탐색으로 불가능하다면 그리디(greedy)하고 탐욕스럽게 문제를 풀어야한다고 깨닫고 로직 노선을 다시 변경했다. number = "4177252841", k = ..