[그리디] 튜플 - 2019 카카오 개발자 겨울 인턴십
해결 방법 Step1) 문자열을 파싱하여 각 집합을 벡터 v로 만들고, 벡터 v들로 이루어진 2차원 벡터 allv를 구성한다. Step2) allv의 v들을 크기가 작은 순으로 정렬한다. allv를 구성하는 벡터들의 크기는 순서대로 1, 2, 3, ..., allv.size()가 될 것이다. Step3) allv의 마지막 벡터를 이용하여 각 요소의 개수를 카운트 한다. Step4) allv의 n번째 벡터에서 카운트(element_cnt)가 0이 아닌 요소를 answer의 n번째 요소로 넣고, 해당 요소의 카운트를 1 감소시키는 작업을 allv의 첫 번째 벡터부터 수행한다. Step4 예시 {{1}, {2, 1}, {1, 2, 2}, {4, 1, 2, 2}} -> 요소를 카운트해보면 1은 1개, 2는 2개..
2022. 4. 10.
[그리디, 난이도 중] 프로그래머즈, 큰 수 만들기
문자열로 주어진 정수에서 k개의 수를 제거해서 만들 수 있는 가장 큰 수를 계산하는 문제이다. 백준에서 이런 유형의 문제를 풀었던 기억이 있었던 덕에 금방 해결할 수 있었다. 본인의 접근법은 스택의 원리를 이용하는 것이다. 순서대로 정수를 벡터에 넣으며, 기존 벡터의 마지막 인덱스 값(스택 상에선 top)이 현재 push한 정수보다 작을 경우 이 마지막 인덱스 값을 제거해주는 과정을 반복한다. 제거할 때마다 k의 카운트는 1씩 감소시켜야 한다. 해당 규칙으로 입력값의 정수들을 모두 벡터에 넣었음에도 불구하고 수를 k만큼 제거하지 못했을 경우도 있다. 이 과정까지 잘 수행 했다면 벡터의 요소는 ex) (5,4,3,2,1), (7,5,3,2,1), (9,9,7,7,5,5) 같이 내리막수일 것인데, 남은 k가..
2020. 10. 5.
[그리디, 난이도 중] 프로그래머즈, 구명보트
그리디 알고리즘이기 때문에 먼저 people을 오름차순으로 정렬하였다. 본인이 첫 번째로 생각한 접근법은 단순히 체중이 가벼운 순으로 묶는 방법이었다. 50 50 70 80 이 주어졌다면, (50,50),(70),(80) 총 3개의 보트로 테스트 케이스와 일치 50 70 80 이 주어졌다면, (50),(70),(80) 총 3개의 보트 테스트 케이스와 일치 그러나 이 접근법은 5 10 90 95 라는 반례와 막히게 된다. 이 경우에는 내 첫 번째 접근법으로는 답이 3이 나오는데, (5,95),(10,90) 총 2개의 보트로도 가능한 것이다. 정답처리된 본인의 두 번째 접근법은 무게가 가장 가벼운 사람과 가장 무거운 사람끼리 보트에 태우는 것이다. 단, 이 둘의 합이 무게 제한을 넘어갔을 경우에는 무거운 사..
2020. 10. 4.
