2017년 11월 27일 월요일 [D – 4]

 

퇴근을 한 후에는 항상 피곤하다. 요즘에는 낮잠을 자도 많은 꿈을 꾼다. 점심 늦게 일어나 뭔가 먹으려다가 여자친구와 이른 저녁에 약속이 있어 그만두고 블로그 정리를 했다. WordPress에서는 LaTeX와 Markdown을 가능하도록 만드는 플러그인들이 있어서, 이전 블로그 보다는 깔끔하게 표현이 기능해서 좋다. Google Cloud에 서버를 두고 아예 설치해서 WordPress를 쓰는 것이라 이전에 웹 호스팅 버전보다는 훨씬 유연하게 쓸 수 있는 것 같다.

 

하루에 만 걸음 정도라도 꾸준히 걷기 위해서 노력하고 있는데, 오늘은 저녁을 많이 먹어서 한 2시간 정도를 여자친구와 함께 걸어서 만 걸음을 채웠다. 사용하고 있는 어플리케이션은 그 정확도가 상당히 이상한데 어떤 경우에는 많이 걸어도 카운팅이 적게 되고 어떤 경우는 적게 걸어도 카운팅이 많이 된다. 가속도계 값이나 Google Fitness 둘 중 하나를 쓰는 것 같은데 내 생각에는 단순히 흔들리는 정도로만 판단해서 큰 동작없이 천천히 걸었던 걸음들은 제대로 기록하지 못하는 것 같다. 반면에 농구를 하거나 운전을 하거나 가속도 변화가 큰 상황에서는 매우 크게 증가해버린다. 이걸 삭제하고 내일부터는 다른 앱을 써봐야겠다.

 

정리를 하는 것은 나쁘지 않은 일이다. 다만 실제 학습이나 풀이 기간과 포스팅 기간에는 차이를 좀 두는게 좋겠다. 풀이 후에 즉시 포스팅을 해버리면 빠르게 정리는 되지만 복습이 전혀 되지 않아 기억에 남질 않는다. 오늘 한 일이라고는 대회 문제 복습과 운동 뿐이다. 그래도 어떤 형태로든 운동은 꾸준히 할 생각이다.

 

오늘 요약

  • 대회 풀이 정리 : 3시간
  • 운동 (걷기) : 2시간

CodeChef November Challenge 2017 (1)

I. Introduction

이 포스트에서는 CodeChef.com 에서 진행된 November Challenge에 대해서 살펴봅니다.

여기에서는 앞선 5개의 문제를 살펴보고 추후 포스팅에서 나머지 5개의 문제를 다를 예정입니다.

  • 문제 수 : 10개
  • 진행 시간 : 10일
  • 레이팅 구간 : 전체
  • 대회 링크 : https://www.codechef.com/NOV17

 

II. Solve

[Prob A] – Villages and Tribes (VILTRIBE)

문제 링크 : https://www.codechef.com/NOV17/problems/VILTRIBE

n개의 마을이 있다. 여기에는 A와 B의 두 부족이 있는데, 마을은 비어있거나 이 두 부족 중 하나에게 점령되어 있다. 비어있는 마을은 A 부족에게 좌우로 둘러싸여져 있다면 A 부족의 지배를 받고, B부족에게 좌우로 둘러싸여져 있다면 B부족의 지배를 받는다.

A와 B 부족에게 점령당하거나 지배를 받는 마을의 수를 각각 구하여라.

 

문제 풀이

O(n)의 시간 복잡도로 해결할 수 있다.

Prev라는 변수는 가장 최근에 지나친 점령된 마을을 지배하는 부족이라고 하자. 새로운 점령된 마을을 발견했을 때 Prev와 동일한 부족이라면 Prev와 현재 사이의 모든 마을은 해당 부족에게 점령당했다고 볼 수 있다. 이 방식은 부족이 A와 B가 아닌 여럿일 경우에도 동일하게 사용될 수 있다.

 

사용 알고리즘

  • 없음

 

코드


 

[Prob B] – Chef goes Left Right Left (CLRL)

문제 링크 : https://www.codechef.com/NOV17/problems/CLRL

