2017년 12월 15일 [삽질의 시간]

어떤 아이디어를 가지고 어플리케이션 A를 만들기 시작하면 낭비되는 시간 중의 20%는 완전히 삽질에 쓰이게 된다.

 

가령 어떤 회사의 클라우드 서비스를 신청해서 모든 세팅을 마쳤는데 다른 회사의 서비스로 옮겨가야 하는 경우에 필요한 패키지를 다시 설치하는 것이다. Anaconda를 설치하고 Environment를 로드하면 이 문제에서 시간을 획기적으로 단축할 수 있는데 이 글을 쓰는 시점에서야 기억이 났다는 것이 문제다. 제대로 설치되지 않은 패키지가 전체를 망쳐버려서 오도가도 못하는 상황이 그렇고, 방화벽 설정을 했는데도 여전히 연결을 받아주지 않는 서버를 들여다보는 일도 그렇다.

 

다른 20%는 추상적인 설계로 인해서 지금까지 해 온 작업을 롤백하고 다시 돌아가는 것이다. 제대로 설계를 해놓지 않으면 프로그래밍 과정에 그 때 그 때 방향을 설정하게 되는데, 시간이 지나서 이미 짠 코드가 길어진 후에 이것이 큰 어둠의 빛을 발한다. 경험상 이 과정이 제대로 되지 않으면 절대로 프로그램은 완성되지 않는다. 계속해서 제자리를 맴돌다 지쳐버려 개발 의욕 자체가 사라지기 때문이다.

 

다른 20%는 모르는 것에 대한 삽질에 쓰인다. Android Studio를 배우거나, 새로운 라이브러리를 배우거나 익숙지 않게 리눅스를 쓰고 Python을 쓰면서 한글이 깨지는 문제 등에 대해서 삽질을 하다보면 배우는 것이 많다고 느낄 수도 있지만 정리해두지 않으면 그냥 삽질의 시간으로 지나간다.

 

이런 부차적인 작업이 끝나고 난 다음에 실제 개발에 소요되는 시간은 얼마 되지 않는 것 같다. 어플리케이션의 전체 설계와 구체적으로 필요한 클래스와 함수명, 데이터베이스의 구조가 모두 짜여져있고, 모든 API들에 대한 실행 권한과 부가적인 세팅작업이 모두 끝난 상황에서는 말 그대로 코딩만 하면 되기 때문이다. 이미 어플리케이션은 프로그램으로만 짜이지 않아서 그렇지 거의 완성되어 있다. 이 작업이 40%를 차지하는 것도 아니다. 20%의 시간은 테스팅과 최적화에 쓰인다. 20% 정도의 시간이 코딩 이외의 시간으로 쓰이는 것이다.

 

훌륭한 개발자가 무엇인지는 모르겠지만 이런 부차적인 시간을 줄일 수 있는 사람이 아닐까 싶다.

내공이 있다는 것은 왠만한 지식은 갖추고 있으며, 설계 단계부터 최적화와 성능을 고려하고, 불필요한 일들을 굳이 하지 않는다는 것이 아닐까 싶다.

2017년 12월 14일 [비]

일주일 전 정도에는 비가 왔다.

날씨가 더 추웠다면 아마 눈이 내렸을 것이다.

그 때는 웹툰인 목욕의 신을 보면서 밖에 잠깐 나간 것이었는데 많지도 않게 적당히 내리는 비를 맞으며 서 있는 것이 참 기분이 괜찮았다. 대게들 우울할 때 비를 맞으면 비참하다고 하는데, 그렇지 않을 때 적당히 비를 맞는 것은 오히려 괜찮아보인다.

이런 비는 한 동안 맞아도 흠뻑 젖지 않아 오래 맞을 수 있어 좋고, 비를 맞은 후에 세탁기에 옷을 돌려놓고 바로 목욕을 할 수 있다면 더할 나위 없지 않을까 하는 생각이 들었다.

만약 목욕탕 중에서 가운데에 큰 목욕탕을 만들고, 그 주변을 입자가속기처럼 둥글게 에워싸고 항상 비가 내리도록 만들어 사람들이 고요히 비를 맞으며 걷고 난 후 목욕을 할 수 있도록 한다면 정말 좋은 목욕탕이 될 것 같다.

