220216.md

지난 과제 리뷰

• 백준 9251 LCS

  • Problem: LCS(Longest Common Subsequence, 최장 공통 부분 수열) 구하는 문제
  • Solution: DP를 사용해 모두의 부분 수열이 되는 경우 카운트를 더해 나아감
    • 문자열 s1과 s1의 모든 문자를 순회하면서
    • s1[i]==s2[j]일 경우, dp[i][j] = dp[i-1][j-1] + 1
    • s1[i]!=s2[j]일 경우, dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    • LCS2 문제처럼 LCS 수열 자체를 출력하고 싶을 경우 카운트 대신 현재 문자를 추가하면 됨!
  • Code: 기탁 성범 수진

• 백준 15686 치킨 배달

  • Problem: 치킨집이 최대 M개가 있을 때, 도시의 치킨 거리(집과 가장 가까운 치킨집 사이의 거리)의 최솟값을 출력하는 문제
  • Solution: 문제의 조건에 따라 구현해 최솟값을 출력하면 됨
    • 집과 치킨집의 위치 인덱스 저장
    • 치킨집을 중복과 순서 없이 M개 뽑았을 때의 모든 경우를 순회하면서 → 조합
    • 각각의 집에 대해 치킨 거리의 최솟값 계산
  • Code: 기탁 성범 수진

• 백준 15685 드래곤 커브

  • Problem: 드래곤 커브를 구현했을 때 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력하는 문제
  • Solution: 드래곤 커브가 생성되는 규칙에 따라 좌표에 점을 찍어 나아감
  • 규칙: 전 세대 드래곤 커브 방향의 순서를 뒤집은 후 각 방향(d)에 (d+1)%4 적용
    • ex) 0세대 드래곤 커브의 방향이 0일 경우,
    • 1세대 드래곤 커브의 방향: (0) 1
    • 2세대 드래곤 커브의 방향: (0 1) 2 1
    • 3세대 드래곤 커브의 방향: (0 1 2 1) 2 3 2 1
  • Code: 기탁 성범 수진