+ 추가 문제

[Taehyeon-Kim]

solved.ac-class2-e

• boj1181 단어 정렬 (multiple sorting)

solved.ac-class5-e

• boj2467 용액
  • 이전에는 많이 어려워했던 것 같은데 15분 이내에 풀 수 있었다.
  • 투포인터가 떠올라서 적용했고, 쉽게 풀 수 있는 문제였다.

[Taehyeon-Kim]

DP Basic

• 재귀도 연습해봐야하는데 개인적으로 for문 이용한 bottom-up 방식이 쉬운 것 같다.
• Swift로 푸는 경우에는 index of bounds를 주의하도록 하자. (파이썬으로 풀때는 신경안쓰고 넘어갔던 부분인데 Swift 까다롭네)

연습문제

규칙이 어떻게 찾아지는지 살펴보자

• 1로 만들기
• 2xn 타일링
• 1, 2, 3 더하기

BOJ 2839 설탕 배달***

문제 나쁘지 않은 것 같다.

• 그리디하게 풀 수도 있고, DP로도 풀 수 있음
• 둘 다 떠올랐는데, 그리디보다 DP가 더 명확하게 그려져서 DP로 품
• 아까 재귀에 대해 공부했더니 귀납적인 접근이 살짝이나마 떠올랐다.

• K가 5로 나누어 떨어진다면, K-5 역시 나누어 떨어지고 d[k] = d[k-5] + 1로 만들 수 있다.
• K가 3로 나누어 떨어진다면, K-3 역시 나누어 떨어지고 d[k] = d[k-3] + 1로 만들 수 있다.
• 바로 나누어떨어지는 경우가 아니라면 3, 5 뺀 수가 나누어 떨어지는 상황인지 파악하고 최솟값을 구한다.

// d[k] -> d[k-3] + 1 or d[k-5] + 1
let n = Int(readLine()!)!
var d = Array(repeating: -1, count: 5001)

d[3] = 1; d[5] = 1

if n >= 6 {
  for i in 6...n {
    if i % 5 == 0 { d[i] = d[i-5] + 1 }
    else if i % 3 == 0 { d[i] = d[i-3] + 1 }
    else if d[i-3] > 0 && d[i-5] > 0 {
      d[i] = min(d[i-3], d[i-5]) + 1
    }
  }  
}

print(d[n])

BOJ 1149 RGB거리

• dp 문제

[Taehyeon-Kim]

Recursion

BOJ 1629 곱셈

import Foundation
let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
let a = line[0], b = line[1], c = line[2]

func pow(_ a: Int, _ b: Int, _ c: Int) -> Int {
    if b == 1 { return a % c }
    
    var val = pow(a, b/2, c)
    val = val * val % c
    if b % 2 == 0 { return val }
    return a * val % c
}

print(pow(a, b, c))

귀납적 사고

• 1승(제곱)을 계산할 수 있다.
• K승을 계산할 수 있다. => 2K승을 계산할 수 있다. => 2K+1승을 계산할 수 있다.

[Taehyeon-Kim]

Math

BOJ 9421 소수상근수

• 소수 관련 문제 풀어보기

BOJ 1715 카드 정렬하기

• Heap Queue 문제