모든 일은 순탄하게 흘러가고 있다. 적당히 나쁠 일 조차도 없으며, 의도한 대로만 움직인다면 정해진 미래로 나아갈 수 있는 삶을 살고 있다. 한시적인 일이긴 하지만 지금이 매우 좋으며 지금의 상태를 유지하기 위해서 기한 내에 만들기로 한 것을 끝내야겠다는 생각을 한다.

2017년 12월 4일 월요일 [새로운 디데이]

2016년에 설정했던 디데이는 실패로 끝났다.

무언가 제대로 이룬 것이 없게 그냥 시간을 흘러 보낸 것이다.

내년을 다시 바라보기에는 이제는 남은 시간이 없다. 기껏해야 최대한 시간을 미룰 수 있다면, 내년 3월이 끝나는 시점이 될 것이다. 따라서 새로운 디데이는 오늘 기점으로 118일이 되었다. 이 기한이 마지막이고 이것마저 지난다면 그 때는 새로운 결정을 할 수밖에 없다.

오늘 오전에는 해야 할 것들을 끝내놓고, 다시 뭔가를 만들기 위해서 자리에 앉아있다. 네트워킹은 어려운 일처럼 보인다. 실시간 스트리밍 데이터는 더욱 그렇다. 오늘도 만 걸음은 걸어야 한다.

Codeforces educational round 32

I. Introduction

이 포스트에서는 codeforces.com 에서 진행된 Educational Round 32에 대해서 살펴봅니다.

 

II. Solve

[Prob A] – Local Extrema

배열 a가 있다. 이 배열의 원소 a_i 은 자신의 양 옆의 값보다 작으면 (a_i < a_{i-1} \; and \;   a_i  < a_{i+1}) local minimum이라 불린다. 또한 자신의 양 옆의 값보다 크면 local maximum이라 불린다. local minimum이거나 local maximum인 원소를 local extremum이라 한다. local extremum의 원소의 수를 구하여라.

 

문제 풀이

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

( 2 <= i <= n-1 ) 의 반복문을 수행하며 양 옆의 원소와 비교해 조건에 해당하는 것을 카운팅하면 끝이다.

 

코드


 

[Prob B] – Buggy Robot

Ivan은 무한한 평면 그리드에 놓인 로봇을 가지고 있다. 초기 로봇의 위치는 (0,0)이고 다음과 같은 명령에 따라 움직인다.

  • U – (x, y)에서 (x, y + 1)로 이동
  • D – (x, y)에서 (x, y – 1)로 이동
  • L – (x, y)에서 (x – 1, y)로 이동
  • R – (x, y)에서 (x + 1, y)로 이동

Ivan은 n개의 command를 연속으로 입력했고 로봇은 이에 따라 움직여 최종적으로 (0, 0)에서 멈추었다. Ivan은 입력한 command가 정확한지 궁금했다. 그는 어떤 command를 로봇이 무시했다고 생각했다. 로봇에 버그가 존재하는지 알기 위해, 그는 제대로 동작한 command의 최대 갯수를 알고 싶어한다. 이 수를 구하여라.

 

문제 풀이

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

(0, 0)에서 (0, 0)으로 다시 돌아오기 위한 command 쌍의 가장 간단한 형태는 L + R 또는 U + D이다. 이들의 순서는 상관없기 때문에 command를 하나씩 살피면서 갯수를 합쳐 준 다음에 최종 커맨드 수에서 이 쌍의 수만 골라내면 올바른 command의 최대 수를 알 수 있다.

 

코드


 

[Prob C] – K-Dominant Character

알파벳 소문자로 이루어진 문자열 s가 있다. 문자 c는 문자열 s의 부분 문자열 중 최소 k의 길이가 되는 것 중 c를 포함하는 부분 문자열이 존재할 때 k-dominant라고 한다. 예를 들어서 abacaba에서는 k = 2로 설정하면 어떤 경우에도 항상 a는 포함되는 것을 알 수 있다.

최소한 하나의 k-dominant가 존재하는 최소의 k를 출력하여라.

 

문제 풀이

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

