이성주

현재를 즐기며 미래를 만드는 개발자, 이성주입니다.

1. 대회 후기

CODE TREE (https://www.codetree.ai/)

이전에 식목일 기념 코딩 퀴즈 이후로 두 번째 코딩 퀴즈가 열렸다. 이번 코딩 퀴즈는 어버이날 기념이었다. 휴대폰으로 참여 링크 문자가 와서 이에 대해 알 수 있었다.

7일 퀴즈 당일은 일이 있어서 아쉽게도 참여하지 못했고, 8일에 문제를 모의시험을 통해 풀어보았다.

문제는 1번부터 7번까지 있었는데, 7번을 제외하고 6문제를 시간 안에 풀어내었다. 마지막 문제를 제외하곤 무난한 난이도였던 것 같다.

정답 코드

2. 문제 풀이 및 후기

A. 효도의 시작

엄마 아빠 사랑해요!

한글이라 깃헙 링크를 타고 들어간 코드는 깨져 보인다.

B. 위험한 효도

특별한 방법이 없는 살짝 복잡한 구현 문제였다. 거리 $d$를 초과하면 $d$에 도달한 것으로 처리하는 것과, 처음 지점($0$) 미만이면 $0$에 도달한 것으로 처리하는 작업이 중요했다.

C. 진정한 효도

브루트포스로 모든 경우에 대해서 최솟값을 구하면 된다.

D. 함께하는 효도

상당히 까다롭고 시간이 오래 걸렸던 브루트포스 구현 문제였다. 친구 세 명이 각각 상하좌우 세 번을 움직이는 총 $64$가지 행동 중 하나씩 선택하는 방식을 구현해야 했다.

깔끔한 방법이 생각나지 않아서, 미리 모든 행동을 배열에 저장해놓고 친구 세 명이 그 중에 어떤 행동을 선택하도록 삼중 for문을 돌렸다. 친구가 두 명인 경우, 한 명인 경우도, 중복 케이스가 많이 발생하지만 삼중 for문 하나로 한 번에 처리 가능하다.

E. 효도 음식

최근에 백준 대회에서 비슷한 문제 [BOJ 25049] 뮤직 플레이리스트를 풀어보아서 쉽게 풀어냈다.

위 문제와 마찬가지로, 기준점을 정해서 왼쪽과 오른쪽의 최대 부분합 maximum dp를 구하고, 모든 기준점에서의 maximum 값을 구하면 된다.

F. 효도 여행

트리 탐색과 동시에 LCS를 구현해야 하는 문제이다.

LCS는 한 문자열$B$를 기준으로 다른 문자열$A$의 글자 하나하나마다 dp 값을 갱신해 나간다. 따라서 트리를 탐색하며 만나는 간선의 문자마다 dp 값을 그때그때 갱신해 줄 수 있다. LCS 코드 구조는 다음과 같다.

for (int i = 0; i < A.size(); i++) {
  for (int j = 0; j < B.size(); j++) {
    if (A[i] == B[j]) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
    }
    else if (A[i] != B[j]) {
      dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
    }
  }
}

한 문자마다 한 줄의 dp 값이 이전 줄의 dp 값에 의해 변경되므로, 두 줄의 dp 값만 가지고도 값을 계속 변경시키는데 충분하다. 재귀를 다시 나올때 초기화를 위해 임시 vector도 하나 필요하다.

모든 leaf node에서의 maximum dp 값이 정답이 된다.

댓글남기기