티바이트

출처 

Koreatech Online Judge(링크)

문제이해 

양의 정수를 1부터 일렬로 나열했을 때 (ex 123456789101112...) P번째에 오는 숫자를 구하는 문제이다.

문제접근 

자리수가 1개인 수(1~9), 2개인 수(10~99), 3개인 수(100~999), ... 를 구분하여 계산한다

구현 

아래와 같은 규칙이 있다.

- 자리수가 1개인 수를 모두 썼을 때는 길이가 9인 문자열이 생성된다.

- 자리수가 2개인 수를 모두 썼을 때는 길이가 90*2 = 180 인 문자열이 생성된다.

- 자리수가 3개인 수를 모두 썼을 때는 길이가 900*3 = 2700인 문자열이 생성된다.

만약 P 값으로 2889가 입력된다면, 그 수는 9+180+2700 이므로 세 자리 숫자 중 가장 마지막에 오는 숫자(999)일 것이다.

같은 방법으로, 임의의 P가 있을 때 이 수가 몇 자리 수로 이루어진 정수까지 썼을 때 나온 길이인지 계산할 수 있으며, 해당 자리 수를 가진 수 중 가장 작은 수까지 썼을 때 문자열의 길이도 구할 수 있다.

1부터 n까지 수를 일렬로 나열했을 때 문자열의 길이를 f(n)이라 한다면,

예를 들어, f(1000)과 f(10000)을 미리 계산할 수 있으므로, P가 이 사이의 값이라면 P는 네 자리 수까지 썼을 때의 값이다. 이 P값에서 f(1000)을 뺀 후 4로 나누고, 1000을 더하면, n값을 알 수 있는 것이다.  

실행결과 

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1068/1068.cpp

출처

Koreatech Onlinejudge(링크)

문제이해

-50000이상 50000이하 정수로 이루어진 배열이 입력된다. 두 개의 수를 제외한 나머지 수는 모두 2개씩 존재한다. 단 하나씩만 존재하는 두 수를 크기가 작은 것부터 출력하는 문제이다.

문제접근

유일한 수를 찾는 문제에서는(링크) 모든 배열원소들을 XOR연산으로 누적하여 쉽게 구할 수 있었다. 그러나 이 문제에서는 2개를 찾아야 하므로 단순히 XOR로는 구할 수 없다. 

1. 배열 이용

입력되는 수의 범위가 -50000부터 50000까지 100001크기의 범위이므로 크기 100001짜리 배열을 만들고, 모든 인자를 0으로 초기화한 후, 입력배열을 순차탐색하면서 해당 입력값을 인덱스로 하는 배열위치에 1을 더한다. 이 과정이 끝났을 때 1이 기록되어 있는 위치를 출력하면 된다. 이 방법의 한계는 입력되는 수의 범위가 더 클 경우 적용할 수 없다는 것이다.

2. std::map 이용

입력되는 수를 std::find()로 찾아서 값이 있으면 std::erase()로 지우고 없으면 추가한다.

최종적으로 남은 요소를 출력하면 된다

std::map은 rbtree로 되어있기 때문에 각 연산이 O(logn)이며 입력의 수만큼 반복하게 되므로 복잡도는 O(nlogn)이 된다.

3. 비트연산(XOR) 이용

(참고 : http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/)

XOR연산으로도 이 문제를 풀 수 있다. 우선 모든 수를 XOR연산으로 누적하면 하나의 수가 나오는데, 이것은 답으로 출력해야 할 두 수의 XOR연산결과이다. 이 결과에서 rightmost set bit(낮은 비트부터 봤을 때 1이 처음으로 나타나는 위치)을 찾는다.

예를 들어 XOR결과가 이진수로 1101000라고 하자. rightmost set bit을 제외한 나머지 비트들을 0으로 하면 0001000이 된다. 이것은 모든 입력값들 중에서 해당 위치에 1이 쓰여진 원소가 홀수 개라는 뜻이 된다. 즉, 구하고자 하는 답 중에서 하나는 해당 위치에 1이 쓰여진 원소들 중에서 나오고, 다른 하나는 해당 위치에 0이 쓰여진 원소들 중에서 나온다는 것이다.

