U E D R , A S I H C RSS

ACM_ICPC/2011년스터디

1. 목표

  • 알고리즘 문제 해결 능력을 증진시킨다.
  • ACM-ICPC 2011 Asia Daejeon Regional에 도전한다.

2. 규칙

  • 한 명이라도 못 하면 다음 문제로 넘어가지 않는다.
  • 지각비
    • 지각 10분당 벌금 천원
    • 비용 계산은 올림(11분 지각시 지각비 2천원)
    • 전날 미리 이야기 하면 지각비 면제
  • 보증금
    • 만원씩 보증금을 걷고 결석 횟수가 일정 횟수 넘을 시 돌려주지 않음.
    • 회계 : 권순의

3. 진행 방식

  • 문제 제시
  • 간단한 방향 제시
    • 풀어온 후 자신의 풀이 방법 소개?
    • Anything else..
  • 맞게 푼 것인지 확인은 http://poj.org 에서

4. 출석체크

날짜 김수경 서지혜 강소현 정진경 정의정 김태진 권순의 강성현
5/22 O O O O X O O
5/29 O O O O X O O
6/5 X O X O X O X
6/26 X X O O X O O O

날짜 김수경 강소현 정진경 정의정 김태진 권순의 송지원
7/5 O O O X X O X
7/12 O O O X O O O
7/19 O O O X O X O
7/26 X O X X O O O

날짜 정진경 김태진 권순의 송지원 강소현
8/2 O O O X -
8/9 X O O O -
8/16 O O X X -
8/23 O O O O O
8/30 O O O O O

날짜 정진경 김태진 권순의 강소현 김준석 고한종
10/3 개천절 - -
10/10 O O O O - -
10/17 O O O O - O
10/31 O O O O - O

날짜 정진경 김태진 권순의 강소현 김준석 고한종
11/7 세모 O O O O O
11/14 O O X X O X

5. 스터디

6. 5월 22일

6.1. 내용

  • 진행 방식 및 기본 규칙에 대한 회의
  • 다음주 문제
  • 다음주에 보증금 걷습니다.

6.3. 후기

  • 네.. 이번주는 대략적인 것들을 결정하는 시간이었지요. Jolly Jumper를 제가 그냥 임의로 찍어서 문제로 하기로 해서, 5시 스터디가 끝나자마자 1시간동안 열심히 코딩해서 완성했습니다. ..그런데 Wrong Answer. 으아아ㅏ아아아아ㅏ 2시간동안 진경이랑 삽질하다 얻은 결론: 얘내들은 입출력방식이 달라서 우리가 짠 것만으로 되는게 아니고 계속 입력을 받도록 해야한다. 그리고 입력이 끝나면 프로그램이 종료되어야 하는데 뭐 -1?인가 그게 뜨도록 하려면 띄어쓰기같은 것도 없어야한다. ...결국 답은 대략 맞았지만 저런 형식때문에 2시간동안 고민한거죠. JollyJumpers하시는 형/누나들 참고하세요 ;ㅅ; ..아무튼 ACM스터디가 재밌게 잘 진행되었으면 좋겠어요~ -김태진

  • 늦어서 민망했습니다. 진행 방식에 대한 논의가 부족하다는 생각이 드는데 진행하면서 더 다듬으면 되겠죠? - 김수경

  • 생각치도 못한 표준입출력 때문에 고생했습니다. 저놈의 judge 프로그램을 이해하지 못하겠습니다. 입출력방식이 낯서네요. 입력 종료를 위해 값을 따로 주지 않고 알아서 EOF 까지 받아야한다니... 정올 현역때는 이런 문제 구경하기 힘들었는데ㅜㅜ 제가 뭘 크게 오해하고 있나요. 덕분에 c도 아니고 c++도 아닌 코드가 나왔습니다. 그리고 3N+1 문제가 25일 프로그래밍 경진대회에 1번 문제로 나왔습니다. 허허.. - 정진경
    • 그리고 아직도 효율적인 방안에 대해 고민하고 있습니다. 허허...(미리 고민하고 풀엇다면 정올에서 날로 먹었을것을 쳇.)-김태진
  • 할머니 생신 파티로 약 한 시간을 늦게 갔는데 친절히 맞아주어 고마웠슴다;ㅅ; 졸리점퍼의 첫 숫자도 포함인줄 알았는데 나중에 보니까 그냥 갯수였더군요. 0을 입력 받으면 갯수가 0이니까 종료되는 거고! 오오..한국어인데도 이해가 안가면 안되는데 ;ㅅ; -강소현
    • 사실 저도 한글번역한거보고 그게 더 헷깔렸다죠;; 그리고, 호두과자 맛있게 먹었어요~ -김태진

