꼬부기의 공대이야기

KOI 2017 - 한국정보올림피아드 초등부 본문

Algorithm

KOI 2017 - 한국정보올림피아드 초등부

전설의꼬부기 2018.04.04 09:16

1. 딱지치기 (BOJ 14696번)
어린이 A와 B의 그림을 4,3,2,1 그림에 맞게 cnt배열을 증가시켜준다음, 별에 해당하는 부분부터 비교해 가면서 크면 답을 출력하고 break, 끝까지 가면 'D'를 출력하게 구현하였다.

#include<stdio.h> #include<string.h> int main ( void ) { int N, iter, val; scanf ( "%d", &N ); int arr[2][4]; char result; for ( int n = 0; n < N; n++ ) { memset ( arr, 0, sizeof ( arr ) ); for ( int i = 0; i < 2; i++ ) { scanf ( "%d", &iter ); for ( int j = 0; j < iter; j++ ) { scanf ( "%d", &val ); arr[i][val - 1]++; } } result = 'D'; for ( int i = 3; i >= 0; i-- ) { if ( arr[0][i] > arr[1][i] ) { result = 'A'; break; } else if ( arr[0][i] < arr[1][i] ) { result = 'B'; break; } } printf ( "%c\n", result ); } return 0; }


2. 방배정하기 (BOJ 14697번)
완전 탐색으로 해결하였다.
- N명이 있을 때 각 방을 배정할 수 있는 한계가 있다.
- 0부터 그 한계까지 각 방별로 반복문을 중첩한 뒤, 
  (N-현재 배정 방 인원)을 마지막 방 인원수로 나눈 나머지가 0이 될 경우 가능하다고 판단.

#include<stdio.h> int main ( void ) { // 방 인원 수 받을 배열 선언 int arr[3], N; scanf ( "%d %d %d %d", &arr[0], &arr[1], &arr[2], &N ); // 첫 번째 인원수 제외 for ( int i = 0; N - i*arr[0] >= 0; i++ ) { // 두 번째 인원수 제외 for ( int j = 0; N - (i*arr[0] + j*arr[1]) >= 0; j++ ) { // 세 번째 인원수로 나눈 나머지가 0일 경우 '가능' if ( (N - (arr[0] * i + arr[1] * j)) % arr[2] == 0 ) { printf ( "1\n" ); return 0; } } } // 실패 printf ( "0\n" ); return 0; }

3. 서울에서 경산까지 (BOJ 14863번)
문제를 풀기 전에 생각해낸 풀이의 공간복잡도와 시간복잡도를 고려할 수 있어야하는데,
아직은 생각나면 바로 코딩하고, 틀렸다는 결과를 보고나서야 원인을 분석하게 된다.

 처음에는 완전탐색으로 접근을 했다.

#include<stdio.h> int walk[100][2]; // 시간, 모금액 - 도보 int cycle[100][2]; // 시간, 모금액 - 자전거 int N, K, Max; void go ( int cur, int time, int Sum ) { if ( time > K ) return; if ( cur == N ) { Max = Max < Sum ? Sum : Max; return; } go ( cur + 1, time + walk[cur][0], Sum + walk[cur][1] ); go ( cur + 1, time + cycle[cur][0], Sum + cycle[cur][1] ); } int main ( void ) { scanf ( "%d %d", &N, &K ); for ( int n = 0; n < N; n++ ) scanf ( "%d %d %d %d", &walk[n][0], &walk[n][1], &cycle[n][0], &cycle[n][1] ); go ( 0, 0, 0 ); printf ( "%d\n", Max ); return 0; }

그런데 이렇게 풀 경우 시간 복잡도가 O(2^N)이 되는데, N의 범위가 100까지라서 매우 오래걸린다.

그래서 DP로 접근했다.