Chef는 현재 Reziba를 추적하려고 한다. 하지만 그가 알고 있는 것은 사람들의 각기 다른 CodeXP rating 뿐이다. Reziba는 현재 Expo에 있으므로 Chef는 Reziba의 rating을 통해 Expo에 있는 사람들로부터 Reziba를 찾아내려고 한다.

하지만 Chef는 Reziba의 rating을 모른다. 대신 Expo에 있는 나머지 모든 사람들이 Reziba의 rating을 알고 있다. 따라서 Chef는 다음과 같은 방법으로 Reziba를 찾아내기로 한다.

Expo의 사람들은 현재 rating의 오름차순으로 일렬로 정렬되어 있다. 맨 처음 Chef는 임의의 어떤 사람에게 질문을 하고, 그는 자신의 rating이 Reziba보다 높고 작음에 따라 Reziba가 자신을 기준으로 왼쪽에 있거나 오른쪽에 있다고 응답한다. 그러면 Chef는 응답받은 방향으로 어느 정도 이동한 후 다시 멈춰서 그 자리에 있는 사람에게 질문을 계속해나간다. 여기서 제약이 존재한다. Chef는 이동 시에 동일한 지점을 두 번 방문할 수 없다. 최종적으로 Chef는 Reziba의 앞에서 이동을 종료한다.

이 수색 과정에서 Chef는 자신에게 응답한 사람들의 rating을 응답 순서대로 기록했다. 이 기록의 마지막은 Reziba의 것이다. Chef는 기록이 틀리지 않았는지 알고 싶어한다. 이를 출력하여라.

 

문제 풀이

상한과 하한을 계속해서 낮춰가면서 범위를 좁히는 탐색이다. 입력에서는 Reziba의 rating이 주어졌으므로 기록을 통해 사람들이 left, right 중 무엇으로 답했는지 알 수 있다.

(l, r)의 rating 사이에 Reziba가 존재한다고 가정하자. 초기의 l과 r은 각각 0과 infinite이다. rating이 R_i 인 사람이 right라고 답했으면 l = R_i 이 된다. 반대로 left라고 말했으면 r = R_i 이다. 응답자들은 모두 현재의 범위 내의 rating을 가지고 있어야 한다. 그렇지 않다는 것은 Chef가 l 또는 r의 값을 가진 사람을 두 번 지나쳤다는 것이기 때문이다.

따라서 과정은 매우 간단하다.

  • 현재 응답자가 (l, r)의 범위 내에 있는지 판별한다.
  • 범위 내에 있으면 Reziba의 rating과 비교하여 응답을 알아낸 후 응답에 따라 l 또는 r을 응답자의 rating으로 패치한다.

 

사용 알고리즘

  • 상한 하한

 

코드


 

[Prob C] – Periodic Palindrome Construction (PERPALIN)

문제 링크 : https://www.codechef.com/NOV17/problems/PERPALIN

Chef는 최근 문자열의 주기성에 대해 배웠다. 길이 N인 문자열은 P \mid N 인 P가 존재하며, 길이 P인 문자열이 N / P 번 반복되는 문자를 말한다. 예를 들어 문자열 “abab”는 2와 4의 주기를 갖는다.

Chef는 펠린드롬이면서 동시에 P의 주기를 갖는 문자열을 만들고 싶어한다. 문자열은 ‘a’와 ‘b’로만 구성된다. 단, Chef는 둘 중 하나의 문자로만 구성된 문자는 싫어한다. N이 반드시 P의 배수로 주어진다고 할 때 그러한 펠린드롬 문자열을 구할 수 있다면 예시를 하나 출력하고, 그렇지 않으면 ‘impossible’을 출력하라.

 

문제 풀이

우선 P가 1인 경우를 살펴보면 Chef가 싫어하는 문자열이다.

P가 2인 경우를 살펴보면 가능한 문자열이 ‘ab’나 ‘ba’ 연속인데 펠린드롬을 만들 수가 없다.

P가 3이 이상인 경우를 살펴보면 ‘aba’나 ‘abba’와 같은 P를 만들 수 있다. P가 그 자체로 펠린드롬이므로 P를 몇 개를 이어 붙이더라도 펠린드롬이 된다.

따라서 P가 1 또는 2인 경우에는 ‘impossible’이며, 이외의 경우에는 길이 P의 abbb….bbba를 (N / P)개 출력하면 된다.

 

