More actions
imported>jereneal20 No edit summary |
imported>jereneal20 No edit summary |
||
| Line 224: | Line 224: | ||
* [http://www.algospot.com/judge/problem/read/POLY 폴리오미노] | * [http://www.algospot.com/judge/problem/read/POLY 폴리오미노] | ||
** DP문제. 태진 풀이 [[POLY/김태진]] | ** DP문제. 태진 풀이 [[POLY/김태진]] | ||
== 8월 21일,8월 28일 == | |||
* 제2회 대학생프로그래밍 대회 동아리 연합 [http://algospot.com/judge/problem/list/?source=제%202회%20전국%20대학생%20프로그래밍%20대회%20동아리%20연합%20대회 링크] | |||
* 사각형 2개가 겹치는 지 아닌지 판별하는 방법 | |||
Ax1은 A사각형의 왼쪽위 x좌표. By2는 B사각형의 오른쪽아래 y좌표 | |||
if Ax1 < Bx1 | |||
if Bx1 > Ax2 && By1 > Ay2 | |||
if By2 > Ay1 | |||
then 겹침 | |||
else 안겹침 | |||
else 안겹침 | |||
else A와 B를 바꿔서 재시도 | |||
---- | ---- | ||
[[2013년활동지도]] | [[2013년활동지도]] | ||
Revision as of 02:47, 28 August 2013
목표
- 김태진, 권영기, 곽병학 팀 : 동상 (본선 학교순위 10위 이내)
- 참여를 원하는 분을 위한 문은 언제나 열려있습니다.
진행 방식
- 각자 문제를 풀어오고 설명, 설명들은 문제는 다음 시간까지 개인적으로 풀어올 것.(Dovelet 사용)
방학 중
- 시간 - 매주 목 오후 5시.
- 장소 - 6층 PC실
- 방식 - 각자 문제를 풀어와서 토의하고, 다음 문제를 정합니다.
스터디
1월 10일
내용
풀이
- sort/권영기
- subsequence/권영기 - 부분 구간, 건조, 공격적인 소 문제 코드 모두 있어여. 근데 소스 공개하기 부끄럽네..
1월 18일
내용
- 참가자 : 김태진, 권영기, 곽병학
- 오늘 푼 문제
- 김태진
- dynamic programming - 부분 합
- greedy method - 거스름돈, 발아
- 곽병학
- bisection - crossed ladder
- queue - 도망 간 소를 잡아라
- 권영기
- graph, dfs - 단지 번호 붙이기, orders, 짝 짓기, 슈퍼 소수, 달팽이
풀이
1월 24일
내용
*권영기
- 17 위상정렬 - topo_sort
- 17 위상정렬 - 다
풀이
2월 13일
내용
- 참가자 :
- 오늘 푼 문제
- 곽병학
- 김태진
- 계단오르기
- BackTracking문제 1문제
*권영기
- 풀어보기 : land
풀이
2월 20일
내용
- 참가자 :
- 오늘 푼 문제
- 곽병학
- 김태진
- 헛간(저번주 문제)
- n 마리의 쥐가 크기가 같은 n 개의 버터를 먹는데 n 시간이 걸린다고 할 때 , m 마리의 쥐가 m 개의 버터를 먹는데 걸리는 시간을 구하는것이 문제이다. 각각의 쥐가 치즈를 먹는 속도는 모두 동일하다고 한다.
*권영기
- 풀어보기 : land
풀이
2월 27일
내용
- 참가자 :
- 오늘 푼 문제
- 개강 이후에는 매주 수요일 6시에 스터디 시작하기로 결정, 격주로 토요일에도 만나기로 함.
- inflate 모르겠다 알려줘
풀이
3월 6일
내용
- 참가자 :
- 오늘 푼 문제
- 곽병학
- pongdang, align, us
- 김태진
- jumping_cow
- 권영기
풀이
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]
- 권영기 :
- 곽병학 :
7월 11일
Need to Discuss
내용
- 김태진 : Dynamic Programming
- KnapsackProblem/김태진 : 0/1냅색 문제 이제 좀 이해했음다..
- 곽병학 : 한붓그리기?
- 권영기 : ?
7월 16일
Need to Discuss
내용
- 참고문제 prime_path [4]
- 곽병학: 전체 맵에서 각각 독립적인 그래프들 찾기 - 문제점은 알았고 풀어오겠음, 그래프 문제 안풀어오면 저녁
- 김태진: gusul/김태진
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))
- 증명 - 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테이블의 범위에 벗어나는 경우(예를 들어서 음수 번지)가 나올 수 있으므로 이에 대한 처리를 해줘야 한다. 비쥬얼 스튜디오에서 코드를 작성할 때, 테이블 범위에 벗어나도 정답이 나오는 경우가 생겨서 이런 예외를 발견하기 힘들었음..
- 풀이 - 삼차원 테이블을 사용한 DP문제, d(bar,unit,width)는 bar번째의 bar를 사용하면서, unit의 위치에 그 bar의 폭이 width일 때의 경우이다. 따라서 가능한 모든 바코드의 수를 구하는 것은 d(bar,unit,0 ~ width)를 전부 더해주면 된다.
7월 28일
- Algospot배 알고리즘대회
- 멘탈파괴당함
7월 30일,8월 6일,8월 8일
- Coder's High 2013 (Algospot 알고리즘대회) 풀기
- 링크
- 푼 문제
- 사신도
- 태진 풀이 FOURGODS/김태진
- Jump
- 태진 풀이 JumpJump/김태진
- 째능교육
- Weekly Calendar
- 우주개발의 길은 멀고도 험하다
- 권영기 품
8월 13일,8월 15일
- 2012 ICPC대전 문제 풀기 : 링크
- C - Critical 3-path
- 위상정렬, critical path에 대해 공부 및 코딩 - 코드 및 해설은 Fundamental of DataStructure를 참고하자.
- 폴리오미노
- DP문제. 태진 풀이 POLY/김태진
8월 21일,8월 28일
- 제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를 바꿔서 재시도