2014년 7월 31일 목요일

9575 - 운 좋은 수

모듈화를 잘 하니까 쉬워졌다.

처음에 배열의 갯수가 바뀌는 줄 알고 재귀적으로 생각했다가
배열이 항상 a, b, c 로 고정된거 깨닫고 3중 for문으로 끝냈다.

bool형 배열 선언해서 캐싱하면서 중복되는 수를 제외시켰고
lucky(n) 이란 함수로 정수 n에 5나 8이 포함되는지 확인했다.

5나 8이 확인되는지는 sprintf로 스트링을 만든 다음 인덱스 하나씩 확인했음.

중복 제외시킬 때 숫자 최대 합이 90000 인거랑 매번 테스트케이스마다 초기화를 까먹어서 오답을 받았다.
초기화랑 배열 범위는 항상 조심!

2312 - 수 복원하기

소수 찾기처럼 에라토스테네스의 체를 이용하면 굳이 n까지 확인을 안 해도 될거라 생각했는데, 아닌가보다.

매개변수를 2부터 N까지 증가시키면서 나누어 떨어진다면 N을 2로 나눌 수 있는 만큼 나누고 몇번 나눴는가를 출력했다.

사실 매개변수를 k 라고 한다면 logkN 으로 알 수 있지 않을까 했는데 그렇지도 않았다. 나누어떨어진다는 이유로 다른 소인수를 무시하고 억지로 나누어버리기 때문. (예를들면 k=2 인 상황에서 n=10)

2014년 7월 28일 월요일

1005 - ACM Craft

DFS로 탐색을 했다. 그냥 DFS를 했다고 해야하나? 역전 앞

노드와 간선의 정보가 주어지고 노드 번호가 주어지면 "그 노드까지 이어진 최장 경로"를 찾는 문제로 생각할 수 있는 데, 그림의 간선 방향을 반대로 바꾸면 "시작노드가 주어지고 시작노드로부터 가장 긴 경로"를 찾는 문제가 될 거라고 생각했다.

하지만 위 알고리즘은 시간초과를 벗어날 수 없게되었다...

친구의 도움을 받아 백트래킹을 이용하면 풀 수 있다는 것을 알게 되었다.
한 노드를 잡고 그 노드까지 가는 최대 경로를 누적하면 목적지까지 가는 노드를 알 수 있다!

백트래킹이 뭔지 모르는 친구에게 백트래킹을 배웠다. 밤낮으로 더 열심히 문제를 풀어야겠다.

2014년 7월 27일 일요일

2014년 7월 26일 토요일

7575 - 바이러스

라빈-카프 알고리즘을 사용했다. 사실 KMP 알고리즘이 더 적합할 거 같지만..

vector< vector<int> > 형을 사용해서 두 문자열 s와 t에 나오는 패턴의 교집합 저장하였다.
정확히는 [패턴 집합] 과 [문자열]에 대한 교집합을 새로운 [패턴 집합]으로 교체하면서 다음 문자열과 이것을 반복했다.

예를 들면, 문자열 [1 3 2 5 4] 와 [2 5 3 1] 에서 뽑아낼 수 있는 패턴 집합은 "[1 3], [2 5]" 이다. 이 집합을 초기 집합으로 설정하고 "[1 3], [2, 5]" 와 [6 5 1 3 5] 의 교집합을 구한다.
그럼 여기서 일치하지 않는 패턴들은 소거된다.

위 생각으로만 제출했을 때 메모리 초과를 받았다. "[1 2], [1 2], [1 2], [1 2]..." 와 같이 계속 들어갔기 때문인데, map을 사용해서 중복되는 패턴의 삽입을 방지하니 정답을 받았다.
여기서 신기한게 map의 key값 형태를 vector<int>로 하고 체크할 때 인스턴스만 넘겼는데 배열의 각 원소들을 모두 비교한건지 어쩐거지 겹치는 벡터가 없었다. STL의 위엄

2014년 7월 25일 금요일

9461 - 파도반 수열

작년 ACM 본선 문제.

단순한 규칙성 문제라 정답은 아래 정의 하나로 끝나지만 몇가지만 조심하면 된다.

파도반 수열의 N번째 항은 P(N) = P(N-2) + P(N-3); 과 같이 나타낼 수 있다.

하지만 재귀식이므로 DP를 이용해서 꼭! 시간복잡도를 줄여야한다.