어떤 문자 c가 등장하고 그 다음으로 문자 c가 등장하기까지의 간격 중 최대의 간격을 배열에 저장한다. 예를 들어 위의 abacaba에서는 A[‘a’] = 2, A[‘b’] = 4, A[‘c’] = infinite 이다. 문자의 첫 등장은 이전 등장이 없고 마지막 등장은 다음 등장이 없기 때문에 각각 문자열의 시작과 끝을 기준으로 최대 간격을 비교해주어야 한다.

이 배열의 값 중 최소의 값과 (문자열의 길이 / 2) + 1 중 작은 것이 답이다. 모든 문자가 하나씩만 등장하는 경우에는 문자열의 중앙에 있는 문자가 항상 포함되는 부분문자열의 길이를 k로 택하면 되는데 이것이 (문자열의 길이 / 2) + 1이기 때문이다.

 

코드


 

[Prob D] – Almost Identity Permutations

크기 n을 갖는 순열 p는 1부터 n까지의 수가 한 번씩만 등장하는 배열이다.

이 순열 중에서 p_i = i 인 원소가 최소한 n-k개 존재한다면 이것을 almost identity permutation이라 부른다.

n과 k가 주어질 때 almost permutation의 수를 구하시오.

 

문제 풀이

주어진 문제에서 ( 1 <= k <= 4 ) 이므로, 문제를 약간 변형해서 p_i \ne i 인 원소가 최대 k개인 경우를 찾으면 된다.

임의의 m개의 원소가 p_i \ne i 일 때 이들은 서로의 자리를 교환하여 조건을 만족한다. 이외의 n-m개의 원소들은 모두 자신의 자리에 그대로 있기 때문이다. 이 경우의 수를 f(m)이라고 하면, f(0) = 1, f(1) = 0, f(2) = 1,  f(3) = 2, f(4) = 9이다.

정답은 \sum_{m=0}^k {f(k) * {n \choose k}} 이다.

 

코드


 

[Prob E] – Maximum Subsequence

n개의 정수로 이루어진 수열 a가 있다. m이 주어질 때, 임의의 인덱스 수열 b를 (1 \le b_1 \le b_2 \le ... \le b_k \le n ) 을 만족하게 구성하였을 때 \sum_{i = 1}^k{ a_{b_i} mod m } 의 가능한 최댓값을 구하여라.

(1 \le n \le 35 , 1 \le m \le 10^9 ) 이다.

 

문제 풀이

문제에서 주어진 n의 크기에서 힌트를 얻어야 한다. n은 최대가 35이므로, 절반으로 나누면 18, 17이 된다.

즉, 이 절반들에 대해서 각각 가능한 모든 조합을 수행하여 나머지 값을 구한다. 앞의 절반을 배열 A, 나머지를 B에 담는다고 할 때 두 배열을 모두 정렬시키고 모든 A값에 대해서 가장 최대의 Mod M을 만들 수 있는 B를 이분검색을 통해 찾아낼 수 있다.

2^18 = 262,144 이므로 시간이 그렇게 많이 걸리지도 않는다.

배열 A의 각 원소에 대해서 알맞은 B를 찾기 위한 탐색을 시작한다. 가능한 나머지의 최댓값은 M – 1이므로, 정렬되어 있는 B에서 찾아야 할 것은 A[i]에 대해 M – 1 – A[i]와 같거나 작은 것 중 최대 값의 인덱스다.

이 인덱스를 j라고 할 때 A[i] + B[j] 또는 A[i] + B[len(B) – 1] 중 가장 큰 것이 A[i]에 속한 원소들을 택했을 때 가능한 최대의 결과다. 모든 i에 대해 반복문을 수행하여 그 중 최대를 가지는 것을 출력하면 된다. 시간복잡도는 O(n * 2^(n/2 – 1))이다.

 

코드


 

[Prob F] – Connecting Vertics

평면에 n개의 점이 있으며, 이들은 정다각형을 이루고 있다. 여기에서 당신은 n-1개의 선분을 그릴 수 있는데, 각각은 두 개의 정점을 잇는다. 이러한 방법으로 이 점들은 모든 쌍이 직접적으로 연결되거나 간적접으로 연결된다.

그러나 여기에 제한사항이 주어진다. 첫 째로 어떤 점들은 직접적으로 연결될 수 없으며 오로지 간적접으로만 이어져야한다. 둘째로, 당신이 그리는 선분은 정점을 제외하고는 어떤 교차점도 서로 가질 수 없다. n-1개의 선분으로 정점을 모두 연결하는 경우의 수를 구하여라. 수가 클 경우에는 10^9 + 7 로 나눈 나머지를 출력하여라.