이제 다시 모든 원소들을 위에서 구한 XOR값(위 예시에서는 0001000)과 비트 AND 연산을 하면서, 결과가 1인 경우와, 결과가 0인 경우로 나누어 각각 XOR연산으로 누적한다. 

문제의 조건에 따라, 구한 두 값을 크기순서로 출력하면 된다.

구현

이 문제에서 필요한 rightmost set bit의 형태는 위치값이 아니라, 해당 비트만 1로 세팅된 수이기 때문에 아래와 같은 간단한 연산으로 구할 수 있다.  (1101000을 예시로 하여 직접 계산해 보면 이해할 수 있다.)

num&(~num+1)

이 연산을 잘 보면, 2의보수를 구하고 있는 형태이기 때문에

num&-num 으로도 쓸 수 있다.

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1074/1074.c

출처

Koreatech OnlineJudge(링크)

문제이해

5000자 이하의 문자가 입력으로 주어지고, 임의의 위치에 문자를 추가하여 펠린드롬으로 만들 때 추가하는 문자의 개수를 최소화하면, 몇 개인지를 구하는 문제이다.

문제접근

동적 프로그래밍 문제이다.

인덱스 a부터 인덱스 b까지의 구역에 대해 펠린드롬을 만들기 위한 최소비용을 D[a][b]라고 하자. D[a][b]를 한 단계 작은 계산결과로 구하기 위해 두 가지 조건을 따져봐야 한다.

1. 구역의 맨 앞과 맨 뒤가 같은 문자인 경우

D[a][b] (구역의 전체)는 D[a+1][b-1] (회색 부분)와 같다.

2. 구역의 맨 앞과 맨 뒤가 다른 문자인 경우

D[a][b] = 1+min(D[a][b-1], D[a+1][b])

a부터 b-1까지의 부분구역과, a+1부터 b까지의 부분구역 중에서 비용이 작은 것을 선택하여 거기에 1을 더한 값을 D[a][b]로 한다.

Top-down 방식으로 점화식을 해결하면 시간복잡도가 지수함수가 되므로, 아래에서부터 누적하여 구해야 한다.

구간의 길이를 1부터 전체까지 늘려 가며 데이터를 얻는 것이다.

전에 포스팅했던 이 문제와 같은 아이디어이다.

구현

다음과 같이 전처리하면 복잡하지 않게 반복문을 짤 수 있다.

- 구간의 길이가 1인 경우 D값은 0으로 한다.

- 구간의 길이가 2인 경우 D값은, 두 문자가 같을 때 0, 다를 때 1로 한다.

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1060/1060.cpp

출처 

Koreatech OnlineJudge(링크)

문제이해 

입력으로 두 수 A, B가 주어지고 A/B를 순환마디를 표시하여 출력하는 문제이다.

예를 들어 0.123579579579... 를 출력한다고 하면 0.123(579)와 같이 출력하는 것이다.

만약 입력이 1, 4로 계산결과가 0.25가 되어 나누어 떨어진다면 0.25(0)처럼 표현한다.

문제접근

출력해야 할 수가 그림과 같이 0.123579579579... 라면

순환마디 시작점인 a와 끝점인 b를 구해야 한다.

그렇다면 순환마디가 어디까지인지는 어떻게 구해야 할까?

나눗셈을 할 때 매 과정마다 몫과 나머지가 나오고 나머지를 다시 나누는 과정을 반복하는데, 매 과정마다 이 나머지 값을 저장해 두고, 저장됐던 나머지와 같은 값이 나올 때 반복을 종료한다. 이 때 해당 나머지 값이 처음 나온 부분이 순환마디의 시작이며, 다시 나온 부분이 순환마디의 끝이다.

구현

