2014년 8월 30일 토요일

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 = 23 * 31 * 51 = 21 * 31 * 101 이라서 가능하다.

서론이 길었는데, 다시 본문으로 돌아와서.
이 문제에서는 nCm을 구하는게 아니라 nCm의 0의 개수를 구하는 문제이니, [분자에서 나온 2a * 5b]와 [분모에서 나온 2c * 5d] 를 구해서 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 이 각각 21 을 가지고 있다는 뜻이된다.
4의 배수 = N/4 개만큼 있다. = 2개 ( 4, 8. )       ---- 21에 대해서 앞에서 더해줬기 때문에 지금 센 것이 중복일 지 몰라도 잘 생각해보면 "중복을 피했다"

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

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

2014년 8월 21일 목요일

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개에 대해 저장하거나 N2의 시간복잡도를 가지는 경우가 있어서 길이가 1만 정도만 넘어도 사용하기 힘들어진다고 한다.

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

2014년 8월 16일 토요일

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(열)과 붙었을 때 얻을 수 있는 점수는 아래와 같이 표현할 수 있다

RPS
R102
P210
S021

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

1912 - 부분합

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

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

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

2014년 8월 14일 목요일

2504 - 괄호의 값

스택인건 알겠는데 내가 스택 처리를 너무 복잡하게 한 것 같다.

스택 2개를 사용했는데, 하나는 누적값을 넣고, 나머지 하나는 가장 최근에 열린 괄호를 쌓아올렸다.
그리고 닫는 괄호가 나올때마다 이전의 누적값을 갱신했다.
"([])" 를 예로 들면 아래와 같다.

(
x2

( [
x2 x3

(
x2 +3


+6
중간에 짝이 다르면 곧바로 0을 리턴하도록 했다.

소스

2014년 8월 12일 화요일

6500 - 랜덤 숫자 만들기

숫자를 sprintf 등을 이용해서 0이 채워진 8자리 숫자의 형태로 (문자열로) 가공한다.
즉, 8580 은 00008580 과 같이 만든다.
문제의 조건에 따라 다음 숫자의 형태는 둘 중 하나로 결정된다.
숫자가 9999보다 크다면 00####00 을 추출하고, 아니라면 0000#### 를 추출한다. (여기서는 n=4 이기 때문에)
atoi를 이용하여 위에서 추출한 문자열이 곧 다음 숫자가 된다.

위 행동을 반복하면서 사이클이 (=같은 숫자가 다시) 나올 때 행동을 중지하고 반복 횟수를 출력한다.

2075 - N번째 큰수

N크기의 테이블이 주어지면 그 중에서 N번째 큰 수를 구하는 것인데
사실 테이블이라는 형태는 의미 없고 크기가 N2 인 수열에서 N번째 큰 수를 찾으면 된다.

필자는 입력과 동시에 처리하였다. min-heap의 형태를 이용하였는데,
N번째 큰 수를 찾기 위해서는 N개만 누적하고 있으면 되기 때문이다.

12 7 9 15 5 까지 입력된 상황이라면 min-heap은 5 7 9 12 15 의 형태를 이룰 것이다.
다음으로 13 이 들어오면 min-heap에서 최소값을 pop 하고 13 을 push 하면 된다.
그럼 13 이 push된 상황은 7 9 12 13 15 와 같을것이다.

이렇게 N개의 크기를 끝까지 유지하고 입력이 종료 되었을 때 min-heap의 가장 top를 출력하면 그게 N번째 큰 수가 된다.

2014년 8월 5일 화요일

안드로이드에서 Jsoup을 사용하기 위한 세팅

Jsoup 이라는 훌륭한 클래스를 사용했다.

Document document = Jsoup.connect("http://www.blogger.com/").get();
Element el = document.select("#selectID");

select라는 메소드는 강력한 기능을 가진다.
마치 자바스크립트 콘솔에서 선택자를 그대로 옮긴 느낌인데 자세한 사용법은 공식 사이트 API를 참고하면 된다.

Jsoup을 사용하기 위해서는 libs폴더에 jsoup.1.x.x.jar 를 옮긴 다음
Project - Properities - Java build path 에서 Library탭에 들어가고 [Add Jars..] 를 클릭해서 불러오면 된다.

마지막으로 인터넷 접근 권한을 허용하기 위해 안드로이드 메니페스트에서 <uses-permission android:name="android.permission.INTERNET" /> 를 추가한다.

이제 Jsoup을 사용하기 위한 세팅이 끝났다.

2014년 8월 4일 월요일

1149 - RGB거리

<9465 - 스티커>의 솔루션을 그대로 적용해서 풀면 된다.

i번째에서 R을 고르면 i+1번째에서는 G, B밖에 못 고르고 둘 중 (선택했을 때 더욱) 최소값인 것을 저장하면 된다.

스티커에서 재귀로 짰다가 시간초과에 후덜거렸기때문에 O(N)만에 끝나게 안정적으로 짰다!

2014년 8월 3일 일요일

9465 - 스티커

한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.
그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다.

A B C D
E F G H

위와 같이 있을 경우, A 를 선택한다면 C D F G H 중에 선택하게 된다. (하지만 대각선을 선택하는게 가장 좋기 때문에 F 가 선택될 것이다.)
여기서 F 를 선택했다고 생각하면 남은건 C D H 인데, C D 중 더 큰 것을 선택한 것이 F 를 선택했을 때의 최선의 선택이다. X번의 최선의 선택을 F(X) 라 하자.
이해하기 쉽게 위아래로 나누자면 윗줄 중에서 최선의 선택을 F(X), 아랫줄은 G(X) 라고 했을 때,
F(X) 는 F.x(윗줄 x번째 스티커의 값) 과 max( G(X+1), G(X+2) )을 더한 값이 최선의 선택일 것이다.

50 10 100 20 40
30 50  70 10 60

은 아래와 같이 진행된다.

(Base case)
0 0 0 0 40
0 0 0 0 60

0 0 0 20+60=80 40
0 0 0 10+40=50 60

(남은 대각선 방향에서 가장 최선의 값을 누적. 같은 줄은 이미 이전에 확인을 함!)
0 0 100+max(50,60) 80 40
0 0 70+max(80,40) 50 60

(사실 여기서부터는 대각선 방향에서 가장 최선을 볼 필요가 없다. 왜냐면 대각선 방향이 이미 최선이 되었기 때문)
0 10+150 160 80 40
0 50+160 150 50 60

50+210 160 160 80 40
30+160 210 150 50 60

이제 F(0) 과 G(0) 중에서 무엇이 더 큰가만 확인하면 된다.

2014년 8월 2일 토요일

1212 - 8진수 2진수

처음에 파이썬으로 풀었는데 재채점되면서 오답으로 바뀌었다.

파이썬 코드는 다음과 같다.
print bin(int("0%d"%input(),8))[2:]


그래서 그냥 C++로 바꿨다. 8진수는 3자리씩 끊어서 2진수로 변환이 가능하다.
314 → 011 001 100 → 11001100
근데 이거도 귀찮아서 제일 확실한 방법을 썼다. 방법은 아래 코드 참고



숫자에서 앞의 0을 제거하는건 라이브러리 함수를 찾아볼까하다가 그냥 플래그 하나 놓고 처리했다.

게시글 목록