7. 5월 29일

7.1. 내용

7.3. 후기

  • 6월 1일 12시 01분, 드디어 (제가 짠 알고리즘으로, 소트해서!)졸리점퍼 Accept에 성공했습니다! 여러가지 시도를 해봐도 문제가 없었는데 왜 안되나 하다가, 결국 입출력의 문제.-_-;; 띄어쓰기도 인식하는 더러운...; 사실 코드자체가 너무 복잡해서 그걸 발견하기까지 시간이 오래 걸린 문제도 있으니, 코드를 좀 더 간결화 하는 방법도 생각해보아야 겠다고 생각했어요. 아무튼 전 다 했어요~_~(이 후기가 아니고 수업에 대한 후기를 써야하는데 말이죠;) -김태진
  • 생각보다 진행이 디뎠습니다. 입출력 문제가 생각보다 복잡하네요. 하지만 이래저래 여러번 해결하다보니 어느 정도 감이 잡히는 것 같기도 합니다. 졸리점퍼 숏코딩을 할까 하는데, 만약 한다면 처음 해보는 숏코딩이 되겠네요. 중도가서 책을 빌리고 공부해봐야겠습니다.(으아아 대출한도 초과) -정진경
    • ShortCoding 책이 아마 ZeroPage 책장에 있을텐데… 후기를 모아 정회원이 되세요 ㅋㅋㅋㅋㅋ - 김수경
  • 제 코드에 무엇이 문제인지 깨달았습니다. 입출력이 문제가 아니었어요. 숫자 범위 괜히 0이거나 3000 이상이면 "Not jolly" 출력하고 break하니까 이후에 더 적은 숫자가 들어온 경우가 무시당해서 Wrong Answer(출력 하든 안하든, 0 제외하고 3000 이상일 때만 하든 다 Wrong..;ㅅ;) 입력을 하지 않을 때까지 계속 받아야 하는데, 임의로 끊었더니 그만..... 그리고 continue로 해도 마찬가지로 3000을 제외하고 입력 버퍼에 남아있던 것들이 이어서 들어가서 꼬이게 되는! Scanner을 비우는 거는 어찌 하는 걸까요오;ㅁ;? 쨋든 그냥 맘 편하게 조건 지우고 Accepted ㅋㅋ 보증금 및 지각비 관련 내용은 엑셀에 따로 저장하였습니다. - 강소현

  • 이래저래 어느 부분이 잘못 되었는지나오지 않아 더 헤맷던 것 갔네요 -_-;; 어쩌다 정렬까지 쓰게 되어서 시간도 오래 걸리고.. 결국 완성 했는데 왜 뿌듯하지 않을까요? ㅋㅋㅋ;; - 권순의

8. 6월 5일

8.1. 내용

  • 다음주는 시험 전주입니다.
    • 이번주 참여자가 3명이었습니다. 다음주도 이렇다면 곤란할테니 다음주 참여여부를 팀장에게 알려주세요.
    • 참석률을 보아 다음주를 할지 말지 결정한답니다.
  • 다음주 문제