#include<stdio.h> #include<string.h> #define max(a,b) ((a)>(b)) ? (a) : (b) #define IMPOSSIBLE -987654321 int dp[100][100001]; int walk[100][2]; // 시간, 모금액 - 도보 int cycle[100][2]; // 시간, 모금액 - 자전거 int N, K; int go ( int cur, int timeLeft ) { if ( cur == N ) return 0; if ( timeLeft <= 0 ) return IMPOSSIBLE; int& ret = dp[cur][timeLeft]; if ( ret != -1 ) return ret; ret = IMPOSSIBLE; if ( timeLeft - walk[cur][0] >= 0 && go ( cur + 1, timeLeft - walk[cur][0] ) != IMPOSSIBLE ) ret = max ( ret, go ( cur + 1, timeLeft - walk[cur][0] ) + walk[cur][1] ); if ( timeLeft - cycle[cur][0] >= 0 && go ( cur + 1, timeLeft - cycle[cur][0] ) != IMPOSSIBLE ) ret = max ( ret, go ( cur + 1, timeLeft - cycle[cur][0] ) + cycle[cur][1] ); return ret; } int main ( void ) { scanf ( "%d %d", &N, &K ); memset ( dp, -1, sizeof ( dp ) ); for ( int n = 0; n < N; n++ ) scanf ( "%d %d %d %d", &walk[n][0], &walk[n][1], &cycle[n][0], &cycle[n][1] ); printf ( "%d\n", go ( 0, K ) ); return 0; }

백준을 기준으로 이렇게 풀면 메모리 40180KB에 시간이 104MS가 걸린다.
DP 테이블을 배열로 잡았기 때문에 공간 복잡도는 O(N*K), 시간 복잡도는 이렇게 DFS로 타고 들어갈 경우 어떻게 구하는지 아직 모른다...(아시는 분은 댓글에 남겨주세요!)

여기서 메모리를 아끼면서 동시에 시간도 줄일 수 있는 방법을 고민하다가 다음과 같이 구현했다.

#include<stdio.h> #include<string.h> #define Max(a,b) ((a)>(b)) ? (a) : (b) int dp[2][100001]; int walk[101][2]; // 시간, 모금액 - 도보 int cycle[101][2]; // 시간, 모금액 - 자전거 int N, K; int main ( void ) { int k, cur, prev, maxV = 0; scanf ( "%d %d", &N, &K ); for ( int n = 1; n <= N; n++ ) scanf ( "%d %d %d %d", &walk[n][0], &walk[n][1], &cycle[n][0], &cycle[n][1] ); dp[1][walk[1][0]] = walk[1][1]; dp[1][cycle[1][0]] = Max ( dp[1][cycle[1][0]], cycle[1][1] ); for ( int n = 2; n <= N; n++ ) { cur = n & 1; prev = (n - 1) & 1; memset ( dp[cur], 0, sizeof ( dp[cur] ) ); for ( k = walk[n][0]; k <= K; k++ ) { if ( dp[prev][k - walk[n][0]] ) dp[cur][k] = Max ( dp[cur][k], dp[prev][k - walk[n][0]] + walk[n][1] ); } for ( k = cycle[n][0]; k <= K; k++ ) { if ( dp[prev][k - cycle[n][0]] ) dp[cur][k] = Max ( dp[cur][k], dp[prev][k - cycle[n][0]] + cycle[n][1] ); } } cur = N & 1; for ( k = 1; k <= K; k++ ) { maxV = Max ( maxV, dp[cur][k] ); } printf ( "%d\n", maxV ); return 0; }

이 문제에서 DP를 구할 때 필요한 것은 바로 전 경로에서 구했던 DP와, 현재 구하고 있는 DP 이렇게 두 줄만 필요하다. 따라서 논리연산자 &를 활용해서 현재 cur와 이전 prev를 쉽게 이동할 수 있도록 구현했다. (짝수, 홀수로 접근)

4. 줄서기 (BOJ 14864번)
처음에는 위상정렬로 접근을 해서 풀었다. 
(X,Y)를 받아서 X에서 뻗어 나가는 수를 인덱스로 사용해서 해당 학생의 값을 찾아내었다.

Ex) 테케 예시 1번
학생 1번의 idx값이 2가 나오므로, 배열 A = {1,2,3,4,5}에서 A[2]인 3이라는 값을 가지게 된다.
다음 학생 2번의 idx값은 0이고, 배열 A = {1,2,4,5}에서 A[0]인 1이라는 값을 가짐.
다음 학생 3번의 idx값은 2이고, 배열 A = {2,4,5}에서 A[2]인 5라는 값을 가짐
쭉..

