1695 - 팰린드롬 만들기

처음에 그리디적으로 접근했는데, 이게 발상의 시초였다.

팰린드롬을 만들 때, 좌우 한쪽을 기준으로 잡고, 양쪽이 다르면 반대쪽에 "그 문자"를 추가한다고 생각해보았다. 예를 들면,

abaacd 라면 가장 왼쪽 a와 잡고 가장 오른쪽은 d를 비교한다. 이 때 문자가 서로 다르므로 오른쪽에 a를 추가하여 abaacda 를 만든다고 생각한다. a는 이제 추가했으므로 b를 잡고 다시 d를 비교한다. 다르므로 다시 추가하면 abaacdba 가 될 것이다.

이 행동을 반복하면

abaacdaba

abaacdaaba

abaacdcaaba

abaacdcaaba

하지만 위 방법은 너무 그리디적이여서 만약 번갈아서 추가해야하는 상황이 생기면 틀리게 된다.

생각을 살짝 바꾼다면, L번째와 R번째를 비교하는 함수를 p(L, R) 이라 하자.
p(L, R) 에서 나올 수 있는 경우는 3가지이다.

1. L과 R이 같은 경우

2-1. L과 R이 다를 때, p(L+1, R)에서 답이 나오는 경우 + 1 (여기서 1은 한쪽이 다르므로 문자를 추가한 비용)

2-2. L과 R이 다를 때, p(L, R-1)에서 답이 나오는 경우 + 1

우리는 이제 그리디적인 2-1 과 2-2 에 대해 유연하게 대처할 수 있게 되었다.

중복되는 연산이 굉장히 많으므로 [L][R]과 같이 저장해서 중복연산을 피하면 되겠다.

2004 - 조합

nCm 에 대해서 오른쪽부터 0의 개수를 출력하는 문제이다.

nCm = (n! / m!) / (n-m)! 이다. 여기서 m≤n≤2,000,000,000 인데 각각 팩토리얼을 계산한다면 절대 구할 수 없을 것이다. (오버플로우나 시간복잡도 등..)

이 문제 이전에 일반적인 nCm 을 구하는 문제부터 짚어보자.
오버플로우를 피해서 nCm을 구하는 것이라면 각 팩토리얼을 모두 계산 후에 나누는 게 아니라 분자(2 * 3 *... * n-m+1) 와 분모(2 * ... * m) 을 구성하는 각 숫자를 하나씩 계산하는건데

12C5 를 예로 들자면 12! 을 계산 후에 5! 7! 으로 나누는게 아니라 아래와 같이 진행한다.
12C5는 아래와 같이 나타낼 수 있다.
( 12 * 11 * 10 * 9 * 8 ) / ( 5 * 4 * 3 * 2 * 1 )
위 식은 다시말해 (12/5) * (11/4) * (10/3) * (9/2) * (8/3) 을 따로 한 것과 같은 결과이다.

그럼 0의 개수는 어떻게 구할까?
0의 개수를 구하는 문제는 보통 숫자를 소인수분해해서 2의 지수갯수와 5의 지수갯수 중 더 작은 만큼이 0의 갯수를 구성하는 게 일반적이다.
예를들면 120 = 2³ * 3¹ * 5¹ = 2¹ * 3¹ * 10¹ 이라서 가능하다.

서론이 길었는데, 다시 본문으로 돌아와서.
이 문제에서는 nCm을 구하는게 아니라 nCm의 0의 개수를 구하는 문제이니, [분자에서 나온 2^a * 5^b]와 [분모에서 나온 2^c * 5^d] 를 구해서 a-c 와 b-d 중에 더 작은 값이 곧 nCm의 0의 개수가 된다.

N=9 으로 생각해보자.
N! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 이 될 것이다.
여기서 2의 배수만 추려낸다면 2의 지수를 구할 수 있을 것이다.
2의 배수 = N/2 개만큼 있다. = 4개 ( 2, 4, 6, 8. )   --- 여기서 2의 배수만 구했는데, 그럼 2, 4, 6 이 각각 2¹ 을 가지고 있다는 뜻이된다.
4의 배수 = N/4 개만큼 있다. = 2개 ( 4, 8. )       ---- 2¹에 대해서 앞에서 더해줬기 때문에 지금 센 것이 중복일 지 몰라도 잘 생각해보면 "중복을 피했다"

