마지막 정보올림피아드를 다녀왔습니다.
![도전하는 모든 사람에게 행복이 있기를](https://steemitimages.com/640x0/http://i.imgur.com/ob6vZoK.jpg)
안녕하세요, 계략입니다.
일상...이랄까요. 그런 글입니다.
블록체인이라는 특성상 개인정보를 올리기를 꺼려했는데
생각해보니 이정도까지는 괜찮지 않을까... 했습니다.
저는 고등학교 3학년입니다!
이런... 슬프네요.
그리고 정보과학이나 프로그래밍 쪽으로 관심이 있습니다.
그런고로 옛날부터 쭈욱, 한국정보올림피아드에 참가해 왔습니다.
지금까지 두 번, 전국대회에서 은상을 수상했습니다.
사실 그런 것 치고는 제 프로래밍 실력이 뛰어나다고 생각하진 않아요.
다른 수상자들을 보면 엄청 신기할 따름입니다.
약간의 꼼수라면 꼼수를 잘 쓴 덕분이죠.
어찌 되었든, 고3인지라 올해가 마지막이었습니다.
그래서 그걸 준비한다고 1주정도 스팀잇에 글을 올리질 못했네요.
그보다도 감기에 걸렸던게 컸습니다. 아직도 다 안 나았어요. ㅠㅠ
정보올림피아드는 프로그래밍 경진대회입니다.
절대 검색하는 대회가 아니에요!
초등부 / 중등부 / 고등부 나뉘어서
총 4시간 동안, 4개의 프로그래밍 문제를 풀게 됩니다.
최근 들어서는 4개 모두 100점으로 배점이 동일합니다.
400점 만점이고, 보통 1등은 350점 내외를 받습니다.
가끔 가다가 중간에 400점을 받고 나가는 괴물도 있습니다
https://www.acmicpc.net/category/55
에서 지난 년도 문제를 보고 풀어보실 수 있습니다. (공식 사이트는 아닙니다)
결과부터 말하자면, 마지막 대회의 결과는 좋지 못했던 것 같습니다.
1번부터 4번까지 총 4문제가 출제되고, 각 문제별로 배점은 100점으로 동일합니다.
그런데... 1번을 포함해서 100점을 받은 문제가 없었어요.
아무래도 동상을 받게 될 것 같습니다.
실력의 한계를 체험하고 온...
아팠던 것도 있겠지만, 실력적인 한계였던 것 같습니다.
그래도 대부분이 가장 어려웠을거라 생각하는 4번 문제에서 의외의 성적을 거둔 것 같습니다.
프로그래밍 관련해서 관심 있으신 분들은 한번 풀어보셨으면 합니다.
아래는 기억에 의존한 4번 문제입니다.
조개 줍기(수산시장)
N*N개의 격자로 된 마을이 있습니다.
각 마을에는 주민이 1명씩 살고 있고,
가장 왼쪽 위의 마을에는 수산시장이 있습니다.
환경보호를 위해 각 마을에서 주울 수 있는 조개의 개수는 제한되어 있습니다.
주민들은 왼쪽 혹은 위쪽으로만 이동하며 조개를 줍습니다.
수산시장이 있는 마을에도 주민이 살고 있으며
수산시장이 있는 마을에서도 조개를 주울 수 있습니다.
생태계 보호를 위해, 공무원은 조개 개수의 제한을 바꾸려고 합니다.
한 번 바꿀 때, 한 마을에서 주울 조개 개수의 제한을 1개 줄이거나 1개 늘리는 것만 가능합니다.
맨 처음의 상태와, 바뀐 제한에 따라 수산시장에 팔리는 조개 개수의 합의 최대값을 구하세요.
입력
첫 번째 줄에 격자의 크기와 제한을 바꾸는 횟수 N이 주어집니다.
그 다음 N개의 줄에는 각각의 마을에 대해 주울 수 있는
조개 개수의 제한을 나타내는 수 K가 공백으로 구분되어 N개 입력됩니다.
그 다음 N개의 줄에는 주울 수 있는 조개 개수의 제한을 바꾸는 행동이 입력됩니다.
첫 글자가 U일 경우 1개 늘리는 행동, D일 경우 1개 줄이는 행동입니다.
글자 뒤에는 마을의 좌표가 공백으로 구분되어 주어집니다.
왼쪽 위의 마을은 1 1, 오른쪽 아래의 마을은 N N입니다.
출력
첫 번째 줄에는 초기 상태에 대해, 수산시장에서 팔리는 조개의 최댓값을 출력하세요.
두 번째 줄부터 N개의 줄에는 제한을 바꾼 뒤, 수산시장에서 팔리는 조개의 최댓값을 출력하세요.
입력 예시
2
1 5
3 2
U 1 1
D 2 2
출력 예시 (괄호 안은 출력 X)
19 (1+6+4+8)
23 (2+7+5+9)
22 (2+7+5+8)
제약 조건
1<=N<=2000
1<=K<=1000 (확실하지 않습니다)
조개의 제한이 음수가 되는 경우는 없음
1초 내에 결과를 출력해야 함
메모리 512MB 이하 (확실하지 않습니다)
너무 대충 적은 것 같긴 하지만...
일단 제가 봤을 때, 초기 상태에 대해 값을 구하는 건 전형적인 다이나믹 프로그래밍(DP) 문제였습니다.
문제는 그 다음부터죠.
DP로 잘 푼다면, O(N^2)안에 초기 값을 구할 수 있을 겁니다.
그런데 바꾸는 행동이 N개니까, 모두에 대해 DP를 쓰면 O(N^3)으로 시간이 초과됩니다.
그렇게 풀면 시간이 대략 13점이 나는 관계로 약간의 최적화를 감행했습니다.
초기 값을 구하는 DP를 할 때, 위쪽으로 가면 큰지 왼쪽으로 가면 큰지를 메모해뒀습니다.
그 뒤에 숫자를 1 키우거나 줄임에 따라서 그거에 대한 경우를 모두 처리하는(...) 방식으로 말이죠.
그렇게 해서 43점 가량을 받았습니다.
코드가 400줄 이상은 나왔더라고요.
정보올림피아드 문제를 풀면서 가장 길게 적은 코드였던 것 같습니다.
다만 저것보다 시간을 더 줄일 방법은 아직도 잘 모르겠습니다.
댓글로 토의를 해 본다면 어떨까요...?
여하튼, 좀 아쉽긴 하지만 마지막 정보올림피아드를 마쳤습니다.
몸 상태도 그렇고, 결과도 그렇고 썩 좋지만은 않지만
그래도 4번 문제에 저런 시도를 했고 부분의 성공을 거뒀다는 점과
제 한계를 제대로 느꼈다는 점에서 좋았던 것 같습니다.
읽어주신 분들께 감사드리면서,
저 4번 문제의 정해진 시간 내에 풀 수 있을 O(N^2 log N)코드를 알 것 같으신 분은 댓글로 알려주셨으면 합니다(...)
![도전하는 모든 사람에게 행복이 있기를](https://steemitimages.com/640x0/http://i.imgur.com/ob6vZoK.jpg)
제가 아는 몇 수학과, 물리학과 교수님은 중,고등학교 때 수학, 물리 쪽이 아닌 정보 올림피아드 금상 수상자 였습니다. 물론 전산과 쪽에 더 많은 출신자들이 있을 것 같긴 한데 그 분들의 경우 수학, 물리 쪽에 독보적인 존재(?) 라고 알려져 있어 놀라웠었죠 ㅎㅎ
대학에 진학하셔도 프로그래밍 대회는 많습니다. 대표적으로 국내 대회로는 http://icpckorea.org/, 또 국제 대회들도 상당히 많습니다. ㅎㅎ CS 쪽으로 진학하실 것이라면 정보올림피아드 공부가 상당히 도움이 될겁니다.
아니면 보안 관련 대회들도 상당히 많고요, 정올 하다가 온 친구들이 대학와서 이쪽으로 많이 빠지는 경우를 봤습니다. 요즘 친구들은 어떤지 잘 모르겠네요. 그 외 병렬 컴퓨팅 대회, 여러 프로그래밍 공모전 등 할 수 있는것들이 넘쳐납니다. IT 계열 대기업 회사 들이 종종 저런 것들을 열곤 합니다.
ㅎㅎ 아무튼 어느쪽으로 진로를 선택하실지 궁금하긴 하네요 ㅎㅎ 어느 쪽으로 하든지 잘 될거라 봅니다 ㅎㅎ
컴퓨터 프로그래밍, 관련해서 전산학과/컴퓨터공학과/소프트웨어공학과 쪽으로 희망하고 있습니다.
물리학과 수학과 교수님이 정올 수상자라는건 엄청 놀라운 사실이네요...
좋은 말씀 감사합니다!
프로그래밍에는 문외한인 사람이라서 올려주신 걸 봐도 하나도 모르겠어요. 😂 이번에도 좋은 상 받으시기를 바랄게요!
시험 종료 30분 전까지 리더보드(순위)를 밖에서 공개합니다.
확인한 바로는 마지막 순간에 동상 상위권이었으니... 동상 확정입니다...!
글 내용은 조금 어려운 내용...ㅠ
그래도 조금 쉽게 알고리즘에 관해서 글을 써보는 중입니다.
제 블로그에서 한번쯤 읽어보시는건 어떨까요? (홍보홍보)
https://steemit.com/kr/@gyeryak/1
https://steemit.com/kr-dev/@gyeryak/easyalgo-2-bruteforce
오~ 정보올림수상자시군요^^ 멋지십니다. 예전 과고입시 지도할때, 수학/과학 올림피아드와 함께 올림피아드 전형이 따로있었던 기억이 납니다. 앞으로 많은 정보 부탁드려요^^
열심히 해보겠습니다! 감사합니다 :)
p.s. 그 전형이 6년즈음 전에 없어졌습니다. ㅠㅠ
아~ 벌써 그렇게나 되었군요. ㅎㅎㅎ 응원하겠습니다.^^
감사합니다!
다른것보다 고3이라는게 너무 부럽습니다쥬르규ㅠ
저에게는 고통... 남에게는 부러움...
참 아이러니한 직업입니다. 고3이라...
ㅋㅋㅋㅋㅋㅋㅋ 고3...힘내세요!
언젠간 저도 고3을 그리워하고 부러워할 날이 오겠죠
그때를 위해서라도 힘내야겠죠! 감사합니다 :)
우아 그래도 엄청 잘하시는 편인 것 같네요!
꾸준히 하시면 대회 입상보다 더 좋은 보상이 많을 것 같네요.
개인적으로는
애당초 참가에 의의를 두고 있었는데, 상을 몇 번 타더니 거만(?)해진 것 같습니다...
이 쪽으로 계속 공부해 볼 생각입니다! 좋은 말 감사합니다 :)
와 고삼이라는게 우선 부럽습니다! 알고리즘 데이터스트럭쳐 공부를 고삼부터 하시다니 나중에 취업에 많은 도움이 될겁니다 ^^
처음엔 재미를 느껴서 하게 됬습니다.
지금 와서 생각해보니 정말 잘 한 것 같아요. 대학도 그렇고, 취업도 그렇고요...
대학까지 결정되어 버리신 겁니까? 와우. 나중에 신문에서 뵐것 같은 예감이 드네요.
아... 아쉽게도 아직 결정된 건 아무것도 없습니다...
다만 특기자전형이라는 폭이 생겼다는 거죠 :)
신문은 나갈 수 있었으면 좋겠습니다. 하핫;
Congratulations @gyeryak! You have completed some achievement on Steemit and have been rewarded with new badge(s) :
Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here
If you no longer want to receive notifications, reply to this comment with the word
STOP