크루스칼 알고리즘을 이용하는 문제이다. 처음에 문제를 보고 크루스칼 알고리즘이 떠오르지 않아 헤매다가 구글링을 통해 찾아보며 풀이 방법을 알게 되었다. 크루스칼 알고리즘이란? 간단하게 설명하면 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 된다. 즉 최소 신장 트리를 구하기 위한 알고리즘이다. 참고 https://chanhuiseok.github.io/posts/algo-33/ 알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST) ## chanhuiseok.github.io 다른 풀이 코드 #i..
성공 코드(내 코드) 문자열로 저장되어 있는 숫자를 v 벡터에 정수로 변환하여 넣는다. 선택해야 하는 숫자의 개수만큼 반복문을 돌린다. 총 n개를 뽑아야 한다고 가정하면, 1번째 숫자를 고를 때 뒤에 최소한 n-1개의 숫자가 남아있어야 한다. 뒤에 숫자가 n-1개가 남기 전까지 v 벡터를 탐색하며 가장 큰 숫자를 찾는다. 찾은 가장 큰 숫자를 answer에 string으로 변환하여 추가한다. 똑같은 방법으로 2번째 숫자를 고른다. 이 과정을 n개의 숫자를 모두 뽑을 때 까지 반복한다. 이때는 뒤에 최소한 n-2개의 숫자가 남아있어야 한다. #include #include #include using namespace std; string solution(string number, int k) { strin..
성공 코드(내 코드) people을 오름차순으로 정렬한다. 보트에 최대 2명이 탑승 가능하므로 최솟값 + 최댓값을 더해본다. 더해준 값이 limit을 넘으면 2명 탑승이 안되므로 맨 뒤의 사람은 혼자 타야한다. 한명 밖에 타지 못하면 맨 뒷사람을 가리키는 인덱스를 줄여준다. 더해준 값이 limit을 넘지 않으면 2명 탑승이 가능하다. 즉 맨 앞사람을 가리키는 인덱스를 하나 증가시키고 맨 뒷사람을 가리키는 인덱스를 하나 감소시킨다. 이 과정을 맨 앞사람을 가리키는 인덱스가 맨 뒷사람을 가리키는 인덱스보다 작거나 같은 동안 반복해준다. #include #include #include using namespace std; int solution(vector people, int limit) { int answ..