8.3. 후기

  • 아 졸리점퍼 썽질나 - 서지혜
  • 저번주에 온 사람들은 이제 모두 JollyJumper를 해결한거 같네요. 이제 입출력에서는 좀 덜 틀리겠죠..-_-; 다음주 나이트의 여행은.. 전 뭔가 어렵지 않을까 생각은 들지마는 코드 길이도 길고, 시간도 오래걸리고, 메모리도 많이 먹는 코드를 짜면 괜찮지 않으려나 싶네요 --; 다음주는 시험기간 전이라 스터디를 할 지 안할지 다들 의견교환을 해봐야 할거같네요 -김태진
  • 하면 할수록 입출력에 대한 감각이 어느 정도 살아나는 것 같습니다. 처음 접했을 때보단 생소하게 느껴지진 않네요. 처음에는 무슨 삽질을 했길래 그랬을까... 숏코딩을 처음으로 한번 해봤는데 역시 컴파일러에 대한 깊은 이해와 고도의 수학적 사고력이 요구되는듯 싶습니다. 졸리점퍼 71B는 도데체 어떤 코드일지... 처음에는 관심없었는데 해보니까 승부욕이 생깁니다.. 그것보다 해시함수나 B트리 등 심층적으로 다뤄보지 못한 알고리즘에 대한 의욕도 있지만.. 음!! 하고 싶은게 너무나 많네요. -정진경

9. 6월 26일

9.1. 내용

  • 다음 주 문제
    • "A Knight's journey" accept해오기, UnEasy Problem 아직 해결 못한사람 해오기

9.2. 풀이

9.3. 후기

  • A Knight's journey 어렵네요 ㅠㅠ 알고리즘 배운지 얼마나 됐다고 리셋이 된거지!?! 왠지 백트래킹을 써야할 거 같지만...잘 못쓰겠는 ;ㅅ; An easy problem 같은 경우 부주의하게 했다가 여러 예외를 고루고루 겪었슴다 ~ㅁ~ㅋ 다음에는 코드 한번 더 살펴보고 넣어야지ㅠㅠ - 강소현
  • 어쩌다보니 다른 글들에 후기를 다 써버렸네요. 삽질하다 진경이의 상큼한 힌트로 UneasyProblem은 An easy problem이 되었네요. 지금 나이트저니 삽질하면서 백트래킹에 대해 자연히(?) 배워가는 중입니다. 반쪽짜리 코드는 구현했으나, 3X4영역에서 H가 나오는... 아직 뭔가 오류들이 산재하는거같네요. 예외처리가 문제인지 배열밖을 다 0으로 처리해서 지정한 배열 밖으로 나가버리는지는 좀 연구해봐야겠어요.. 그리고 다음주에는 부산에 내려갔다 와야해서 참석하지 못할 가능성이 높네요. -김태진

10. 7월 5일

10.1. 내용

  • 다음 주 문제
    • 자유롭게 자기가 풀고 싶은 문제 풀어오기. 단, http://poj.org 에서 첫번째 페이지에 있는 문제는 제외!!
Name Prob.ID Title Comments
권순의 1298 The Hardest Problem Ever The Easiest Problem Ever -ㅅ-
송지원 3117 World Cup 이전에 하려던 RSA 문제에 모순이 있어서 부득이하게 변경함.
김태진 2606 Rabbit hunt 좀 쉬워보이는 기하문제에 도전합니당
김수경 1149 PIGS Cillian Murphy의 초기 출연작 Disco Pigs에서 그의 배역이 Pig라서.
정의정 2970 The lazy programmer 물론 제가 게으르다는 말은 아닙니다.
강소현 2348 Euclid's Game 유클리드! 정보보호 젤 첨 날 나왔던 그 아이
  • 풀다가 모르는 것 있으면 위키에 질문 남기고 자기가 아는 것 답해주기.
  • 다음주에 자기가 풀어온 문제 설명하고 어떻게 풀었는지 설명해야함.

10.2. 질문

10.3. 풀이

