BOJ 1254 팰린드롬 만들기

어떤 문자열이 주어지면 그 문자열 뒤에 0개 이상의 문자를 추가해서 팰린드롬을 만들되, 가능하면 짧게 만들어야하는 문제이다. 가장 짧은 팰린드롬의 길이를 출력하는 문제인데,

일단 문자열 뒤에 문자를 추가할 때는 문자열을 구성하는 문자 중 가장 앞의 문자부터 추가해야 한다. 왜냐하면 팰린드롬이려면 0번째와 n-1번째, 1번째와 n-2번째, ... 이렇게 앞 뒤 문자가 같아야 되는데, 주어진 문자열 자체로 팰린드롬이 아니고 최소 개수의 문자를 추가해서 팰린드롬을 만들어야 한다면 ...
abcd가 있다고 하자. 그럼 일단 a부터 붙여본다. abcda 하지만 b와 d가 달라서 실패.
그 다음에는 뭘 붙여봐야할까? 바로 ba를 붙여본다. 그래도 아니면 그 다음에는? cba..
물론, abcd를 거꾸로 한 dcba를 붙이면 당연히 팰린드롬이 되겠지만 이 문제에서는 최소 길이를 구해야 하므로 이렇게 작은 경우부터 붙여보면서 이게 팰린드롬인지 아닌지 검사해보는 방법이 있다. 이 문제에서는 n이 작기 때문에 n가지 경우의 문자열을 만들고 일일이 팰린드롬인지 아닌지 검사하면 O(N*2N)  즉, O(N^2)에 될 것이다.

=>*** 이 방법으로 구현하고, 고수님들의 코드를 봤는데... 굳이 저렇게 모든 경우를 만들어 볼 필요가 없다!! 뒤에 붙여서 팰린드롬이 되려면, 원래 문자열에서 그 붙이는 만큼의 prefix를 제외한 나머지 문자열이 팰린드롬이 되어야 한다! 그렇기 때문에 원래 문자열의 suffix를 검사해보면서 팰린드롬이 되면 원래 문자열에서 그 suffix만큼의 길이를 빼준 만큼만 뒤에 덧 붙여주면 된다는 것이다....!! 아... 엄청난 것 같다. 이렇게 간단하다니... 이 방법으로도 풀어서 제출해야 겠다.

또 한가지 방법은 JM book 문자열 부분에 나온 방법인데, 어떤 문자열S가 있으면 그 문자열을 뒤집은 RS를 만든 후, S의 suffix와 RS의 prefix를 비교해서 공통이면서 가장 긴 부분을 찾는다. 즉 S의 뒷부분과 RS의 앞부분이 최대한 겹치면 그 것이 가장 짧은 팰린드롬이 된다. 그렇기 때문에 kmp를 이용해서 겹치는 부분의 최대 길이를 구하고 그 값을 원래 문자열의 길이에서 뺀 만큼만 원래 문자열에 추가해주면 최소 길이를 구할 수 있다.
아무래도 이 방법은 O(N)만에 될 것 같다.

위의 3가지 방법으로 모두 AC를 받았다.

BOJ 1509 팰린드롬 분할

주어진 문자열을 팰린드롬인 문자열 여러개로 분할하는데, 분할되는 문자열의 최대 개수는 문자 하나 하나씩으로 분할할 때 나올 것이다. 하지만 이 문제에서는 최소 개수를 구해야 한다.

d[n]=n번째 문자부터 시작해서 문자열을 묶어보고 분할할 때, 팰린드롬 분할의 최소 개수
d[n] = min(m은 한 묶음이 되는 문자열의 길이 1에서 N-n까지... | d[n+m]+1)
이렇게 하면 O(N^2)의 시간복잡도가 나오는...게 아니라 각 묶음에 대해서 팰린드롬인지 검사해야 하므로 O(N)만에 검사하면 O(N^3)이 나오게 될 것이다. 시간초과다. 그럼 dp를 이용하면 팰린드롬인지 판단하는데 처음에 O(N^2)만큼 걸리고 그 이후로는 O(1)만에 팰린드롬인지 판단 가능하므로 결국 O(N^2+N^2)의 시간복잡도를 가지게 될 것이다.

구현해 봐야겠다. AC를 받았다.

BOJ 11047 동전 0