입력으로는 정점의 수와 행렬정보가 주어진다.

정점의 수 N은 ( 3 \le N \le 500 ) 이며, 행렬 a_{i, j} = 1 이면 두 점은 직접적으로 연결될 수 있다.

 

문제 풀이

다이나믹 프로그래밍으로 해결하는 문제다.

DP[i][j]를 i와 j가 이미 연결되어 있을 때 i와 j 사이에 존재하는 정점들을 i 또는 j에 연결하는 경우의 수라고 하자. 이렇게 DP를 설정하면 i와 j 사이의 정점이 (i, j) 구간 바깥의 점에 연결된 경우를 없앨 수 있다.

DP[i][j]를 구하는 방법에 대하여 알아보자. 만약 i-번째 정점을 x번째 정점에 연결하려 한다고 하자. (i, j)구간의 정점을 모두 연결상태로 만들기 위해서는 (i, j) 사이에 존재하는 모든 점들은 i 또는 x에 연결되어 있어야 한다. (x, j)구간의 정점들은 어떠한가. 이 점들은 x, j 또는 i와 연결되어 있어야 한다. 여기서 (x, j)구간의 점들과 i의 연결을 다루기 힘들다.

이것을 간단히 하기 위해서 x를 i와 직접적으로 연결한 모든 점 중 가장 인덱스가 큰 것으로 고르고, 반대로 어떤 것을 j와 연결할 때는 직접적으로 연결한 모든 점 중 가장 인덱스가 작은 것으로 고른다. 이렇게 되면 이 인덱스를 기점으로 i에 가까운 것은 j와 직접적으로 연결될 수 없고, j에 가까운 것은 i와 직접적으로 연결될 수 없다.

프로그래밍 대회를 위한 알고리즘 [1] – Tarjan’s Algorithm

본 포스팅은 geeksforgeeks의 http://www.geeksforgeeks.org/tarjan-algorithm-find-strongly-connected-components/ 를 통해 제작된 것입니다.

 

알고리즘 설명

Tarjan’s Algorithm은 그래프에서 Strongly Connected Component (SCC)를 찾아내기 위한 알고리즘이다. 여기에서 SCC란 유향간선(양방향 통로가 아닌 단방향 통로)으로 구성된 그래프 중에서도 모든 정점 쌍 사이에 경로가 존재하는 그래프를 말한다. 예를 들어 아래의 그래프에서는 그림과 같이 3개의 SCC가 존재한다.

Tarjan’s algorithm은 다음과 같은 사실들에 근거한다.

  1. DFS 탐색은 DFS 트리를 만들어낸다.
  2. SCC는 DFS의 subtree를 구성한다.
  3. 만약 그러한 subtree의 head를 찾을 수 있다면, 해당 subtree의 모든 노드를 출력할 수 있다.
  4. 하나의 SCC로부터 다른 SCC로 돌아가는 back edge는 존재하지 않는다. (서로 다른 SCC는 사이클을 이루지 않는다는 말인 듯.)

 

SCC의 head를 찾기 위해서 disc와 low 배열을 사용한다. disc[u]는 탐색에서 u를 방문한 시간이며, low[u]는 u를 root로 한 subtree에서 도달할 수 있는 가장 일찍 방문된 정점의 방문 시간을 의미한다.

즉, 어떤 SCC의 head란 disc[u] == low[u]인 노드를 의미한다. SCC에 속한 다른 노드의 경우 disc[u] > low[u]이다.

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

  • 그래프 G에서 아직 방문하지 않은 노드 u를 하나 선택한다.
    • 노드 u를 Stack에 집어 넣는다.
    • dist[u] = 현재 노드를 방문하는 시간, low[u] = dist[u]
    • u로부터 이동가능한 SCC에 속하지 않은 노드 v를 탐색한다.
      • 만약 방문하지 않은 노드라면 해당 노드로 DFS를 호출한 후에 low[u] = min(low[u], low[v]) 이다.
      • 만약 이미 방문한 노드라면 low[u] = min(low[u], disc[v])이다.
    • 탐색 종료 후 disc[u] = low[u]이면
      • 노드 u는 SCC의 Head이다.
      • Stack에서 u까지를 pop하여 SCC를 구성한다.

