구름톤 챌린지 | 4주차 학습일기 [16일차 / 17일차 / 18일차]

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

4주차 학습일기

Day16 연합

문제 분석

N개의 섬이 있고 M개의 마을 연결 정보가 있다. 연결은 단방향이고 양쪽에서 서로 연결돼 있을 경우 하나의 연합이 된다. 모든 연결 정보를 분석해 연합의 수를 출력하면 된다.

풀이 전략

1. N x N 배열을 이용해 M개의 연결 정보를 기록하고, N의 길이의 배열에 최상단 노드의 정보(부모노드)를 기록한다. (처음엔 자기 자신을 가리킨다.)

2. N x N 배열에서 (i, j), (j, i) 요소가 모두 true인 경우가 양방향 연결 된 상태이다. 이 때 연합을 시도한다.

3-1. find함수를 정의해 부모노드의 정보를 불러온다.

3-2. 불러온 두 노드의 부모가 일치한 경우 연합하지 않는다.

3-3. 불러온 두 노드의 부모가 다른 경우 연합시켜주며 둘 중 부모노드의 크기가 작은 것으로 부모노드 정보를 갱신해준다.

4. 위의 2, 3 단계를 N x N 배열의 모든 요소에 대해서 시행한다.

5. 부모노드 정보를 갖고 있는 배열에서 존재하는 부모의 수를 세 출력해준다.

결과

그래프 탐색이 익숙하지 않아 10시에 시작한 풀이가 오후 5시가 돼서 끝났다.

16일차 미션 성공

16일차 미션 블록

Day17 통신망 분석

문제 분석

N개의 노드가 주어지고 M개의 연결 정보(간선)이 주어진다. 연결은 언제나 양방향이고 연결된 노드들의 모임을 컴포넌트라한다. 하나의 컴포넌트에 노드 대비 간선의 수를 간선밀도라 한다. 간선밀도가 높은 컴포넌트의 노드들을 작은순으로 출력하는 문제이다.

풀이 전략

1. N 길이의 ArrayList<Integer> 배열을 정의 한 뒤, M개의 연결 정보를 넣어준다. 그런 다음 효율적인 탐색을 위해 각 배열의 리스트를 정렬해 준다.

2. 모든 노드에 대해서 DFS를 시작한다. 하나의 노드에 방문하면 a) 방문 체크를 하고 b) 방문한 노드의 수를 늘려준 뒤 c) 임시 배열에 현재 노드를 추가해준다. d) 그런 뒤 연결 된 노드에 방문여부를 모두 체크해 방문 되지 않은 노드의 수를 간선수로 더해준다.

3. 위의 2번 단계를 방문이 멈출 때 까지 진행해 준 뒤 현재 컴포넌트의 간선 밀도를 계산해 현재까지 계산 된 최대 간선 밀도값과 비교한다. 클 경우 갱신해 줌과 동시에 임시 배열에 저장해 놓은 노드 리스트를 최대 밀도 컴포넌트 리스트를 갱신해 준다.

4. 위의 2, 3번 단계가 마무리 되면 모든 노드에 대한 탐색을 마치고 최종적으로 갱신 돼 있는 최대 밀도 컴포넌트 리스트를 출력해 준다.

결과

Day16을 풀면서 그래프에 대해 많이 익숙해 져서 Day17은 2시간 만에 풀 수 있었다.

17일차 미션 성공

17일차 미션 블록

Day18 중첩 점

문제 분석

N x N 격자안에 M개의 선을 그을 것이다. 주어진 점에서 시작해 오른쪽, 왼쪽, 위, 아래 중 한 곳으로 반직선을 긋는다. 모든 선을 그은 후 그은 선들의 교차점의 수를 구하는 문제이다.

결과

구르미에게 구름 컵을 들고 있게 해줬다. 이건 좀 갖고 싶게 생긴 컵이다. 오버플로우 해결하는 것 외에는 로직이 계획했던게 그대로 맞았다. 계획했던 로직이 딱 들어맞는게 기분이 상당히 좋다. 문제가 안풀려서 6시간이나 골머리를 앓아도 보니, 더이상 그러고 싶지 않아서 문제 풀기 전에 풀이전략을 짜보기 시작했다. 미리 코드 전략을 짜고 코드 작성을 시작하는 이런 습관을 갖게 된 것이 현재까지 구름톤 챌린지에서 얻은 가장큰 성취물이 아닐까 생각한다.

18일차 결과

18일차 미션 블록