사용 알고리즘

  • 펠린드롬의 성질

 

코드


 

[Prob D] – Chef Hates Palindromes (CHEFHPAL)

문제 링크 : https://www.codechef.com/NOV17/problems/CHEFHPAL

Fehc는 Chef에게 길이 N인 문자열을 선물로 주려고 한다.

Chef가 펠린드롬을 싫어하기 때문에 Fehc는 문자열에서 뽑을 수 있는 펠린드롬을 이루는 부분문자열의 최대길이가 가능한 짧기를 바란다. 문자열은 A개의 문자만 사용할 수 있다. 예를 들어 A = 3이면 ‘a’,’b’,’c’만 문자로 사용가능하다. 만들어야 할 문자열의 길이 N과 사용 가능한 문자의 수 A가 주어질 때 만들 수 있는 문자를 출력하여라.

문제 풀이

이 문제는 생각이 아닌 관찰로 푸는 문제다. 브루트포싱으로 풀기 때문이다.

A의 크기에 따라 경우를 나누어본다.

  • A = 1인 경우 단순히 N의 길이의 ‘aaaa….aaaa’를 출력하면 된다.
  • A > 2인 경우 단순히 ‘abcabcabc…’ 형태로 N의 길이만큼 출력하면 된다.
  • A = 2인 경우만 해결하면 되는데 이걸 좀 심각하게 생각해야 한다.

N = 15 길이로 만들 수 있는 모든 문자들을 최대 펠린드롬 길이로 정렬해보면 패턴을 찾을 수 있다.

일단 최대 펠린드롬의 길이가 N = 8부터는 4로 유지된다는 점과, ‘aabb abaa bbab’가 반복되는 문자열이 존재한다는 것이다. 즉, 이것만 반복시키면 최대 펠린드롬의 길이는 4이상으로 늘어나지 않는다. N이 8이하인 경우까지는 문자의 길이가 매우 작기 때문에 단순히 모든 경우를 발생시켜 조사한 후 최소를 출력해도 된다. 내 경우에는 다른 방식으로 풀던 코드가 쓸모없게 되면서 그냥 재활용 차원에서 남겨두었는데 가장 깔끔한 방식은 그냥 배열에 1 <= N <= 8인 경우까지는 예시를 미리 저장했다가 출력하는 것이다.

문제가 안 풀릴때는 N의 크기를 줄이면서 관찰하는 것이 필요하다는 것을 알려주는 것 같지만 매우 짜증난다.

 

사용 알고리즘

  • 브루트포스

코드


 

[Prob E] – Chef and Intersection Line (CHEFNIL)

문제 링크 : https://www.codechef.com/problems/CHEFNIL

Chef는 A[M][N][N]의 3차원 행렬을 가지고 M초 동안 게임을 진행한다. 1 <= k <= M 에 해당하는 각 k초마다 Chef는 (i, j)의 쌍을 하나 골라 A[k][i][j]의 점수를 얻는다.

또한 그녀는 2차원 평면을 가지고 있는데, k = 2일 때부터 그녀는 평면에 k-1초에 골랐던 (i, j)와 k초에 고른 (i, j)를 잇는 선분을 그린다. 게임의 룰은 이 선분이 교차하지 않으면서 최대의 점수를 얻는 것이다. 물론 그녀가 선분을 그리는 방식에 의해서 직전에 그렸던 선분과 현재 그린 선분이 가지는 하나의 교점은 교차로 취급하지 않는다.

k = 1초부터 그녀가 선택한 (i, j)쌍을 한 줄씩 출력하여라.

그녀가 꼭 M초동안 게임을 진행할 필요는 없다. 게임 도중에 그만두고 싶으면 -1 -1을 출력한다.

 

문제 풀이

이 풀이는 1.0점 만점에서 0.61점을 받았기 때문에 61% 정도의 답안의 역할만 한다.

M의 크기 제한이 500, N이 50으로 주어지기 때문에 탐색 자체만으로도 계산량이 적지 않은 수준이다.

게임에서는 반드시 축과 수평하게 이동할 필요가 없기 때문에 어떤 선분이라도 두 점을 이을 수만 있고, 교차하지 않는다면 그릴 수 있다. 하지만 그것까지 고려할 방법은 생각하지 못했기 때문에 나는 진행경로를 DP를 쓰기에 가장 좋은 방식으로 설정하고, 정해진 경로에서 최적의 해를 구하는 방식을 쓰기로 했다.

