구름톤 챌린지 | 3주차 학습일기 [11일차 / 12일차 / 13일차]

구름톤 챌린지 3주차 학습일기입니다.

구름톤 챌린지 3주차 학습일기

이전글

구름톤 챌린지 | 20일간의 코딩테스트 챌린지 시작 (Feat. 3일차)

 

구름톤 챌린지 | 2주차 학습일기 [9일차 / 10일차]

Day11 통증 (2)

지난 통증 문제에서 한 단계 업그레이드 된 문제이다.

문제분석

통증을 줄이는 두 개의 아이템을 사용해서 0을 만드는데 이 때 아이템을 사용할 수 있는 모든 경우의 수 중 최소값을 출력하는 문제이다.

풀이 전략

1. 각 경우마다 아이템 2개를 사용해 통증을 0으로 만들 수 있는지 확인한다.

2. 0으로 만들 수 있을 경우 사용한 아이템 수가 여태까지의 최소값보다 작은지 비교 후 작을 경우 값을 업데이트 해준다.

3. 모든 경우의 수를 확인 한 후 최소값을 출력한다.

4. 만약 마지막 까지 단 한 번도 통증을 0으로 만들 수 없다면 -1을 출력한다.

결과

성공! 구르미에게 구름모양 머리 가발을 씌워줄 수 있었다. 알고보니 구르미 머리카락이 없는 아이였네?!

11일차 미션 성공

11일차 미션 블록

Day12 발전기

문제 분석

N x N 격자 안에 0과 1이 주어지는데, 1이 쓰여진 곳은 집이 있는 곳이다. 집에 전기를 공급하기 위해 상하좌우 인접한 칸에 다른 집이 있어야 한다. 만약 없다면 발전기를 지어야 한다. 이 때 모든 집에 전기 공급하기 위해 필요한 발전기의 최소수를 구하는 문제이다.

풀이 전략 1

1. 각 칸을 순차적으로 방문해 0인 경우 방문 체크를 진행한다.

2. 0 이후 처음 만나는 1마다 발전기를 설치한다.

3. 1을 방문하면 재귀적으로 상하좌우에서 1으로 연결된 집들을 모두 차례로 방문해 방문 체크를 진행한다.

4. 마지막 총 설치한 발전기의 수를 출력한다.

결과 1

• Runtime Error

재귀를 사용한 경우 런타임 에러가 발생한 경우는 Stack Overflow인 경우가 많다. 재귀가 아닌 다른 방법을 사용해보기로 한다.

풀이 전략 2

1. 각 칸을 순차적으로 방문해 0인 경우 방문 체크를 진행한다.

2. 0 이후 처음 만나는 1마다 발전기를 설치한다.

3. 1을 방문하면 그 칸을 기준으로 상하좌우 방문 여부를 체크한다.

4. 방문 체크를 한 후 방문한 위치를 Stack에 담아서 위의 3번을 반복한다.

교훈

겨우 풀었다. 4시간 반이나 걸렸다. Runtime Error에서 바로 재귀 외의 방법을 찾았어야 했다.

재귀에서 Runtime Error가 발생하면 다른 방법을 빠르게 찾아보자.

결과

구르미의 상의와 책가방을 겟했다.

12일차 미션성공

12일차 미션 블록

Day13 발전기 (2)

발전기 문제를 응요한 문제이다.

문제 분석

N x N 격자의 모든 칸에는 숫자(마을)이 담겨 있다. 상하좌우로 연결 된 같은 숫자의 마을의 수가 K보다 클 경우 하나의 단지라고 한다. 단지의 수가 많은 마을의 숫자를 출력해야 한다. 단지의 수가 같을 경우에는 마을의 숫자가 큰 숫자를 출력한다.

풀이 전략

1. 모든 격자를 순차적으로 방문해 해당 칸의 숫자와 같은 수를 가진 마을이 상하좌우에 있는지 찾아다닌다.

2. 수가 같은 마을을 방문했을 땐 방문 했음을 체크해 놓는다.

3. 위의 1과 2를 하나의 방문이라고 할 때, 방문이 끝날 때마다 방문한 마을의 수가 K보다 큰지를 확인해 해당 숫자의 단지수를 늘려준다.

4. 모든 격자를 방문한 뒤 단지수의 최대값을 찾아서 최대 단지수의 마을 숫자를 출력한다. 만약 최대값이 여러개라면 마을의 숫자가 큰 것을 출력한다.

결과

어제와 비슷한 문제였다. 전체 로직은 빠르게 작성할 수 있었는데 어제도 문제를 일으켰던 배열이 또 문제를 일으켜 3시간이나 걸렸다. 이 문제는 멘토링을 한 번 받아본 다음 결과를 업데이트 하도록 하겠다.

결과적으로 구르미에게 에너지드링크인지, 베터린지 모를 번개모양 아이템을 손에 쥐어주게 됐다.

13일차 미션 성공

13일차 미션 블록