구름톤 챌린지 | 3주차 학습일기 [14일차 / 15일차]

구름톤 코딩테스트 챌린지 3주차 학습일기입니다.

3주차 학습일기

구름톤 챌린지

Day14 작은 노드

문제 분석

N개의 노드, M개의 간선이 주어진다. 첫 노드는 K이고 주어진 간선들 중 최소값의 노드로 이동한다. 중복 이동은 허용되지 않으며 자기 자신으로 향하는 간선은 없다. 계속 이동해 더이상 이동할 수 없을 때까지 방문한 노드의 총 수와 도착한 노드의 번호를 출력한다.

풀이 전략

1. 연결 정보를 이중 배열로 담고, 현재 노드와 방문한 노드의 수를 체크하는 변수를 정의해 놓는다.

2. 반복문을 활용해 처음으로 만나는 연결 가능한 노드로 이동하고 방문 노드 수를 올려주고 현재 노드 값을 업데이트 해준다. (자동으로 최소값을 찾게 된다.)

3. 방문한 노드의 모든 행과 열을 방문처리한다.

4. 위의 2, 3번을 더 이상 진행할 노드가 없어질 때까지 반복한 뒤 방문한 노드의 수와 현재 노드를 출력한다.

결과

익숙하지 않은 그래프 문제였는데 차분히 풀어냈다. 시간은 1시간 조금 넘게 소요됐다. 결과적으로 구르미에게 바지를 입힐 수 있게됐다. 바지 먼저 입혀주시지 하는 생각이 들었다.

14일차 미션 성공

14일차 미션 블록

Day15 과일구매

문제 분석

1부터 N개의 과일이 있다. 각 과일은 P(i)의 값을 갖고 C(i)의 포만감을 준다. 모든 과일은 가격 크기인 P(i) 수로 똑같이 나눌 수 있고 그 때  각 조각의 포만감도 비례해서 등분된다. 예산이 K이 있을 때 K를 모두 사용해서 과일을 구매해서 얻을 수 있는 최대 포만감을 구하는 문제이다.

풀이 전략

1. 과일의 수만큼 N 길이에 각 엘레멘트가 3의 길이의 배열을 갖는 N x 3 이중배열을 생성한다. 각 내부 배열은 [과일의 값, 포만감, 조각의 포만감]을 담는다. *조각의 포만감은 (포만감 / 과일의 값) 이다.

2. 중복 값을 허용하지 않는 Set을 생성해 조각의 포만감 값을 담아준 뒤 내림차순 정렬해준다.

3. 조각의 포만감이 높은 순으로 예산 K를 순차적으로 소진해준뒤, K를 다 소진했을 때 얻은 총 포만감을 출력해준다.

결과

문제가 몇 가지 케이스들이 해결이 되지 않는 문제가 있었다. 그 경우는 과일의 수가 적어 K를 다 쓰지 못하는 경우도 고려해야 하는 경우였다. 그리하여 결국 문제를 성공시켰고 구르미에게 돋보기를 손에 쥐어주었고 블럭도 총 15개를 얻었다.

15일차 미션 성공

15일차 미션 블록

3주차 구르미 진화

3주차 구르미