n종류의 동전을 최소(개수)로 이용해서 k원을 만들어야 하는데, 이 문제에서 주어지는 n종류의 동전은 1원부터 시작해서 Ai원은 Ai-1원의 배수인 경우가 주어진다.
즉, 주어지는 n종류의 동전은 오름차순으로 나열되어 있고, X원의 동전은 X원 이하의 모든 동전의 배수가 된다.
보통 동전 문제는 다이나믹 프로그래밍으로 푸는 걸로 알고 있는데, 이 문제의 경우 X원의 동전은 X원 이하의 모든 동전의 배수이므로 가능한 동전 주 무조건 가치가 큰 동전을 우선적으로 써야한다. 그리디 문제이다.
가치가 큰 동전부터 우선적으로 써야하는 것을 명확하게 증명은 못하겠지만, 생각해보면 배수가 아닌 경우에는 5원*3= 15원 , 12원*1+1원*3= 15원.. 이런 예에서 볼 수 있듯이, 가치가 큰 동전을 우선적으로 썼을 때, 더 개수가 많이 필요한 경우가 있다. 하지만 이렇게 배수들로 주어지는 경우에는 일단 같은 수를 여러번 쓸 바에야 그 배수를 쓰는 것이 훨씬 이익인데, 이 것만으로는 완벽히 증명이 힘들다.
  최소 배인 2배만 한다고 해도, 1원부터 시작할 경우 1, 2, 4, 8, 16, 32, 64, 128,... 어떤 수에 대해서 그 수의 앞의 수들을 다 합쳐서 어떤 수보다 작다. 만약 3배, 4배를 한다면 더 큰 차이가 날 것이다.
어떤 수에 대해서 그 수의 앞의 수들을 다 합쳐도 그 수보다 작기 때문에 가장 큰 수를 우선적으로 이용하는 것이 개수를 줄이는 데 좋을 것이다.

하지만... 그래도 완벽히는 증명은 못하겠다. 일단 직관적으로는 90퍼센트 확실한 것 같은데... 일단 풀어봐야 겠다. 나중에 더 공부하고 다시 생각해보자.

BOJ 2259 두더지 잡기