마찬가지로 8의 배수, 16의 배수... 에 대해서 반복하면 된다.
5의 배수도 위와 같이 세면 된다.

수학적인 사고가 부족해서 위 개념을 이해하는 데 한참 걸렸다. 답답함을 안고 알려준 친구에게 고마움을 표한다.

1701 - 소녀시대 공식팬클럽 회장

2번 이상 나타나는 부분문자열을 찾고 그 최대 길이를 출력하는 문제이다.

Suffix Array 를 사용했는데,
길이가 n인 문자열 s에 대해 s[i...n]의 suffix (n개)를 나열한다. 예를들어, abbac 라면

abbac
bbac
bac
ac
c

와 같이 나오는데, 이걸 사전순으로 정렬하여 다음과 같이 만든다.

abbac
ac
bac
bbac
c

위 suffix array에 대해 서로 문자열을 비교한다.
i번 문자열과 i+1번 문자열에 대해 [0...j]를 비교. [i][j] 와 [i+1][j] 가 다를 때까지의 길이가 부분문자열의 길이가 된다.
이는 "모든 부분문자열은 모든 접미사의 접두사들"이기 때문이다.

Suffix Array는 간단한 구현으로 많은 문제에 영감을 줄 수 있지만, 위와 같이 N개에 대해 저장하거나 N²의 시간복잡도를 가지는 경우가 있어서 길이가 1만 정도만 넘어도 사용하기 힘들어진다고 한다.

길이가 10만을 넘는 문자열에 대해서 부분문자열은 어떻게 찾는지 고심해봐야겠다.

7579 - 앱

M 메모리를 확보하기 위해 활성화 중인 앱을 종료시켜야 하는데
다시 실행하는 데 드는 비용 C 를 최소화하는 문제이다.

생각을 바꿔서, 비용 C로 얼마만큼의 메모리를 확보할 수 있는가로 풀면 된다.

1244 - 스위치 켜고 끄기

남학생의 경우 주어진 수(k라 하자)의 배수마다 NOT 연산을 한다.
이부분은 인덱스 idx를 k-1부터 시작해서 idx += k 씩 증가시키면서 NOT을 하면 된다.

여학생의 경우 주어신 수 k를 기준으로 좌우대칭 구간만큼 NOT 연산을 한다.
left = k, right = k 로 설정하고 left--, right++ 을 하면서 배열의 [left]원소와 [right]원소가 다를 때 까지 NOT 연산을 반복하면 된다.

최대 학생 수=100, 스위치=100 이라 걱정없었지만, 더 큰 입력에 대해선 어떻게 해야할 지 모르겠다. 더 효율적인 좋은 방법이 있으리라 생각한다.

4493 - 가위 바위 보?

가위, 바위, 보는 서로를 향하는 상성을 가진다.
이기면 +2점, 비기면 +1점, 지면 0점이라고 했을 때
X(행)가 Y(열)과 붙었을 때 얻을 수 있는 점수는 아래와 같이 표현할 수 있다

	R	P	S
R	1	0	2
P	2	1	0
S	0	2	1

입력된 char형에 따라 R => 0, P => 1, S => 2 으로 변환하고, 테이블을 참조하여 플레이어 기준으로 점수를 더하게 했다.

1912 - 부분합

음수는 더하면 손해다. 하지만 음수의 포함한 구간이 더 큰 수를 나타낼 수도 있다.

[ 6, -4, 10, -20, 5, 4 ] 같은 경우에는 [ 6, -4, 10 ]= 12 로 최대이다.

처음부터 수를 누적하면서, 합이 음수가 되면 합을 초기화한다. 그리고 합은 더할때마다 가장 최대값을 따로 저장해둔다.
그럼 합이 음수가 되어 합이 초기화 되는 순간 "하나의 구간"이 구분되고, 따로 저장된 최대값은 "그 구간 내에서 나올 수 있는 최대 합"이 된다.