10.4. 후기

  • 하루 전날까지 표를 보신 분들은 알겠지만 원래 하려던건 RSA Factorization이었는데 문제가 문제가 있더군요(??). 그래서 어느 조건에 맞춰야 Accept가 될지 알 수도 없고 괜히 168명의 사람들만 도전한거 같지는 않아서 일단은 pass하고 다른 문제를 풀었습니다. 기회가 되면 다음엔 prime을 이용한 문제를 좀 풀어보고 싶어요. 물론 Factorization의 특성상 시간이 오래 걸리는 점이 있어서 좋은 알고리즘을 고안해야 겠지만.. World Cup 문제에 대한 후기는.. 음.. 골라놓고 막 머리싸매고 풀어보니 별거 아닌 문제라 웬지 모임에서 학우들의 원성을 살것만 같은 느낌이에요. 엉엉..ㅠㅠ - 지원
    • 아, 그리고 100만년만에 로그인해보니 An Easy Problem이 Wrong Answer 상태로 남아 있더군요. 다시 풀어봐야겠....-_-;; - 지원

11. 7월 12일

11.1. 내용

  • 다음 주 문제
    • PIGS(1149)와 The lazy programmer(2970) 중에서 하나 풀어오기

11.2. 질문

11.3. 후기

  • 문제가 좀 까다로운 편인데 일찍부터 푼 게 아니라 결국 해결을 못 해왔네요. 다음시간엔 꼭 풀어가야겠다... 비효율적인 방법으로라도. - 김수경
  • 문제는 어려워서 풀지도 못하고, 공부도 안해와서 설명하시는걸 다 이해는 못했지만 저에게는 꽤 의미있는 시간이었습니다;) 앞으로는 일주일동안 틈틈이 공부해서 모르는거 있으면 가져오겠습니다. 앞으로도 꾸준히 일주일에 한번씩 모였으면 좋겠습니다~. - 자경

12. 7월 19일


13. 7월 26일

13.1. 내용

13.2. 후기


14. 8월 2일

14.1. 내용

  • 각자 풀어온 문제 설명하고 풀이 방식 이야기 하기

  • 다음 주 주제

14.2. 후기

  • Soldier 문제가 은근히 어렵네요; 이렇게 하면 되겠지 했는데 -_-;; 각자의 문제 설명들을 들으면서 참 애들이 열심히 하려고 하는구나라는 생각이 들었습니다. 근데 난 -_-;;; 에휴; 틈틈히 풀어봐야겠네요 - 권순의

15. 8월 9일

15.1. 내용

  • Soldiers 계속 풀어보기-_-;;
  • 다들 중복 케이스에서 갯수 세는 부분에서 막힌듯;;
  • 다음주는 새로운 문제를 풀어봅시다.

15.2. 후기


16. 8월 16일

16.1. 내용

  • Soldiers를 풀던가 Lotto를 풀던가.

16.3. 후기

  • 김태진 - 진경이는 저 두문제를 다 풀었습니다. 반면 전 솔져가 너무 어려웠기에... 대체제로 지원누나가 풀려고 하셨던 Lotto에 손을 댔죠. 결과는 accepted! 이번주 화요일에는 진경이한테 덜 까일거 같습니다.. 아마도요.

17. 8월 23일