이렇게 풀었더니 대략 10,000KB에 1.1초가 걸렸다.

고민하다가, 이번에는 뻗어 나가는 수는 +, 들어오는 수는 -로 계산한 뒤에, 각 학생 번호를 더해주었다.
Ex) 테케 예시 1번
위의 방법을 고려했을 때 {2,-1,2,0,3}이 나오는데, 여기에 학생 번호를 더해주면
{3,1,5,4,2}가 나온다.

#include<stdio.h> int list[100001], visited[100001], total; int main ( void ) { int N, M, a, b; scanf ( "%d %d", &N, &M ); for ( int m = 0; m < M; m++ ) { scanf ( "%d %d", &a, &b ); list[a]++; list[b]--; } for ( int n = 1; n <= N; n++ ) { list[n] += n; if ( list[n] > 0 && !visited[list[n]] ) { total++; visited[list[n]] = 1; } } if ( total == N ) for ( int n = 1; n <= N; n++ ) printf ( "%d ", list[n] ); else printf ( "-1\n" ); return 0; }

느낀점
: 와.. 공부할겸 초등부 올림피아드 풀어봤는데 장난 아니구나..라는 것을 깨달음
기본기 닦는데 최고인듯!


4 Comments
  • 프로필사진 Favicon of https://yummystudy.tistory.com 작은흐름 2018.04.04 15:59 신고 대박! 안그래도 정올 준비하시는 자제 있으신 분들 요새 계신 것 같던데 큰 도움 될 것 같습니다! 코딩쪽은 반발짝쯤 걸치다 만 정도라(;;) 이건 C++인 거지요? C언어쪽은 구경만 해보고 요즘 파이썬 독학 하다 반쯤 때려친 상태거든요ㅜㅜ 띄엄띄엄 했더니 앞부분이 기억 안나서 다시 독학과정 리셋하고 처음부터 다시 시작할까 하는 중이에요ㅜㅜ 정올은.. 파이썬은 아니고 C지요? 어차피 정올할 건 아니니 파이썬 배우고 바로 텐서플로우 배워볼까 했는데.. 기초 단계에서 허덕허덕 헤메고 있네요ㅜㅜ
  • 프로필사진 Favicon of https://gd-story.tistory.com 전설의꼬부기 2018.04.04 16:23 신고 정올에서는 c++도 되는 것으로 알고 있어요!

    텐서플로우면 딥러닝에 관심이 있으신가봐요!
    프로그래밍 언어를 조금 익힌 적이 있으시다면 조금만 익숙해지면 하실 수 있을것 같습니다.
    파이썬은 '점프 투 파이썬' 이 책 내용이 인터넷에 무료로 올라와 있는데, 책으로 공부하는게 편하시면 구매해서 보시는 것도 나쁘지 않을 것 같아요.

    그리고 텐서플로우 같은 경우는 저는 코드로 큰 줄기를 이해하고, 논문을 읽거나 인터넷에서 세세한 개념들을 익혀가는 중인데요, '골빈 해커 텐서플로우맛' 이 책이 아주 쉽게 코드 설명이 잘 되어 있으니 한번 알아보세요~^^
  • 프로필사진 Favicon of https://gd-story.tistory.com 전설의꼬부기 2018.04.04 16:26 신고 참고로 파이썬이 어떻게 코드가 굴러가는지 이해하고, 딥러닝에서 많이 쓰는 패키지(도구 모음집) 는 어떤게 있는지 정도 알고,

    딥러닝은 개념 이해가 되어야 쉽게 익힐 수 있는 것 같아요.
    골빈 해커 말고 하나하나 익히고 싶으시다면

    퍼셉트론
    CNN(ReNet 등등)

    이 두개부터 개념을 이해하고 가시는게 좋습니다.
  • 프로필사진 Favicon of https://yummystudy.tistory.com 작은흐름 2018.04.07 19:00 신고 우와! 좋은 책 소개 감사합니다! 지금은 코드아카데미로 파이썬 공부하고 있어요. 딥러닝에 대한 입문서 하나로 간단하게 알고리즘들에 대한 소개 정도 공부했는데 파이썬 빨리 끝내고 말씀해주신 책 한번 봐야겠어요! 감사합니다!
댓글쓰기 폼