매 과정마다 나머지 값이 이미 저장되어 있는지 검사해야 하므로 STL map을 사용하면 적절하다. STL map은 레드-블랙 트리를 사용하고, map::find()는 O(logn)으로 어떤 원소가 존재하고 있는지 검사할 수 있다.

반복문의 종료조건은 아래와 같이 두 가지이다.

- 나머지가 0이 되었을 때 (유한소수)

- map::find()값이 map::end()와 다를 때 (나머지값이 중복하여 등장했을 때) 

printf()함수를 사용하여 출력할 때

printf("%.*s", length, str);

의 형태로 사용하면 str이라는 char배열을 length길이만큼 출력할 수 있다.

실행결과

코드

코드에서 for(;~scanf.... 와 같이 되어 있는 부분은 문제를 빨리 풀기 위해 작성한 것으로, 데이터를 입력할 때 EOF를 입력해 주어야 프로그램이 제대로 완료된다.

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1008/1008.cpp

출처

Koreatech OnlineJudge(링크)

문제이해 

전화번호를 누를 때 연속된 각 번호가 상하좌우로 한 칸씩만 떨어져 있는 번호를 '걸기 쉬운 전화번호'라고 한다. 예를 들어 1236987412는 '걸기 쉬운 전화번호'이다.

999와 같이 같은 숫자가 연속하여 나오면 이에 해당하지 않는다.

길이가 N인 '걸기 쉬운 전화번호'를 구하는 문제이다.

문제접근

DP(동적 프로그래밍)로 해결할 수 있는 문제이다.

길이가 n이고, m으로 끝나는 '걸기 쉬운 전화번호'를 f(n, m)으로 정의한다.

그러면 길이가 n인 '걸기 쉬운 전화번호'의 개수는 

이다.

그리고 길이가 n일 때의 경우의 수는 길이가 n-1일 때를 사용하여 구할 수 있다.

예를 들어, f(n, 2)는 f(n-1, 1) + f(n-1, 3) + f(n-1, 5)로 나타낼 수 있는데, 2와 인접해 있는 숫자가 1, 3, 5이기 때문이다.

다시 말하면 끝자리가 1이나 3, 또는 5인 전화번호 다음에만 2가 붙을 수 있다는 것이다.

이런 방법으로 0부터 9까지의 숫자에 대해 점화식을 세워 보면 다음과 같다.

f(n, 0) = f(n-1, 8)

f(n, 1) = f(n-1, 2) + f(n-1, 4)

f(n, 2) = f(n-1, 1) + f(n-1, 3) + f(n-1, 5) 

f(n, 3) = f(n-1, 2) + f(n-1, 6)

f(n, 4) = f(n-1, 1) + f(n-1, 5) + f(n-1, 7)

f(n, 5) = f(n-1, 2) + f(n-1, 4) + f(n-1, 6) + f(n-1, 8)

f(n, 6) = f(n-1, 3) + f(n-1, 5) + f(n-1, 9)

f(n, 7) = f(n-1, 4) + f(n-1, 8)

f(n, 8) = f(n-1, 0) + f(n-1, 5) + f(n-1, 7) + f(n-1, 9)

f(n, 9) = f(n-1, 6) + f(n-1, 8)

bottom-up 방식으로 메모이제이션을 하면 답을 구할 수 있다.

구현

각 번호에 대해, 길이가 1일 때의 초기값은 1로 한다.

f(1, 0) = f(1, 1) = f(1, 2) = ... = f(1, 8) = f(1, 9) = 1

이기 때문이다. (이 경우에 답은 10이 된다.)

길이가 2일때 위 0~9에 대해 점화식을 한 번 시행하면 되고,

길이가 3일때는 두 번 시행하면 된다.

주의할 점은 mod 1,000,000,007을 연산해야 한다는 것인데,

점화식에서 최대 4개의 항을 더하므로 32비트 unsigned int이상의 자료형을 사용하면 편하게 구현할 수 있다.

코드

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1057/1057.c

출처

Koreatech OnlineJudge(링크)

문제이해 

수열에서 수를 3개 뽑아서 합이 0이 되는 경우의 수를 구한다. 중복되는 경우는 계산하지 않는다.

문제접근

단순히 3중 for문으로 반복하여 찾으면 시간복잡도는 O(n^3)으로, 시간초과가 나서 통과하지 못한다.

세 수 i, j, k가 있을 때 i를 처음부터 한 칸씩 증가시키면서 각 i에 대해  j와 k를 찾으면 빠른데,

이 방법을 사용하려면 먼저 수열을 정렬해야 한다.

i+j+k > 0이면

k를 감소시키고,

i+j+k < 0이면,

j를 증가시킨다.

i+j+k = 0이면,

경우의 수를 한 번 카운트하고, k를 감소시키고 j를 증가시킨다.

그리고 반복문의 종료조건은 j와 k가 서로 교차했을 때이므로 아래 그림과 같은 경우까지 반복하게 된다.

시간복잡도는 O(n^2)이다.

이 부분을 코드로 보면 아래와 같다.

prv 변수는 중복되는 순서쌍을 제외하기위해 만든 변수이다.

(전체 코드는 맨 아래에 있음.)

구현 

수열을 정렬할 때 std::sort()를 사용하면 간단하다.

위에서 중복을 제거하는 부분이 있었는데, 바깥쪽 반복문에서 i, j, k 중 i가 중복되는 경우 또한 제거한다.

실행결과 

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1005/1005.cpp

출처 

Koreatech OnlineJudge(링크)

문제이해 

수열을 각 부분당 2개 이상의 원소를 가지는 구간으로 나눌 때,

각 구간의 최댓값-최솟값 값의 합이 최대가 되도록 하려면

구간을 어떻게 나누어야 하는지 구하는 문제이다.

문제접근 

동적 프로그래밍(DP)으로 풀 수 있는 대표적인 유형이다.

문제 푸는 과정을 보면 다음과 같다.

j부터 j+i까지의 구간 S가 있을 때

이 구간을 j부터 k까지, k+1부터 j+i까지

두 개의 구간 Sa와 Sb로 나누는 것이 더 이득일 수 있다.

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 생각해 보면 이해가 쉽다.

즉, 수열 인덱스 j부터 j+i까지의 최대이득을 D[a][b]라고 하면, 

D[j][j+i] 보다 큰 D[j][k]+D[k+1][j+i]를 찾는 것이다.

큰 크기의 문제(D[j][j+i])를 풀기 위해 작은 크기의 문제(D[j][k]+D[k+1][j+i])

의 값이 필요하므로, 구간 길이가 2일 때부터 계산해야 한다.

수열의 길이가 5라고 가정하여 이 과정을 보면,

아래 그림과 같이 구간 길이가 2일때를 계산한다.

그 다음 구간의 길이가 3인 경우,

4인 경우,

마지막으로 5인 경우를 계산한다.

이 글 맨 마지막에 있는 코드를 보면 이해가 쉬울 것이다.

구현 

문제 조건에서는 구간 길이는 2보다 같거나 크지만, 실제 구현할 때에는 구간 길이가 1인 경우도 계산해야 규칙성 있는 반복문을 작성할 수 있다.

구간 길이가 1일 때의 해는 그 원소 자신의 값이 된다. 

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1059/1059.c

출처 

Koreatech OnlineJudge(링크)

문제이해
3xN길이의 판을 1x1 블럭과 2x2 블럭으로 채울 때 판을 꽉 채울 수 있는 방법의 수를 구하는 문제이다. 피보나치 수열을 사용하여 푸는 1056번 문제를 풀었다면 응용하여 풀 수 있다.

문제접근 

n번째 항을 구할 때 n-1번째 항과 n-2번째 항의 값을 가지고 구할 수 있다.

먼저 n-2항에서 n항으로 확장하는 방법은 [그림 1] 처럼 2가지이다.

[그림 1]

그리고 n-2항에서 n항으로 확장하는 방법은  [그림 2] 처럼 1가지이다.

[그림 2]

따라서 점화식은

이다.

[그림 3]에서와 같이 n-2항에서 1x1타일 6개를 확장할 수도 있기 때문에

혼동하기 쉬운데, 이 경우는 [그림 2]의 경우에 포함되므로 계산하지 않아야 한다.

[그림 3]

구현
첫 번째 항을 1로 하고, 두 번째 항을 3으로 하여 위 점화식을 반복하여 계산하면 된다.

숫자가 커질 수도 있으므로 오버플로에 주의하며 1,000,000,007로 나누어야 한다.

또한, N=1인 입력도 있으므로 이 경우에도 올바른 값이 나오도록 해야 한다.

실행결과 

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1055/1055.cpp

출처 

Koreatech OnlineJudge(링크)

문제이해

각 테스트케이스마다 문자열이 한 줄씩 주어진다.

문자열은 R, G, B 3가지 문자로 이루어져 있으며 각 문자마다 

일렬로 배치되어 있는 공의 색깔을 나타낸다.

한 턴에 맨 앞 혹은 맨 뒤의 공 하나만 제거할 수 있을 때

한 가지 색만 남기려면 최소 몇 개의 공을 제거해야 하는지 구하는 문제이다.

문제접근

dequeue 같은 자료구조가 연상되는 문제이지만

몇 가지 경우를 생각해 보면, 연속된 색의 최대길이를 구하는 간단한 문제라는 것을 알 수 있다.

문제의 조건에 따르면, 마지막에는 항상 연속된 구간만 남게 되기 때문이다.

구현

문자열을 선형탐색하며 가장 긴 연속색의 길이를 구한다. (O(n))

실행결과

코드 (컴파일러 : GNU C++11)

https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1028/1028.cpp

출처 

Koreatech OnlineJudge(링크)

문제이해 

배열의 처음부터 끝까지 주어진 간격(1~3) 이하만큼 숫자를 고를 때

최소비용을 구하는 동적 프로그래밍 문제이다.

문제에 직접적으로 서술되어 있지는 않지만, 설명을 보면 첫 번째나 마지막 징검다리는 밟지 않아도 된다는 것을 알 수 있다.

문제접근

간단한 유형의 DP(Dynamic Programming)문제이다.

예를 들어 {28, 85, 89, 70, 1, 43}이 주어질 때는,

89, 1을 고르면 되는데, 89까지의 최적해가 전체 문제의 부분해가 될 수 있는 재귀적 속성(recursive property)이 있다.

배열의 왼쪽부터 시작해서 요소 하나씩 검사해 나가면 되는데,

먼저 처음 원소인 28에 다다르기 위한 최소비용은 당연히 28이다.

그 다음 원소인 85에 가는 방법은 28을 거쳐서 가는 방법과, 85로 바로 가는 방법이 있는데,

85로 바로 가는 방법이 최소비용이므로 최소비용은 85이다.

그 다음 원소인 89 역시 (89까지 도착하기 위한)최소비용이 89이다.

그 다음 원소인 70부터는 아래와 같이 3가지 방법이 있다.

1) 28 -> 70

2) 85 -> 70

3) 89 -> 70

이 중 최소비용은 1번으로, 70까지의 최소비용은 28+70=98이 된다.

그 다음 원소인 1까지 가는 최소비용은 같은 원리로 3가지가 있다.

1) 85까지의 최소비용 + 1

2) 89까지의 최소비용 + 1

3) 70까지의 최소비용 + 1

기억해 놓은 정보로 계산하면,

1) 86

2) 90

3) 98

이므로 1까지의 최소비용은 86이 된다.

이러한 과정을 배열의 끝까지 반복하면 된다.

문제에서 주어진 점프력이 3이므로 현재 위치에서 3개 전까지의 수를 봐야 하는 것이다.

실행결과 

코드
https://github.com/tibyte/algorithm-problems/blob/master/koreatech/1011/1011.c