17.3. 후기

  • 강소현 - 솔져는 왠지 감히 접근할 수 없는 포쓰가 느껴져서 Lotto를 풀었슴다. 담주 화요일 오후 6시부터 10시까지 도서관 팀플룸3을 쓴다고 예약하긴 했는데, 안쓰면 말고 쓰면 쓰고해요 ~ㅁ~ 기숙사 의자 편하고 좋긴한데 혹시 안열까봐 ㅇㅁㅇ..
    • 오~ 센스쟁이~_~ 팀플룸을 빌렸구낭~~~ - 지원
    • 우와 그거 빌릴 수 있군요(당연하잖아) 어떻게 빌리는건지 다음에 물어봐야겠네요~ (2공학관 봉쇄사태....-;) -김태진
  • 송지원 - Soldier를 풀면서 끝내 이해하지 못했던 진경이 코드의 한 for문을 이제서야 설명을 듣고 좀 납득했습니다. 기회가 되면 저도 그런 방법으로 풀어 봐야겠어요~_~ 문제를 하나 고르긴 했는데 잘 풀 수 있을지 모르겠네용. Lotto를 골라놓고 보니 좀 쉬워서 많은 학우들이 풀었는데 이번엔 과연 어떨지....
    • 아, 다음주 모임은 여름방학 마지막 모임이니만큼 2학기 모임 날짜/시간과 향후 일정에 대해 논의해 보아요. 나가서 밥이라도 같이 먹으면 어쩔지 ㅎㅎ
  • 김태진 - 뭔가 문제 고르고 먹고 솔져 설명을 약간 듣고 끝난 느낌이었네요. 라고 생각해보니 Lotto 풀이 방식을 공유해보지 않았군요! (는 다들 비슷하지만 전 코드가 좀 조잡해서..) 요 근래 좀 더 루즈해진 느낌도 있으니 문제푸는건 좀 더 확실히 해와야될거 같아요.
  • 정진경 - 솔저 풀이를 공유를 했으나 로또는 뭐 쉬워서인지 그냥 넘어가버렸네요. 구현 방법에만 차이가 있을 것 같으니 코드 공개만 해도 될 것 같습니다. 후기를 늦게 써서 4문제를 다 억셉트하고 나서 쓰네요. 찝찝한게 2159 Ancient Cipher 문제 조건에서. Substitution Cipher는 '일반적으로' 키가 정수 1개인건가요? 아니면 각 알파벳을 일대일 매칭시키는 배열인가요? 이에 따라 알고리즘이 바뀌는데, 문제 읽고 키가 정수 1개인 것인줄 알고 했는데 제 알고리즘이 틀렸는지 문제를 잘못 이해한건지 WA 왕창 먹고 키가 배열인걸 전제로 하고 알고리즘 짜서 AC... 흑흑 선입견이 문제인가
    • 예제가 단순히 ABC를 CDE처럼 2 더한거로 되어있어서 단순히 substitution cipher 중에서도 시저 사이퍼를 썼으려니 하고 푸는 뻘짓을 한ㅠㅠ 그냥 알파벳을 일대일 대칭하는 거임. 말 그대로 substitution이 대칭이니 ;ㅅ; 간단히 ABC가 RHN으로 변한다 해도 YES가 떠야하는거 ;ㅅ; A->R, B->H, C->N으로 바뀐거지. - 강소현
  • 권순의 - 얼라 이거 안 쓰고 있었네 (흠흠) 솔져는 참.. 어이없게 끝났네요. 결국 마무리도 못하고 -_-;; 이번 문제는 어렵지는 않았는데,, 왜 Presentation Error가 뜨는거지 이러고 있습니다. -_-;;

18. 8월 30일

18.1. 내용

  • 풀었던 문제는 23일에 페이지 추가~

18.2. 후기


19. 9월 8일

19.1. 내용

http://koistudy.net 에서 문제 풀기
  • 시간내에 449, 450, 451번 문제풀기.

19.2. 후기


  • 문제풀이 감이 떨어진거 같습니다. 2시간이 이렇게 짧았나...ㅠㅠ 초등부 문제를 풀었는데 대체로 고도의 수학적 사고나 효율성보다는 주어진 스펙대로 정확히 짜는데에 초점이 맞춰진 것 같습니다.-정진경

20. 9월 19일

20.1. 내용

http://koistudy.net 에서 '기본과정' 혹은 '국내외기출'에 있는 문제 풀기

20.2. 후기


21. 9월 26일

21.1. 내용

21.2. 후기

22. 10월 10일, 17일

22.1. 내용

  • 재귀함수와 백트래킹, Dynamic Programming에 난항을 겪어 최적해구하는 문제에서 고전했습니다.
    • 그래서 정진경군이 157번The tower of Hanoi문제를 풀고, 설명한 후 Mario문제(선형적인 문제)를 풀게하여 연습을 한 후 다시 파닭문제에 도전하게 되었습니다.
  • 145번 기숙사와 파닭 풀어오기

22.2. 후기

  • 김태진 - 파닭문제를 드디어 풀었습니다. 풀기까지 재귀함수 문제들도 풀어보고, Hanoi문제도 풀어보고, Mario문제도 이렇게 풀었다 저렇게 풀었다를 몇시간째, 진경이가 for문으로 Mario를 풀어보라기에 꾸역꾸역풀고나니, !!! 파닭푸는 방법을 알았다! 며 10분만에 해결했습니다.-- 파닭문제 프로젝트를 만든지 1달째인데 푼건 10분도 안걸린.... 네, 아무튼 약속대로 소현이누나가 파닭을 쏘네요+_+!
  • 강소현 - 왜 사람들이 acm 문제 푸는데 자바를 안 쓰는지 알게 되었습니다ㅋ 같은 알고리즘이더라도 속도가 10~100배는 차이나는듯합니다 ㄲㄲ

