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

> 코딩 공부

# 그리디

📝 수 채우기 - https://www.codetree.ai/missions/8/problems/fill-in-number/description

문제

정답률 48% · 제출 405회 · 예상 소요 시간 21분

주어진 금액을 2원과 5원 동전을 이용해서 합 n 을 만들려고 합니다.
사용하는 동전의 총 개수를 최소로 하려고 할 때, 총 몇 개가 필요한지를 구하는 프로그램을 작성하세요.

 
입력 예제

14

 
 
출력 예제

4

 
제출 결과

 
코멘트
- 비교적 쉬운 문제였다.
- 먼저 큰 단위인 5원으로 채울 수 있는만큼 채워야한다.
- 여기서 포인트는 채울 수 있는 숫자임에도 불구하고 5원으로 인해 남은 금액이 홀수가 되어 2원으로 채우지 못하는 경우가 존재한다.
- 위에서 말한 경우는 잘 생각해보면 5원을 채우고 남은 금액이 '어떠 한 경우 하나'만 존재한다.
 
 

# DP

📝 연속 부분 합의 최댓값 구하기 - https://www.codetree.ai/missions/2/problems/max-of-partial-sum/description

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

문제

정답률 59% · 제출 1,321회 · 예상 소요 시간 25분


n개의 정수가 입력으로 주어지고, 이 중 연속한 부분 수열에 속한 원소들의 합이 최대가 될 때의 값을 출력하는 코드를 작성해보세요. (단, 부분 수열은 최소 한 개 이상의 원소를 포함합니다.)

 
 
입력 예제

7
4 -1 2 -19 3 6 9

 
출력 예제

18

 
제출 결과

 
코멘트
- 이번 문제의 포인트는 음수 값이 가능하다는 것이다.
- 단순하게 현재 값이 음수라 합이 작아진다고 해서 중간에 끊게 되면 뒤에 오는 값을 더했을 때 최대값이 나오는 경우에 걸리게 된다. (3, 4,  -1, 5)
- 이전 연속 값에 현재 값을 더한 값과 현재 값을 비교했을 때 현재 값이 더 크다면 이전 연속 값을 유지할 필요가 없어진다.
 
 

📝 계단 오르기 2 - https://www.codetree.ai/missions/2/problems/climbing-stairs-2/description

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

문제

정답률 40% · 제출 296회 · 예상 소요 시간 측정 불가

남우는 n층 높이의 계단을 오르려고 합니다. 남우는 계단을 오를 때 한 번에 정확히 1계단 혹은 2계단 단위로만 올라갈 수 있습니다.
계단의 각 층에는 동전들이 떨어져 있습니다. 만약 남우가 해당 층을 밟고 지나가면, 아주 빠르게 해당 층에 있는 동전을 쓸어갈 수 있습니다.
남우는 빠르게 계단을 올라가고 싶기 때문에, 1계단 오르는 것을 좋아하지 않습니다. 따라서 이 행동은 최대 3번만 하고자 합니다.
조건에 맞춰서 남우가 계단을 n층까지 올라가고자 할 때, 올라가면서 얻을 수 있는 동전의 최대 개수를 구하는 프로그램을 작성하세요.
단, 2계단 단위로 올라갈 경우 n층까지 정확히 1계단이 남은 상황에서는 n층으로 올라가지 못함에 유의합니다.

 
입력 예제

4
1 2 3 4

 
출력 예제

9

 
제출 결과

코멘트
- 주의 깊게 살펴봐야 할 부분은 최대 3번의 특이 행동인 1칸을 오르는 행동이 존재한다는 것이다.
- 1칸을 오른 횟수를 기준으로 생각해본다면, 현재 상태를 [지금까지 0번, 지금까지 1번, 지금까지 2번, 지금까지 3번]으로 나눌 수 있다는 것이다.
- 또한 현재 층수에 도달하기 위한 방법이 두 가지가 존재한다.
      1. '현재층 - 1번째'층에서 한 칸 오르기
      2. '현재층 - 2번째'층에서 두 칸 오르기
- 그렇다면 x번 1칸 오른 상태에서 현재 위치한 계단 층수에서의 최대값은
      1. '현재층 - 1번째'층에서 x-1번만 1칸을 오른 상태의 최대값
      2. '현재층 - 2번째'층에서 x번만 1칸을 오른 상태의 최대값
   둘을 비교하여 더 큰 값에 현재 층수 값을 더한 값으로 생각할 수 있다.