좌표상에서 두더지가 어떤 시간 T에 어떤 좌표에 출몰하는데, 1초당 S만큼 이동할 수 있는 두더지 사냥꾼이 좌표(0, 0)에서 출발해서 최대 몇 마리의 두더지를 잡을 수 있는지 구하는 문제이다.
모든 경우를 다 해봐야할 것 같다. 하지만 그러면 너무 경우가 많으니 dp로 풀어야 한다.
d[x][y] = (x, y)의 두더지를 잡으면서 시작할 때, 잡을 수 있는 두더지의 최대 마리수
로 하면... 문제가... (x, y)이전에 어떤 두더지를 잡으면서 왔냐에 따라 d[x][y]가 영향받기 때문에... 그럼 시간도 넣어야 하나? d[x][y][T] = (시간 T에 (x, y)를... 아 ... 다시 생각해보자.
일단 (x, y)의 두더지를 잡으려면 그 두더지가 출몰하는 시간 T에만 잡을 수 있다. 즉, (x, y)의 두더지를 잡은 후에는 시간 T이후에 출몰하는 두더지들만 잡을 수 있는 것이다.
그러니까 아까 고민했던 (x, y)이전에 어떤 두더지를 잡으면서 왔냐에 따라 d[x][y]가 영향을 받는다는 것은, (x, y)이전에 어떤 두더지를 잡으면서 왔냐에 따라 앞으로 잡을 수 있는 두더지가 변할 수 있다는 것이었는데, 두더지는 무조건 시간 T! 딱 그 순간에만 잡을 수 있으므로 (x, y)의 두더지가 출몰하는 시간 T이전에는 시간 T이후의 두더지를 잡을 수 없다.
그러니까... 나는 시간 T이하?로 착각했던 것 같다. 그러므로 그냥 d[x][y]로 해도 될 것이다.
하지만 이럴 경우 x, y값이 최대 1000이므로 두더지는 최대 6666마리이므로 시간복잡도상으로 O(1000*1000*6666)..가 나올 수 있어보이는데... 음 (x, y)는 좌표고 결국 이 좌표는 6666개 있으므로 즉 두더지는 최대 6666마리이므로 각 좌표마다 번호를 부여해서
d[x] = x번 두더지를 잡으면서 시작할 때, 잡을 수 있는 두더지의 최대 마리수
로 놓으면 될 것 같다.
d[x] = max(nextX는 xT이후에 시간 안에 도달 가능한 곳만.. | d[nextX]+1) 이 될 것 같은데,
아예 미리 시간 T기준으로 정렬을 해놓으면 편할 것 같다.

조금 까다롭다고 생각되는 부분이 어떤 좌표에서 어떤 좌표로 이동할 때, 실수만큼의 시간이 걸린다는 것인데 일단 실수 계산으로 인한 오차가 영향을 줄 정도의 데이터 개수는 아닌 것 같으니... 그냥 double형으로 놓고 해보려고 한다.

구현해보자. AC를 받았다.
고수님들의 코드를 보니 대부분 for문으로 구현하신 것 같고,
일단 두 좌표간의 거리를 계산하는 부분에서 대각선 거리이므로 피타고라스의 정리를 이용하고 제곱과 sqrt연산이 필요해서 코드가 길어지는데, 이 부분에서 곱셈 연산을 함수로 만들어서 코드를 좀 간단하게 한 방법도 있었고, 시간을 구해 비교하기 위해 거리를 속도로 나눠주는데 나눌 필요없이 상대편 시간과 속도를 곱해서 거리를 만들어서 비교해도 된다. 나눗셈이 더 느리단 말을 얼핏 들은 거 같은데 찾아보니 나눗셈 연산이 곱셈보다 더 느린 것 같다. 그러니까 저렇게 나눗셈 대신 곱셈을 쓰는 것이 더 나아보인다.
그리고 sqrt를 쓰지 않고 곱셈한 값으로만 비교한 경우도 있었는데, 이 방법은 좀 더 생각을 해봐야겠지만 좋아보인다.(시간도 시간이지만...int를 double로 형변환할 필요도 없어서 오차 없이 정확할 것 같다. 아 그 대신 long long이 필요하거나 더 커질 수도 있겠지만...)
곱셈한 값으로만 비교해서 하니 시간도 좀 줄었고, 확실히 정확해서 좋을 것 같다.

문제를 풀다보니 약간... 경찰차 문제와 비슷한 느낌을 받았다.

Algospot Jaeha’s Safe 계속 틀린 이유...아...

이 문제는 분명 입력으로 들어오는 스트링의 제한이 10000이하라고 되어있고, 계산시 배열을 2배하는 것이 필요해서 배열의 크기를 20001로 잡고 했는데 오답이 나서 40001로 잡고 제출했더니 맞는 것이었다. 그래서 20001에서 40001까지 올려가면서 해봤는데, 계속 오답이다가 40000에서 런타임 에러까지...음 그리고 내가 코드에 들어오는 데이터의 길이가 10000보다 크면 무한 루프가 실행되게 해두었는데도 실행이 안된 것을 보면 데이터에는 문제가 없다. 결국 계속 오답이다가 40000에서  런타임 에러를 받고 나서 조금 느낌이 왔다. 정말 40000까지 접근하는 것 같았고, 도대체 어디서? 고민하다가 알게 되었다.

나는 char 배열을 str1, str2 두 개만 사용하는데, 그래서 문제가 생긴 것이다. 예를 들어 str2를 2배하면 str1을 입력받고, str2를 또 2배하게 된다. (내 코드에서..) 결국 str2를 2배해준 후 그대로 놔두기 때문에 이런일이 발생하는 것이다. 해결책으로는 그냥 str1을 사용했으면 '\0'(NULL)을 2배하기 전의 위치에 넣어주면 될 것이다.

고쳐서 AC를 받았다. 정말 감사하면서 열심히 해야겠다. 이번 실수는 어떻게 찾았는지 믿기지 않는다. 정말 찾기도 힘들었고, 길이를 40001로 설정하면 맞으니 그냥 데이터 문제인가 보다 혹은 귀찮아서라도 그냥 넘어갈 수 있었는데, 다행이다 이렇게 알게되니 기분 좋다.

BOJ 13423 Three Dots

나에겐 매우 어려운 문제였다. 결국 나는 생각하지 못했고, 풀이를 보고 풀었다.

나는 그냥 O(N^3)짜리 코드를 짰는데, for문 형태만 N^3이고, 사실은 N^2일 것이라고 단단히 착각하고 있었다... 계속해서 TLE를 받고 풀이를 보기 전까지...

풀이를 다시 보고 풀고 생각해보니 시간 복잡도 계산이 그리 간단치 않아서
직접 계산해봤다.

대충 계산을 해보면,
(n-1)*(n-2) + (n-2)*(n-3) + (n-3)*(n-4) + .... + 2*1 이렇게 될 것인데,
이것은 SUM(k=1 ~ n, (n-k)*(n-(k+1)) ) 이 될 것이다. 시그마를 써서 표현하면 더 알아보기 쉬울텐데, 일단은 이렇게 쓰겠다.
식으로 풀어써서 계산을 해보면 (맞는진 모르겠지만..) (n^3 - 3*n^2 + 2*n)/3 이 나온다.
즉 O(N^3)으로 볼 수 있다.

이거 계산하면서 느낀 것이... 일단 매우 오래 걸렸고, 수학 공부 좀 할껄... 아니 이제와서 후회해봤자 소용없으니, 앞으로 수학 공부좀 하자라는 생각이 들었다. 공부하자. 알고리즘 잘하려면 수학적 센스도 필요하고 수학적 개념이 많이 필요한 것 같다.

자, 이제 다시 문제로 돌아와서 저렇게 O(N^3)으로 구현하면 시간초과가 난다.
그래서 일단 앞의 두 개의 수 a, b만 먼저 찾고(일단 중복 방지를 위해 sorting이 되어 있다.) 세번째 수c는 b+(b-a)가 있는지를 해싱이나, 이분 탐색으로 탐색해서 존재하면 count해주는 식으로 하면 O(N^2 logN)이 된다.

난 map을 써서 배열의 수를 다 저장해두고, 이분탐색 대신 map.count를 이용해서 그 수가 존재하는지 확인하는 방법을 사용했는데, 또 시간초과가 났다.
map도 binary tree로 구현되어 있어서 map.count하면 binary search와 비슷할 것 같은데...음... 일단 이 부분은 나중에 찾아보기로 하고 map.find를 써봤는데, 역시 시간초과이다.
물론 내가 사용법을 잘 몰라서 잘못 썼을 가능성도 있다.

일단은 좀 힘과 의욕이 많이 떨어진 상태라 더 안 찾아보고 이분 탐색으로 구현했더니 AC를 받았다.
그리고 고수분들의 코드를 확인하고 O(N^2)의 방법을 알 수 있었다.

O(N^2)의 방법은 다음과 같다.
일단 모든 수를 가운데 수b를 먼저 정한다. 그리고 배열의 양 끝에서 각각 a, c의 후보가 되는 수들을 차례 차례 본다.
그러면서 b-a > c-b 이면 aIdx++, b-a==c-b인 경우 count, b-a < c-b 이면 cIdx--.
이렇게 구하면 가운데 수 b에 대해서 N번씩 보면 되므로 O(N^2)이다. 멋지다.

오늘은 정말 내가 엄청 못한다는 것과 여태 좀 한다는 착각에 단단히 빠져있었다는 것을 깨달았다.

참고 : 국민대학교 교내 대회 풀이 슬라이드

BOJ 13421 국민 랜드

입력으로 4개의 좌표가 주어지면 그 4개의 좌표를 옮겨서
각 변이 x축 또는 y축에 평행하고, 두 대각선의 교점이 (0, 0)이되는 정사각형을 최소비용으로 만들어야 한다. 이 때, 최소비용으로 만들 수 있는 정사각형 중에서 가장 큰 정사각형을 만들어야 하고 그 정사각형의 한 변의 길이를 출력하는 문제이다.

각 좌표를 옮길 때 드는 비용은 |Xold - Xnew| + |Yold - Ynew| 이다.
그리고 입력으로 들어오는 좌표의 범위는 -10억 ~ 10억이다.

이 것을 모든 정사각형에 대해 입력으로 주어진 4개의 좌표와 비교해서 직접 계산해보면서 최소비용으로 만들 수 있는 것 중 가장 큰 것을 찾으면 시간초과가 분명해진다.

그렇다고 이분탐색을 쓰자니...  기준 값도 마땅치 않고... 기준 값에 대해 크냐 작냐에 따라, 차이가 커지는지, 적어지는지에 대한 것이 명확하지 않은 것 같다.
국민대 풀이 슬라이드가 있지만 지금 당장 보기보다는 나중에 다시 생각해보자.