23. 10월 31일

23.1. 내용

  • 보물찾기 문제 풀기
  • 혹은 Mario를 풀지 못한 사람은 그것부터 차근차근 밟아 나가기...

23.2. 후기

  • 김태진 - 보물찾기를 풀고 있습니다. 우선 테스트케이스 5번까지는 통과를 했지만 6번은 Time Limit Exceeded.. 포인터를 통해서 해보라는 진경이의 힌트를 받고 Search대신 다른 방식으로 할 걸 생각해보고 있습니다.
    • 왜 바꾼거 없이 한번 더 제출했더니 submit일까요;;? 하지만 이중for문으로 해서 뭔가 찜찜했기에 고민고민하다 복잡도n으로 해결봤습니다. ㅇㅅㅇ
    • 나도 여기서 바꾼거 없이 TLE 탈출 성공 했었던것 같은데.. -고한종
      • 가끔 여기가 이상한가보네 ㄷㄷ -강소현

24. 11월 7일

24.1. 내용

  • 세 용액 문제 풀기
  • 혹은 파닭을 풀지 못한 사람은 그것부터 풀기...

24.2. 후기

  • 김태진 - 진경이 출생의 비밀..은 아니고 KOI 은상의 배경이 된, 세 용액이라는 작년 정올 1번문제를 풀어보았습니다. 다들 알고리즘 복잡도는 무시하고 Time Limit Exceeded라도 띄워보자고 짜는데, 이상하게 Wrong Answer.. 값이 int범위에서 해결되지 않아 줄줄 새고 있었습니다-- 범위를 제대로 생각해봐야겠다는 것을 염두함과 동시에 복잡도에 관해서도 좀 더 생각해봐야겠네요.
  • 강소현 - java가 그냥 느리기만 한 것은 아니었어! long 만세~ㅁ~ 하면서 time limit exceeded를 띄웠지요. 자...이제 시간 복잡도를 고려해야 할텐데...결국은 원점으로...ㅠㅠ
  • 김준석 - Special Judge때문에 화난것도 있고. 세 용액 섞기전에 두 용액에서 펑크나는건 분노의 질주=ㅂ= 결국 다른 사이트를 알아보게 됬는데 http://211.228.163.31/ 괜찮아용. Special Judge도 준비되어있고. OK? 다만 여긴 시간제약이 더 빡셈.

25. 11월 14일

25.1. 내용

  • 위성 사진 문제 풀기
  • 세 용액문제는 스페셜저지가 준비중이라 복수정답을 찾아내지 못하고 있습니다. 그래서 패스하기로하고, 약간 다른문제의 인공위성을 풉니다.

25.2. 후기

  • 김태진 - 세 용액문제는 포기하고 진경이가 하자고(해보라고) 찍은 인공위성 문제를 풀었습니다. 우리가 평소에 풀던 배열에 숫자넣고 장난 치는 문제가 아니라 조금 다른 탐색문제였는데요, 이전이라면 못풀었을것만 같았는데 진경이가 이전에 렙업시켜준 덕분에(-_-) 어렵지 않게 풀 수 있었네요. Knight Journey도 이제 풀 수 있을거 같습니다.
  • 김준석 - 재귀로 푼다고했으나 뻘짓을 많이 해서 엄청나게 고생한 문제. 가로 세로가 계산이 안되는거 보니 한물 간것 같습니다. 사실상 세 용액은 실패한것이고 이 문제가 ACM 첫도전이라 재밌었네요 :)
    • 이게 참 열불날때도 많지만 풀면 재밌기도 하죠 ㅎㅎ -김태진

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2013-02-13 07:41:55
Processing time 0.3060 sec