설정한 경로은 (1,1)을 행렬의 최상단, 좌측으로 잡고 행이 홀수일 때는 오른쪽으로 이동하고, 짝수일 때는 왼쪽으로 이동하는 아래 그림과 같은 방식이다.

즉, D[k][i][j]는 그 이전 단계로 가능한 D[k-1][i][j] 중에서 가장 최적인 것을 골라 자신의 해에 추가한다.

아래로의 이동을 위해서는 반드시 행의 좌우측 끝을 선택해야만 하기 때문에 주어진 경로를 완전히 자유롭게 사용할 수 없다. 이것을 약간 보완하기 위해서 행의 좌우측에서는 직전 행에서만 값을 가져오는 것이 아니라 앞선 모든 행에서 가장 최적인 것을 가져오는 방식을 선택했다.

알고리즘은 다음과 같이 동작한다.

  • D[0][i][j]는 입력된 값 A[0][i][j]로 우선 채운다. (해당 지점에서 시작하는 경우)
  • i는 1부터 M – 1까지 반복
    • j는 모든 행을 순차적으로 방문한다.
      • i가 홀수 행이면 진행방향이 오른쪽이므로 자신의 왼쪽에 있는 것 중 최적해를 찾고 그 위치를 기록
      • i가 짝수 행이면 진행방향이 왼쪽이므로 자신의 오른쪽에 있는 것 중 최적해를 찾고 그 위치를 기록
      • 행의 양 끝에서는 위 작업에 추가해서 같은 열의 이전 행들 중에서 최적해를 찾고 그 위치를 기록
    • 현재 D[i][j][k] 중에서 가장 큰 값을 찾아서 i와 j와 k를 기록한다.
  • 반복문 종료 후 최대 i와 j와 k로부터 역추적으로 지나온 경로를 저장하여, 순차적으로 출력한다.
  • 최대 i가 M-1이 아니면 중간에 그만 둔 것이므로 -1, -1을 출력한다.

 

사용 알고리즘

  • 다이나믹 프로그래밍

코드


 

2017년 11월 26일 [D – 5]

아마도 작년 5월 쯤에 교육원에서 세팅한 디데이는 이제 5일이 남았다.

그 많던 날들이 5일까지 줄어드는 동안 세상도 변하고 참 많은 것들이 변했다.

알고리즘 실력은 전과 큰 차이가 없다고 생각했지만 가끔 KOI 문제를 풀어보면 이전보다는 많이 발전했다는 것을 느낀다.  물론 내 레이팅을 바꿔놓을 정도로 큰 차이는 아니다. 복습 할 알고리즘도 많고, 더 풀 문제들도 많다. 그나마 다행인 것은 프로그래머의 채용 방식이 프로그래밍 대회 형태로 바뀌고 있다는 점이다.

세상의 변화는 훨씬 빠르다. 10년 정도 남았다고 생각했던 기술들은 훨씬 더 빠르게 등장하고 있다. 이것이 가져올 사회의 변화는 알 수 없다. 하지만 초기 산업 혁명이 사람들의 우려와 달리 새로운 시대를 열었던 것처럼, 다시 새로운 시대가 열릴 수도 있는 일이다. 새로운 시대와 환경에서, 그 환경에 적합한 사람들이 새로운 기회를 잡을 수 있을지도 모른다.

하지만 그 미래를 알 수 없는 현재에서는 매우 불안할 따름이다.

확실한 것은 내가 가진 선택지들 중에서 안정적인 것은 아무것도 없다는 것 뿐이다. 그렇기에 내가 할 수 있는 일이란 더 좋은 선택지들을 위해 노력하는 것 뿐이다. 지난 시간들에서 아쉬운 점은 지나온 하루하루들에서 내가 무엇을 했는지 아무런 기억도 나지 않는다는 것이다.

여기에서의 일이 끝나는 시점은 내년 5월이다. 아마도 3월까지는 시간이 있으며 그 전까지는 단기간의 진로에 대해서는 준비가 되어 있어야 할 것이다. 그리고 그 기간에 내가 무엇을 하였는지의 기록도 반드시 필요하다.