프로그래머스 스킬체크 lv3,4 리뷰

불만족스러운 점

왜 한번 보면 다시 못볼까?

그리고 문제출처도 프로그래머스 내부에서 랜덤으로 돌린 문제일텐데 다시 볼 수 있게하면 좋겠다.

문제와 풀이를 잘 설명못하겠다.

 

lv3

1번문제

문제설명

화폐 단위가 담긴 money배열(길이100이하)이 주어진다.

각 화폐는 무한하게 사용 가능하다.

주어진 화폐들로 금액n(100만인가10만이하)을 만드는 경우의 수를 구하여라.

 

풀이방식

현재 가지고 있는 화폐단위를 x라고하자.

이전에 t-x원을 만들 수 있었으면 t원도 x를 이용해 만들 수 있다.

따라서 n만큼의 0으로 초기화된 dp를 만든 뒤 dp[0] = 1로 초기화한다.

dp[t] = dp[t] + dp[t-x]이다.

 

2번문제

긴지문이 주어지고 이걸 구현해봐라.

 

풀이방식

2차원배열을 병합하고 병합을 해제하는 과정이 있었다.

2차원배열의 최대크기는 51*51이다.

따라서 parent[51*51]을 이용한 union find를 사용했다.

union find를 이용해 어떤것들이 서로 병합돼있는지 쉽게 판단가능하다.

병합을 해제할때도 parent[i] = i를 하면 편리하다.

나머지 쿼리는 자유롭게 구현해도 될 것 같다.

 

lv4

1번문제

원형dp문제이다.

배열이 주어지고  인접한 것 끼리는 더할  수 없을때, 합의 최댓값을 구하는 문제이다. 

 

풀이방식

원형dp은 끝과 처음이 만나는 케이스만 잘 처리하면 된다.

0번을 선택하면 N-1번을 선택할 수 없다.

0번을 선택하지 않으면 N-1번을 선택할 수 있다.

두 케이스에 대해 dp를 돌리고 이중최댓값을 채택했다.

 

2번문제

0과 distance사이에 Point들이 주어진다.

최대N개의 point를 지울 수 있을때

인접한 point의 최솟값의 최대를 구하는 것이다.

 

풀이방식

경험적으로 비슷한 문제를 많이봤고 매개변수탐색으로 풀었다.