2417 - 정수 제곱근

n이 주어지면 q2 ≥ n 이 되는 q를 찾으라는데, 식을 뒤집으면 q ≥ √n 이므로 경계만 잘 파악하면 쉽게 q를 알아낼 수 있다.

이 문제에서 꽤 여러번 틀렸는데, 입력되는 정수 N 의 범위가 0 ≤ N ≤ 263 이라길래 당연히 unsigned long long 을 썼다. 그런데도 계속 틀린 답이 나와서 도대체 뭐가 문제인지 몰랐는데, 오답은 "0 ≤ N" 을 간과해서 나온 것이였다.

unsigned long long 은 0 을 포함하지 않으므로 overflow가 나는걸 주의하자.

그리고 최소/최대 케이스 테스트할 때, 대충 하지 말아야겠다.

2014년 7월 23일 수요일

1753 - 최단경로

정점의 갯수 V와 간선의 갯수 E가 주어지고, E개만큼의 간선 정보가 입력된다.
정점은 1....V 만큼 있을 때 시작점 Vs 로부터 모든 간선으로의 최단 경로를 출력하는 문제이다.


먼저, 필자는 벨만-포드 알고리즘을 사용했다. 벨만-포드는 O(VE)의 시간복잡도를 가져서 이 문제에서는 적합하기 않다. ( 1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000 이기 때문 )

E개의 노드를 차례로 살피면서 각 노드의 최단경로 정보를 갱신한다. 정확도를 위해 (누락되는 경로가 없도록) 각 정점의 갯수 V만큼 갱신을 반복한다. 그래서 O(VE)이다.

당연히 시간초과를 받았지만, 확률상으로 누락되는 경로가 있을까 싶어서 모험을 해봤다.
V번 반복하지 않고 log(V)번 반복해서 시간복잡도 O(E logV)로 도전해봤는데 정답을 맞았다. 운이 좋았다. 그리고 난 쾌재를 불렀다

7806 - GCD!

n! 와 k 의 최대공약수를 구하는 문제이다.

n!과 k를 각각 소인수분해해서 각 겹치는 인수들 중에 지수가 더 작은 것끼리 곱하면 그것이  n!과 k의 공약수이다.

예를 들어, (n=4)!, k=18 이라면 4! 을 소인수분해하면 23x3 이고 18 은 2x32 이다. 겹치는 인수는 2, 3 이고 지수가 더 작은 것끼리 곱하면  21x31 = 6 이다.

매개변수 p를 두고 p=2 부터 $p^2 \le k$ 까지 늘려가면서 아래 작업을 수행한다.

n에서 pa 를 알아내고, k에서 pb 를 알아내서 result 에 pmin(a,b)를 중첩하여 곱셈했다.

5724 - 파인만

정답은 "N까지의 {Nk2}들의 합" 이다.

N=1 일 때 칸은 1개이다.
N=2 일 때는 1개짜리 칸이 2X2. 총 4개만큼 늘어나고, 거기에 2X2짜리 네모가 1개 있다.
N=3 일 때는 1개짜리 칸이 3X3개 + 2X2짜리가 4개 + 3X3짜리가 1개....

더이상 자세한 설명은 생략한다.

1003 - 피보나치 함수

보통 피보나치는 문제의 설명에 적혀있듯이 재귀적으로 작성할 수 있다.

return fibonacci(n‐1) + fibonacci(n‐2); 와 같이 말이다.

하지만 함수의 호출 스택의 한계를 무시한다고 생각해도 일단 중복되는 호출이 굉장히 많다.
f(3) = f(2) + f(1) = f(1) + f(0) + f(1) = f(1) + f(0) + f(0) 과 같이 f(3)만 하더라고 f(1)을 여러번 부른다. 이러면 시간복잡도는 지수함수가 되는데, 메모리는 둘째치고 시간이 굉장히 오래걸린다.

즉, 이 문제는 재귀를 사용하지 않고 비재귀적(iterative)하게 작성할 수 있는가가 핵심이다.

원리만 잘 파악하면 피보나치는 변수 2개로 해결할 수 있다.

먼저 a = 0, b = 1 로 시작한다. 그리고 다음번의 b 가 a + b 가 되고, 다음번의 a 는 바뀌기 전의 b 가 된다. 이 행동을 반복하면, b는 N번째 피보나치 수가 된다.

