문제 해결 알고리즘 기초/문제 해결에 대해서 (4) 썸네일형 리스트형 수학적 귀납법, 반복문 불변식 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 목차 (눌러서 이동) 수학적 귀납법 반복적인 구조를 갖는 명제의 증명에 유용하게 사용할 수 있다. 먼저, 증명할 사실을 여러 단계로 나누고 그 중 첫 단계에서 증명이 성립함을 보인다. 어떤 한 단계에서 증명이 성립하면, 다음 단계에서도 성립함을 보인다. (단계 나누기 → 첫 단계 증명 → 귀납 증명) 사다리 게임을 예로 들어보자. N 개의 세로줄에 가로 줄을 원하는 만큼 그어도 위, 아래의 선택지가 1:1로 대응됨을 증명한다. 1. 단계 나누기 : N 개의 세로 줄에 가로 줄을 하나씩 그어 간다. 가로 줄을 하나 긋는 것을 한 단계라고 하자. 2. 첫 단계 증명 : 텅빈 N개의 세로 줄.. 시간 복잡도에 대해서 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 목차 (눌러서 이동) 반복문이 지배 반복문은 알고리즘의 수행 시간을 지배한다. 따라서, 수행 시간은 보통 반복문의 수행 횟수로 측정한다. 선형 시간과 선형 이하 시간 알고리즘 선형 시간 알고리즘은 수행 시간이 입력 크기에 비례한다. 즉, 입력된 자료를 최소 한 번은 모두 훑어야 하는 프로그램이다. (e.g. 이동 평균 구하기) 선형 이하 시간 알고리즘은 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가한다. (Logarithmic) (e.g. 이분 검색) 다항 시간과 지수 시간 다항 시간 알고리즘은 반복문 수행 횟수를 입력 크기에 대한 다항식으로 표현할 수 있는 알고리즘이다. 지수 .. 코딩과 디버깅 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 목차 (클릭 시 이동) 1. 알고리즘 대회를 위한 코딩 원칙. 간결한 코드 작성 전역 변수를 사용하면 코드가 간결하다. 보통은 안 좋은 습관이지만, 대회 문제는 변수의 사용처가 명확해 대부분 문제가 없다. 또한, 자주 사용되는 코드를 매크로로 작성하면 편하다. 코드 재사용 반복되는 코드는 함수로 분리해 재사용한다. 표준 라이브러리 활용 알고리즘, 자료 구조를 직접 구현하는 것은 시간 낭비다. 표준 라이브러리를 적극 활용하자. 항상 같은 형태로 프로그램 작성 반복적으로 작성되는 코드(이분검색, 너비 우선 탐색 등 유명한 알고리즘) 는 같은 형태로 작성하자. 다만, 처음에는 자신이 알아보기.. 문제 해결을 시작하며 ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 문제 해결의 과정 1. 문제를 읽고 이해하기 문제가 원하는 바를 공격적으로 완전히 이해하기. 사소한 제약 조건들 놓치지 않기. 2. 재정의와 추상화 재정의: 요구사항의 이해를 위해 자신의 쉬운 언어, 개념으로 풀어 쓰기. 추상화: 복잡한 문제의 본질만 남겨두고 축약, 다루기 쉽게 표현하기. 3. 계획 세우기 해결 방식을 결정, 사용 할 알고리즘과 자료구조를 선택하기. 4. 계획 검증하기 어떤 경우에도 요구 조건을 정확히 수행하는가? 시간, 메모리가 제약 조건에 부합하는가? 5. 계획 수행하기 6. 회고하기 해결 과정을 돌이켜 보기. (효율성, 간결성, 직관성 등.) 코드와 경험을 기록하기. (접근 방식, 해결의 실마리, 오답의 원인.) 못 푼 경우.. 이전 1 다음
