[코드트리 조별과제] 6주차 레포트

코드트리 방학 과제 마지막 주다.
한 달 좀 넘는 기간이 순식간에 지나버렸다.
이번 주는 현생 이슈로 마지막 주임에도 불구하고 문제를 거의 풀지 못했다.
아쉬운데로 급하게 쉬운 dp 한 문제, 좋아하는 dfs 한 문제씩 풀이 했다.

생각보다 별로 풀이하지 못해 아쉬운 마음이 크고, 또 이런 좋은 기회가 오면 좋겠다.

(애플워치 받으면 좋겠다)

> 문제 풀이

# dfs

📝  마을 구분하기 - https://www.codetree.ai/missions/2/problems/seperate-village/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제

정답률 72% 제출 1,841회 예상 소요 시간 36분

n * n크기의 이차원 영역에 사람 혹은 벽이 놓여져있습니다. 이 때 상하좌우의 인접한 영역에 있는 사람들은 같은 마을에 있는 것으로 간주한다고 합니다. 예를 들어 <그림 1> 같이 사람과 벽이 배치되어 있는 경우, 그림 안의 점선과 같이 마을을 나눌 수 있습니다. 이 때 총 마을의 개수와 같은 마을에 있는 사람의 수를 오름차순으로 정렬하여 출력하는 코드를 작성해보세요.

입력 예제

5
1 0 1 1 1
1 0 0 0 0
0 0 0 1 1
1 1 0 1 1
1 1 0 1 1

출력 예제

4
2
3
4
6

코멘트

- 오랜만에 dfs였다.
- 사실 이 문제는 dfs던 bfs던 차이가 없다.
- 모든 탐색 문제가 그렇지만 방문체크가 중요하다.
- 사람(1)인 경우 dfs 탐색을 시행하며 개수를 세어감과 동시에 벽(0)으로 만들어 방문체크를 했다.

# dfs

📝 최대 점프 횟수 - https://www.codetree.ai/missions/2/problems/maximum-number-of-jumps/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제

정답률 51% 제출 644회 예상 소요 시간 25분

각 위치로부터의 최대 점프 가능 거리를 의미하는 n개의 수가 주어졌을 때, 첫 번째 위치로부터 최대 몇 번 점프를 할 수 있는지를 구하는 프로그램을 작성해보세요. 단, 동일한 위치로 점프하는 것은 불가능하고 앞으로 점프하는 것만 가능합니다.

입력 예제

5
2 3 0 1 4

출력 예제

3

제출 결과

코멘트

- 현재 돌 기준으로 현재 돌까지 도달 가능한 이전 돌들 중에서 가장 많이 점프를 거친 돌에 1을 더하는 방식으로 해결했다.
- 만약 모두 체크했는데 0 즉, 현재 돌로 도달할 방법이 없는 경우에는 이후 돌들 또한 무조건 도달 불가하기 때문에 그만두면 된다.
- 돌들중에서 가장 많은 점프 횟수를 출력하면 된다.