이 알고리즘은 모든 노드를 모든 엣지를 통해서 단 한번만 방문하기 때문에 O(V + E)의 시간 복잡도를 갖는다.

 

코드 (원본 : geeksforgeeks)

 

 

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월까지는 시간이 있으며 그 전까지는 단기간의 진로에 대해서는 준비가 되어 있어야 할 것이다. 그리고 그 기간에 내가 무엇을 하였는지의 기록도 반드시 필요하다.

Atcoder Regular Contest 085

I. Introduction

이 포스트에서는 Atcoder.jp 에서 진행된 Regular Contest 085에 대해서 살펴봅니다.

 

II. Solve

[Prob C] – HSI

Takahashi는 현재 프로그래밍 대회에 참가 중이다. 그는 N개의 문제 중에서 M개의 문제를 각각 1900초 만에 1/2의 확률로 해결할 수 있고, 나머지 (N-M)개의 문제를 각각 100초만에 완전히 해결할 수 있다.

그가 대회를 진행하는 과정은 코드를 제출하고, 모든 테스트 케이스를 통과하지 못하면 통과할 때까지 다시 코드를 제출하는 것이다.  N과 M이 주어질 때 Takahashi가 이 문제를 통과하기 위해 걸리는 시간의 기대값을 구하여라.

 

문제 풀이

기본적인 무한 급수 문제이다. 문제의 수가 M개일 때 이 문제를 모두 맞출 수 있는 확률은 {( {1\over 2} )}^M 이다. 이 확률을 r 이라고 한다면, 총 시간의 기댓값

S = \sum_{k=1}^{\infty} {k * (M * 1900 + (N - M) + 100) * (1 - r)^{ k-1 } * r}

= r * (M * 1800 + 100 * N) * \sum_{k=1}^{\infty} {k * (1-r)^{ k-1 }} 이다.

 

S - (1 - r)S =  r * (M * 1800 + 100 * N) * \sum_{k=1}^{\infty} {(1-r)^{ k-1 }}

rS = r * (M * 1800 + 100 * N) * {1 \over {1 - (1 - r)}} 이므로

S = (M * 1800 + 100 * N) * {1 \over r}

을 출력하면 된다.

 

사용 알고리즘

  • 무한 급수

 

코드

 

[Prob D] – HSI

N개의 카드로 이루어진 덱이 있다. 각각의 카드에는 양의 정수 값이 적혀 있다.

두 명의 사람 X와 Y는 이 카드를 가지고 플레이한다. 가장 처음에 X와 Y는 하나의 카드를 들고 게임을 시작하며 각각 들고 있는 숫자는 Z와 W이다. 매 턴마다 플레이어는 현재 들고 있는 카드를 버리고 덱에서 최소 1장에서 원하는 숫자만큼의 카드를 위에서부터 뽑아 가장 마지막으로 뽑은 카드를 손에 쥔다.

모든 카드가 소진되면 게임은 종료되며 이 때 두 플레이어가 들고 있는 카드의 숫자 차이의 절댓값이 게임의 스코어가 된다. X의 목표는 스코어를 최대화하는 것이고, Y의 목표는 스코어를 최소화하는 것이다. 두 플레이어가 최적의 방식을 따른다고 할 때 게임의 스코어를 구하여라.

 

문제 풀이

선을 쥐고 있는 것이 X이므로 X의 입장에서 생각해보자.

  • X가 첫 턴에서 모든 카드를 다 뽑아버린다면 게임 스코어는 | D_n - W | 이다.
  • X가 첫 턴에서 하나의 카드만 남겨버린다면 게임 스코어는 | D_{n-1} - D_n | 이다.
  • X가 첫 턴에서 하나 이상의 카드를 남긴다면 위의 두 경우보다 큰 차이를 낼 수 있기 때문이다. 이 경우 Y는 이런 시나리오를 피하기 위해서 하나의 카드만 남겨버릴 수 있다. 이 경우 게임 스코어는 두 번째 경우와 동일한 | D_{n-1} - D_n | 이다.

따라서 게임은 X의 선택에 따라서 결정되는 것과 같으며 두 값 중 최댓값을 출력하면 끝이다.

 

사용 알고리즘

  • 게임이론