예를 들면, 순서대로 a b 라고 할 때 1~5번의 반복이 일어날 동안 변수의 상황은 아래와 같다.

0 1
1 1
2 1
3 2
5 3

예시를 잘 보면 문제를 해결할 수 있을 것이다.

1159 - 농구 경기

자료구조 map을 그대로 사용하면 된다.

단순한 map의 사용 문제

소스 보기

2014년 7월 22일 화요일

1012 - 유기농 배추

DFS나 BFS와 같은 전탐색으로 문제를 해결할 수 있다.
필자는 DFS를 사용했는데, int dirt[4]={-1,0,1,0}; 과 같이 선언하고

08int DFS(int y, int x, int H /*최대 높이*/, int W /*최대 너비*/)
09{
10    if( /* Base Case; 기저 케이스 */ ) return 0;
15    for(int i=0; i < 4; ++i)
16        DFS( y+dirt[(i+3)%4], x+dirt[i], H, W );
17    return 1;
18}

위와 같이 [상(-1,0), 우(0,-1), 하(+1,0), 좌(0,+1) ]의 조합을 배열 하나로 사용했다.

여기서 DFS가 return 1; 을 했다. 이건 한 덩어리(구간)의 출발점만 리턴될 것이다.
왜냐하면 기저 케이스에서 "방문한 노드"는 return 0; 으로  걸러질 것이기 때문이다.

2014년 7월 21일 월요일

1735 - 분수 합

입력받는 순서대로 A B C D 라고 했을 때,
A/B + C/D 를 기약분수의 형태로 나타내는 문제이다.

A/B + C/D 는 다시말해 (A*D)+(B*C)/(B*D) (중등수학:분수 참고) 라는 말인데, 기약분수란 더 이상 약분되지 않는 분수를 말한다고 한다.

분자를 v라 하고, 분모를 u 라 하고 할 때, 분자 분모에 각각 v와 u의 공약수를 나누면 된다!
공약수(=공통된 약수)로 나누면 더 이상 나눌 약수가 없다는 의미이다.

5883 - 아이폰 9S

원 제목 : Cows in a Row

모든 경우의 수에 대해 시뮬레이팅을 해보았다.
예를 들면, 2 7 3 7 7 3 7 5 7 에서 2 가 빠질 경우, 7이 빠질 경우, 3이 빠질 경우...
각 경우에 대해 가장 연속 구간이 긴 길이를 구해서 정답이 될 최대 길이를 갱신했다.

자료구조 map과 vector를 이용했다.

소스 링크

2325 - 오븐 시계

입력받은 시간, 분을 분으로 변환하고 계산하면 편하다.

나머지는 모듈러 연산을 적절히 잘 사용하면 되는데, 자세한 내용은 소스를 참고.

소스.c

1225 - 이상한 곱셈

N자리 숫자와 M자리 숫자가 주어지고, 각 숫자를 모두 더한 합을 출력한다.

두 개의 문자열 S, T 에 대해 0 .. n 까지 Sn 과 0 .. m 까지의 Tm 을 각각 곱한 후 더하면 된다.

2개의 for문으로 감싸고, sum += (S[i]-'0') + (T[j]-'0'); 을 적으면 sum이 곧 정답이 된다.

문자에 대해 S[i] - '0' 을 한 이유는 문자 '0'~'9' 에 '0'의 아스키코드값을 빼면 숫자 0 이 되기 때문이다. (이 방법은 자주 사용하므로 익혀두면 좋다)

2014년 7월 20일 일요일

1032 - 명령 프롬프트

파일 갯수는 N < 50 이고, 파일 이름도 50보다 작은데 시간제한은 2000MS.

파일 이름을 string 배열로 저장한 뒤, 한 글자를 확인할 때마다, 그 위치의 다른 모든 파일의 이름도 같이 확인했다.
예를 들면, (파일 이름)[0] 을 확인할 땐, (나머지 파일의 이름)[0] 을 확인했다.

원소를 하나씩 살피면서 모두 같다면 그 원소를, 아니라면 ? 를 출력하게 했다.

물론 이렇게 하면 O(N2) 이지만 O(N2 < 2500) 정도이므로 더 이상 생각하지 않았다.

2965 - 캥거루 세마리

