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

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

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

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

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

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

• 오늘 푼 문제
  
  • 곽병학
    
    • 이분법 - crossed ladder
      
    • 스택 - 송신탑
      
  • 김태진
    
    • dp - 티켓
      
    • dp - 레인지
      
  • 권영기
    
    • 17 위상정렬 - topo_sort
      
    • 17 위상정렬 - 다
      

• crossedladder/곽병학
  

• 오늘 푼 문제
  
  • 곽병학
    
    • 
      
  • 김태진
    
    • 계단오르기
      
    • BackTracking문제 1문제
      
  • 권영기
    
    • 헛간
      
    • 
      
• 풀어보기 : land
  

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

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

• 오늘 푼 문제
  
  • 곽병학
    
    • 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
        
    
    

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

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

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

• 시험기간에 의한 휴식기
  

• 문제 풀어오지 못함..
  

• 김태진
  
  • 코드잼_1C라운드: 857등
    
    • Consonants, Pogo, The Great Wall
      

def Solve(x, y):
  N = 0
  sum = 0
  while sum < abs(x) + abs(y) or (sum + x + y) % 2 == 1:
    N += 1
    sum += N
  result = ""
  while N > 0:
    if abs(x) > abs(y):
      if x > 0: 
        result += 'E'
        x -= N
      else:
        result += 'W'
        x += N
    else:
      if y > 0:
        result += 'N'
        y -= N
      else:
        result += 'S'
        y += N
    N -= 1
  return result.reversed()

• 권영기
  
• 곽병학
  

• 김태진 : 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 - 쓸데없을거 같음..
  

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

• 김태진 : DP
  
  • 
    
  • Maximum Sum - kadane's algorithm
    
    • proof - http://prezi.com/fsaynn-iexse/kadanes-algorithm/
      
    • Array에서 특정 subset의 합이 가장 크도록 하는 부분찾기.
      
• 권영기 :
  
  • Topological sort -
    
    • http://homepages.ius.edu/rwisman/C455/html/notes/Chapter22/TopSort.htm
      
    • http://en.wikipedia.org/wiki/Topological_sorting
      
  • Strongly Connected Component(SCC)
    
    • Tarjan's strongly connected components algorithm - 링크
      
      • URL에 '가 들어가면 개고생.
        
• 곽병학 :
  

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

• 참고문제 prime_path http://211.229.66.5/30stair/prime_path/prime_path.php?pname=prime_path
  
  
• 곽병학: 전체 맵에서 각각 독립적인 그래프들 찾기 - 문제점은 알았고 풀어오겠음, 그래프 문제 안풀어오면 저녁
  
• 김태진: gusul/김태진
  

• 완전(교란)순열 - http://ko.wikipedia.org/wiki/완전순열
  
  • !n = (n - 1) * (!(n - 2) + !(n - 1))
    
  • 증명 - http://blog.naver.com/PostView.nhn?blogId=kcg2271&logNo=90064644595
    
• DP 문제 worm/김태진 - 점화식 세울 때 k=0와 k=1, k=2일때를 특히 조심하자. - 걍 여긴 수작업하는게 속편함.
  
• Bar_code 문제 - http://211.229.66.5/30stair/bar_code/bar_code.php?pname=bar_code
  
  • 풀이 - 삼차원 테이블을 사용한 DP문제, d(bar,unit,width)는 bar번째의 bar를 사용하면서, unit의 위치에 그 bar의 폭이 width일 때의 경우이다. 따라서 가능한 모든 바코드의 수를 구하는 것은 d(bar,unit,0 ~ width)를 전부 더해주면 된다.
    
    - 점화식 : d(bar, unit, width) += d(bar - 1,unit - width,l);
    - 점화식을 구하는 것은 금방 구했으나, index를 얻어내는 것이 힘들었음.
    - 설명하면 1110110 이라는 것이 있을 때, 1110110이 오기 전에는 110으로 시작하는 모든 바코드가 있을 것이고, 그 이전에는 10으로 시작하는 모든 바코드가 있을 것이다. 그리고 1110110이라는 바코드가 오기 전에는 111000으로 시작하는 모든 바코드가 있을 것이고, 그 이전에는 11100으로 시작하는 모든 바코드가 있을 것이다. dp테이블에 해당 경우에 대한 경우의 수를 모두 저장해놨기 때문에, 앞에서 부터 차례대로 이전에 올 바코드의 수를 더해나가면 index를 구할 수 있다.
    
  • 풀면서 주의할 점 : dp테이블의 범위에 벗어나는 경우(예를 들어서 음수 번지)가 나올 수 있으므로 이에 대한 처리를 해줘야 한다. 비쥬얼 스튜디오에서 코드를 작성할 때, 테이블 범위에 벗어나도 정답이 나오는 경우가 생겨서 이런 예외를 발견하기 힘들었음..
    

• Algospot배 알고리즘대회
  
• 멘탈파괴당함
  

• Coder's High 2013 (Algospot 알고리즘대회) 풀기
  
  • 링크
    
  • 푼 문제
    
    • 사신도
      
      • 태진 풀이 FOURGODS/김태진
        
    • Jump
      
      • 태진 풀이 JumpJump/김태진
        
    • 째능교육
      
    • Weekly Calendar
      
    • 우주개발의 길은 멀고도 험하다
      
      • 권영기 품
        

• 2012 ICPC대전 문제 풀기 : 링크
  
  • C - Critical 3-path
    
    • 위상정렬, critical path에 대해 공부 및 코딩 - 코드 및 해설은 Fundamental of DataStructure를 참고하자.
      
• 폴리오미노
  
  • DP문제. 태진 풀이 POLY/김태진
    

• 제2회 대학생프로그래밍 대회 동아리 연합 링크
  
• 사각형 2개가 겹치는 지 아닌지 판별하는 방법
  

Ax1은 A사각형의 왼쪽위 x좌표. By2는 B사각형의 오른쪽아래 y좌표
 if Ax1 < Bx1
  if Bx1 > Ax2 && By1 > Ay2
   if By2 > Ay1
    then 겹침
   else 안겹침
  else 안겹침
 else A와 B를 바꿔서 재시도

• Sliding Window Minimum Algorithm - http://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html
  

• 우리의 1년간의 여정은 갑작스럽게 끝이 찾아왔습니다.