ACM ICPC/2013년스터디

목표

• 김태진, 권영기, 곽병학 팀 : 동상 (본선 학교순위 10위 이내)
• 참여를 원하는 분을 위한 문은 언제나 열려있습니다.

진행 방식

• 각자 문제를 풀어오고 설명, 설명들은 문제는 다음 시간까지 개인적으로 풀어올 것.(Dovelet 사용)

방학 중

• 시간 - 매주 목 오후 5시.
• 장소 - 6층 PC실
• 방식 - 각자 문제를 풀어와서 토의하고, 다음 문제를 정합니다.

스터디

1월 10일

내용

• 참가자 : 김태진, 권영기, 곽병학
• 2013년 스터디 시작!
  • 작년 방식하고 똑같습니다.
• 오늘 푼 문제
  • 김태진
  • queue - 소수 길
  • 곽병학
  • dynamic programming - 끼리끼리
  • 권영기
  • linked list - josephus
  • 퀵 정렬,이진검색,parametric search - 숫자 추측하기, 세 값의 정렬, 부분 구간, 건조, 공격적인 소

풀이

• sort/권영기
• subsequence/권영기 - 부분 구간, 건조, 공격적인 소 문제 코드 모두 있어여. 근데 소스 공개하기 부끄럽네..

1월 18일

내용

• 참가자 : 김태진, 권영기, 곽병학
• 오늘 푼 문제
  • 김태진
  • dynamic programming - 부분 합
  • greedy method - 거스름돈, 발아
  • 곽병학
  • bisection - crossed ladder
  • queue - 도망 간 소를 잡아라
  • 권영기
  • graph, dfs - 단지 번호 붙이기, orders, 짝 짓기, 슈퍼 소수, 달팽이

1월 24일

내용

• 참가자 : 김태진, 권영기, 곽병학
• 오늘 푼 문제
  • 곽병학
  • 이분법 - crossed ladder
  • 스택 - 송신탑
  • 김태진
  • dp - 티켓
  • dp - 레인지

 *권영기

• • 17 위상정렬 - topo_sort
  • 17 위상정렬 - 다

풀이

• crossedladder/곽병학

2월 13일

내용

• 참가자 :
• 오늘 푼 문제
  • 곽병학
  • 김태진
  • 계단오르기
  • BackTracking문제 1문제

 *권영기

• • 헛간
• 풀어보기 : land

2월 20일

내용

• 참가자 :
• 오늘 푼 문제
  • 곽병학
  • 김태진
  • 헛간(저번주 문제)
  • n 마리의 쥐가 크기가 같은 n 개의 버터를 먹는데 n 시간이 걸린다고 할 때 , m 마리의 쥐가 m 개의 버터를 먹는데 걸리는 시간을 구하는것이 문제이다. 각각의 쥐가 치즈를 먹는 속도는 모두 동일하다고 한다.

 *권영기

• 풀어보기 : land

2월 27일

내용

• 참가자 :
• 오늘 푼 문제
  • 곽병학
  • inflate
  • 김태진
  • 권영기
  • Binary Indexed Tree
  • Up Sequence
  • moblie
• 개강 이후에는 매주 수요일 6시에 스터디 시작하기로 결정, 격주로 토요일에도 만나기로 함.
• inflate 모르겠다 알려줘

3월 6일

내용

• 참가자 :
• 오늘 푼 문제
  • 곽병학
  • pongdang, align, us
  • 김태진
  • jumping_cow
  • 권영기
    • Up Sequence
      • Time Complexity O(n log n) 의 Up Sequence
      • bridging - binary indexed tree를 이용한 Up Sequence 문제
      • tower, align, tile_up_block, koi_cpaper, buy_lower

3월 13일

내용

• • 곽병학
  • catch_cow
  • 김태진
  • 아군살리기
  • 권영기

3월 20일

내용

• 코드포스 문제풀기
  • 284회vol2.
  • A,B번 풀었음

3월 24일

내용

• 코드포스 복기
  • C번은 예상대로 쉽게 푸는 방법이 있었음
  • D번은 풀이법에 대한 실마리가 제시되어 각자 코딩할 계획

4월

• 시험기간에 의한 휴식기

5월 8일

• 문제 풀어오지 못함..

5월 15일

내용

• 김태진
  • 코드잼_1C라운드: 857등
  • Consonants, Pogo, The Great Wall
• 권영기
• 곽병학

6월 27일

• 김태진 : Dynamic Programming 6.1~6.3
  • Shortest Path : DAG(directed acyclic graphs)로 바꾼 후 Source에서부터 dist(v) = min{dist(v) + l(u,v)}사용
  • 170p
  • Longest increasing subsequence : DAG로 바꾼다.(increasing하는 곳에만 edge생성됨) 이후 가장 많이 방문하도록 L(j) = 1+ max{L(i) : (i,j)}수행
  • 최대 path의 길이를 구한 후에 뒤로 돌아가면서 숫자가 줄어드는 녀석들을 스택에 담으면 path도 구할 수 있다.
  • Edit distance : 글자 최소 오류개수 구하기 (exponential과 polynomial의 최소 오류는 6개.)
  • Similar to DTW
• 권영기 : 3장 그래프
• 곽병학 : Hoffman code - 쓸데없을거 같음..

7월 4일

Need to Discuss

• Stack부분에서 Histogram 문제
• BFS 효율적 구현

내용

• 김태진 : DP
  • Maximum Sum - kadane's algorithm
    • proof - [1]
• 권영기 :
  • Topological sort -
    • [2]
    • [3]
  • Strongly Connected Component(SCC)
    • Tarjan's strongly connected components algorithm - 링크
    • URL에 '가 들어가면 개고생.
• 곽병학 :

7월 11일

내용

• 김태진 : Dynamic Programming
  • KnapsackProblem/김태진 : 0/1냅색 문제 이제 좀 이해했음다..
• 곽병학 : 한붓그리기?
• 권영기 : ?

7월 16일

내용

• 참고문제 prime_path [4]

• 곽병학: 전체 맵에서 각각 독립적인 그래프들 찾기 - 문제점은 알았고 풀어오겠음, 그래프 문제 안풀어오면 저녁

7월 25일

• 완전(교란)순열 - http://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97%B4
  • • • • • • • • • !n = (n - 1) * (!(n - 2) + !(n - 1))

---

2013년활동지도