조건을 확인하면 0 < A < B < C < 100 이다.
입력이 작으니 직접 시뮬레이팅을 해도 괜찮다.
캥거루의 좌표 변화는 아래와 같을 것이다.
3 5 9
5 6 9
6 7 9
7 8 9
그래서 결과는 3 이 나오는데, 첫번째 이동 이후로는 A, B 가 1씩 밀리는 것을 확인할 수 있다.
왜냐하면, 처음에 더 넓은 구간을 찾을 후, 그 구간 직전(혹은 직후)로 이동하면 그 둘 사이는 거리가 1 이기 때문에 이동할 일이 없다.
그러므로 "더 넓은 구간 - 1"만큼의 이동만 하면 된다.

2014년 7월 19일 토요일

2163 - 초콜릿 자르기

여기서 초콜릿을 쪼갠다는 표현을 나는 "절반으로 나눈다"라고 생각하여 문제가 어려워졌었다.
절반으로 쪼개고 그 이후에 다시 절반으로 쪼개는 것이나, 왼쪽(혹은 오른쪽)부터 1열씩 쪼개나 쪼개는 횟수가 같다.
즉, 가로가 M만큼의 너비라면, M-1만큼 쪼개면 되고. 다시 M-1개의 조각들에 대해 N-1번(세로)만큼 쪼개면 된다.

수식으로 정리하면 다음과 같다. 가로를 M, 세로를 N이라 했을 때,
"쪼개야 하는 횟수 = (M-1) + M·(N-1)" 이다.

2455 - 지능형 기차

시간 제한에 비해 입력 데이터가 매우 작으니 직접 시뮬레이팅을 하면 된다.

"현재 기차에 있는 사람의 수 = 이전까지 있던 사람 수 + 타는 사람 - 내린 사람" 이다.

즉, "현재 기차에 있는 사람의 수 += (타는 사람) - (내린 사람)" 을 각 기차역마다 반복하면 쉽게 정답을 받을 수 있다.

문제에서 조건이 많은데 이건 오히려 도움이 되는 조건이다. (수학에서 가정지을 때 조건을 제한하는 것과 같음)

2014년 7월 18일 금요일

1009 - 분산처리

a의 b제곱을 굳이 다 구할 필요가 없다.

ab개의 컴퓨터는 10대의 컴퓨터로 분산될 것이고, 이는 웬지 ab % 10 을 하면 될 것 같다.

그럼 1의 자리만 구하면 된다는 건데, 사실 ab는 b에 따라 일정 주기를 가지고 반복된다.

예를 들면, 30 = 1, 31 = 3, 32 = 9, 33 = 27, 34 = 81, 35 = 273 ...
1의 자리만 보면 [1, 3, 9, 7] 이 반복된다. 이는 다른 숫자들도 모두 적용되고 있다.

10번 데이터는 10번이므로 10으로 나누어 떨어질 때에 주의하면 된다.

1350 - 진짜 공간

클러스터는 한 종류의 파일만 저장할 수 있다.

파일 하나의 크기를 클러스터의 크기로 나누면 필요한 클러스터 갯수가 나오지만 정수형으로 변환되면서 소수점이 잘린다.

나누어떨어지지 않으면 1을 더해주자.
(예를 들면, 파일은 512 이고 클러스터는 512 일 때는 클러스터는 1개만 있으면 된다.)
( 511 / 512 = 0 이고, 512 / 512 = 1 , 513 / 512 = 1 .. )

클러스터 크기와 클러스터 갯수를 곱한 값이 문제의 정답.

1759 - 암호 만들기

재귀적인 탐색 문제이다.

문제에서 "최소 1개의 모음과 최소 2개의 자음" 이라는 부분을 놓쳐서 몇 번 틀렸다.

재귀함수는 아래와 같다.

void password( int cur, int k, int N, int /*Consonant*/int /*Vowel*/ ){
    
if( k >= N && C > 1 && V > 0 ){
        
// 누적된 문자열 출력
        
return;
    
}
    // ....

}

글자수가 제한되어 있으니 재귀 호출의 깊이를 제한하면 된다.
깊이의 제한을 위해 k로 깊이를 인자로 넘기고, N은 문제에서 말한 암호의 길이이다.

cur은 알파벳이고, 처음에 입력받은 알파벳들은 정렬 후 사용했다. (사전순 출력을 위해)

게시글 목록