Programming Challenge! AS2008 Ted Programming Challenge!
발표자 소개 Generalist AnD Study 열심멤버3레벨 안준석(Ted)
오늘 할 이야기
CyberJJ님 2008 Book Award! * 본 PT 에서는 좀 더 쉽게 재미에 다가설수 있 도록 안내만 해 드립니다. ^^
책 소개 기간 2008.01.12 시작 2008.05.03 끝 14주 문제 풀이 36개
책 들여다보기 자료구조 문자열 정렬 계산과 대수 조합론 정수론 백트래킹 그래프 순회 그래프 알고리즘 동적 프로그래밍 격자 기하 계산기하
ACM 문제 양식
Introduce 스터디 소개
Online Judge
문제 고르기
문제 풀이 과정 Online
문제 풀이 과정 Offline 부작용-기억에 의존한 풀이
Insight 소가 뒷걸음질치다 쥐 잡다? 일을 시작하기 위해 기분이 내킬 때까지 기다리는 따위의 짓을 하지 않으려면 시험 제도는 좋은 훈련이 된다. – 아놀드 토인비
소가 뒷걸음질 쳐서 쥐 잡는 일은 없었다 그 만큼 Solved 는 기뻤지요~
끌개 찾기, 깔끔하게 코딩하기, TDD 시행 착오 무작정 생각 없이 달려들면.. 맨땅에 헤딩 하고.. 달릴 수 있는것은 Break 가 있기 때문
닭 잡는데 소 잡는 칼 왼손은 거들뿐. 괜히 갓 배운 알고리즘 사용하려다가 낭패 기본적인 조작이 중요
수학은 좋은 도구다
발상과 표현 표현 기법은 생각을 더욱 풍부 하게 한다.
Algorithm 재귀와 동적프로그래밍
에셔의 ‘그림 그리는 손’ 80%
간단한 예 피보나치 수열 1 1 + 1 = 2 1 + 2 = 3 2 + 3 = 5 3 + 5 = 8 f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1
재귀 공부 하기 자신과 성격은 똑같지만 크기만 다른 문제와의 관계를 통해 문제의 구조를 파악하는 것. 이것이 재귀적 접근 자신과 성격은 똑같지만 크기만 다른 문제와의 관계를 통해 문제의 구조를 파악하는 것. 이것이 재귀적 접근 재귀가 제대로 작동하기 위해서는 어떤 문제에 포함되어 있는 동일한 문제는 원래 문제보다 크 기가 작아야 한다. 연속적인 재귀 호출의 끝에는 항상 재귀적 순환 을 끝내는 경계조건에 대한 정의가 있어야 한다.
재귀 사용해 보기 피보나치 수열 fib(n) { if (n=1 or n=2) then return 1; else return (fib(n-1) + fib(n-2)); } ② ①
중복 호출로 심각한 비효율 발생 fib(7) fib(6) fib(5) fib(4) fib(4) fib(3) fib(3)
중복을 줄이려면? 큰 문제의 해답에 작은 문제의 해답이 포 함되어 있고 이를 재귀호출 알고리즘으로 구현하면 지 나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법이 필요하 다.
동적 프로그래밍 최적 부분 구조를 이룬다. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다. 다음 두 성질을 가지고 있는 문제 대해 적절한 저장 방법으로 중복 호출의 비효율을 제거한 것을 동적 프 로그래밍이라 한다. 최적 부분 구조를 이룬다. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.
동적 프로그래밍 피보나치 수열 fib(n) { f[1] <- f[2] <- 1 for i<-3 to n f[i] <- f[i-1] + f[i-2]; return f[n]; } Dynamic 용어의 유래는 원래 제어 분야에서 해를 테이블에 저장해가면서 풀어나간다는 데서 유래했다고 한다. 영어든 한국어든 어울리지 않음.
생각의 틀 만드는 훈련을 했다 이 책에서 배운 가장 큰 배움 문제 해결 포인트 알고리즘 도구 재귀로 피보나치 수열 구하면 느리다 해결 포인트 중복을 제거한다 알고리즘 도구 동적 프로그래밍 생각의 틀 만드는 훈련을 했다
문제 소개 Algorithm/Stacks of Flapjacks - 팬 케이크 암기해서 풀려고 함 Algorithm/Expressions - 표현식 재귀 동적프로그래밍
또 다른 도전! TopCoder
생각하는 방법을 터득한 것은 미래의 문제 를 미리 해결한 것이다 사실을 많이 아는 것보다는 이론적 틀이 중요하고, 기억력보다는 생각하는 법이 더 중요하다 – 제임스 왓슨
감사합니다! 2009.01.10 Ted