편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
본격적으로 알고리즘을 종류별로 다룬다. 각 알고리즘을 적용하는 간단한 예시와 연습문제를 제공하니 풀어보면서 이해하는 것이 좋다. 연습문제는 acmicpc.net의 것을 링크한다. [[KOI]] 같은 경시대회를 대비하는데 도움이 될 수도..? | 본격적으로 알고리즘을 종류별로 다룬다. 각 알고리즘을 적용하는 간단한 예시와 연습문제를 제공하니 풀어보면서 이해하는 것이 좋다. 연습문제는 acmicpc.net의 것을 링크한다. [[KOI]]같은 경시대회를 대비하는데 도움이 될 수도..? | ||
== 알고리즘의 정당성 증명 == | == 알고리즘의 정당성 증명 == | ||
갑자기 웬 뜬금없이 증명이 튀어나왔는지 궁금할 것이다. 당연하지만, 우리는 천재가 아니라서 머릿속으로 생각한 알고리즘이 실제로 아주 잘 돌아간다고 보장할 수 없기 때문에 생각해낸 알고리즘이 문제를 풀 수 있다는 것을 보여야 한다. | 갑자기 웬 뜬금없이 증명이 튀어나왔는지 궁금할 것이다. 당연하지만, 우리는 천재가 아니라서 머릿속으로 생각한 알고리즘이 실제로 아주 잘 돌아간다고 보장할 수 없기 때문에 생각해낸 알고리즘이 문제를 풀 수 있다는 것을 보여야 한다. | ||
189번째 줄: | 188번째 줄: | ||
문제를 쓸데없이 어렵게 접근하여 골치아파하지 말고 이 방법을 가장 먼저 적용하자. 이 방법도 나쁜 방법이 아니며, 준수한 성능을 내는 알고리즘을 설계할 수 있는 좋은 방법이다. | 문제를 쓸데없이 어렵게 접근하여 골치아파하지 말고 이 방법을 가장 먼저 적용하자. 이 방법도 나쁜 방법이 아니며, 준수한 성능을 내는 알고리즘을 설계할 수 있는 좋은 방법이다. | ||
다만 이 방법을 쓰려 한다면, 리소스를 많이 써먹을 수 있는 | 다만 이 방법을 쓰려 한다면,리소스를 많이 써먹을 수 있는 프로그렘을 짤 수 있다는 전제조건이 따라붙는다. 크고 아름다운 성능을 이용하려 해도 싱글코어밖에 못 쓰는 프로그렘이라면 빛이 바랠 것이다. | ||
== 분할 정복 == | == 분할 정복 == | ||
199번째 줄: | 198번째 줄: | ||
미리 모든 필요한 데이터들을 DP Table에 채워넣고 거기서 값을 뽑아서 계산하고 출력하는 방식이다. 스택 오버플로우가 날 일이 없어지고, 수행 시간이 줄어들며 토글링을 적용할 수 있다는 장점이 있다. | 미리 모든 필요한 데이터들을 DP Table에 채워넣고 거기서 값을 뽑아서 계산하고 출력하는 방식이다. 스택 오버플로우가 날 일이 없어지고, 수행 시간이 줄어들며 토글링을 적용할 수 있다는 장점이 있다. | ||
== 탐욕법 == | == 탐욕법 == | ||
그리디 알고리즘 또는 욕심쟁이 알고리즘 등으로도 불리운다. 현재 봤을 때 가장 | 그리디 알고리즘 또는 욕심쟁이 알고리즘 등으로도 불리운다. 현재 봤을 때 가장 최적해같아 보이는 것을 선택하는 알고리즘이다. 근사해를 구할 때 쓰이면 가장 좋으나, 최적해를 구할 때에는 역추적을 해야만 한다. 가장 사람을 잘 흉내내는 알고리즘이다.{{--|이런 욕심쟁이들.}} | ||
== 파라매트릭 서치 == | == 파라매트릭 서치 == | ||
290번째 줄: | 289번째 줄: | ||
{{각주}} | {{각주}} | ||
[[분류:수학인듯 과학아닌 공학같은 컴퓨터과학]] | [[분류:수학인듯 과학아닌 공학같은 컴퓨터과학]] | ||
[[분류:컴퓨터 과학]] | [[분류:컴퓨터 과학]] |