본문 바로가기

분류 전체보기

 (83)
수학적 귀납법, 반복문 불변식 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 목차 (눌러서 이동) 수학적 귀납법 반복적인 구조를 갖는 명제의 증명에 유용하게 사용할 수 있다. 먼저, 증명할 사실을 여러 단계로 나누고 그 중 첫 단계에서 증명이 성립함을 보인다. 어떤 한 단계에서 증명이 성립하면, 다음 단계에서도 성립함을 보인다. (단계 나누기 → 첫 단계 증명 → 귀납 증명) 사다리 게임을 예로 들어보자. N 개의 세로줄에 가로 줄을 원하는 만큼 그어도 위, 아래의 선택지가 1:1로 대응됨을 증명한다. 1. 단계 나누기 : N 개의 세로 줄에 가로 줄을 하나씩 그어 간다. 가로 줄을 하나 긋는 것을 한 단계라고 하자. 2. 첫 단계 증명 : 텅빈 N개의 세로 줄..
시간 복잡도에 대해서 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 목차 (눌러서 이동) 반복문이 지배 반복문은 알고리즘의 수행 시간을 지배한다. 따라서, 수행 시간은 보통 반복문의 수행 횟수로 측정한다. 선형 시간과 선형 이하 시간 알고리즘 선형 시간 알고리즘은 수행 시간이 입력 크기에 비례한다. 즉, 입력된 자료를 최소 한 번은 모두 훑어야 하는 프로그램이다. (e.g. 이동 평균 구하기) 선형 이하 시간 알고리즘은 입력의 크기가 커지는 것보다 수행 시간이 느리게 증가한다. (Logarithmic) (e.g. 이분 검색) 다항 시간과 지수 시간 다항 시간 알고리즘은 반복문 수행 횟수를 입력 크기에 대한 다항식으로 표현할 수 있는 알고리즘이다. 지수 ..
코딩과 디버깅 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 목차 (클릭 시 이동) 1. 알고리즘 대회를 위한 코딩 원칙. 간결한 코드 작성 전역 변수를 사용하면 코드가 간결하다. 보통은 안 좋은 습관이지만, 대회 문제는 변수의 사용처가 명확해 대부분 문제가 없다. 또한, 자주 사용되는 코드를 매크로로 작성하면 편하다. 코드 재사용 반복되는 코드는 함수로 분리해 재사용한다. 표준 라이브러리 활용 알고리즘, 자료 구조를 직접 구현하는 것은 시간 낭비다. 표준 라이브러리를 적극 활용하자. 항상 같은 형태로 프로그램 작성 반복적으로 작성되는 코드(이분검색, 너비 우선 탐색 등 유명한 알고리즘) 는 같은 형태로 작성하자. 다만, 처음에는 자신이 알아보기..
문제 해결을 시작하며 ※ 알고리즘 문제해결전략 의 일부를 요약, 정리 하였음. 문제 해결의 과정 1. 문제를 읽고 이해하기 문제가 원하는 바를 공격적으로 완전히 이해하기. 사소한 제약 조건들 놓치지 않기. 2. 재정의와 추상화 재정의: 요구사항의 이해를 위해 자신의 쉬운 언어, 개념으로 풀어 쓰기. 추상화: 복잡한 문제의 본질만 남겨두고 축약, 다루기 쉽게 표현하기. 3. 계획 세우기 해결 방식을 결정, 사용 할 알고리즘과 자료구조를 선택하기. 4. 계획 검증하기 어떤 경우에도 요구 조건을 정확히 수행하는가? 시간, 메모리가 제약 조건에 부합하는가? 5. 계획 수행하기 6. 회고하기 해결 과정을 돌이켜 보기. (효율성, 간결성, 직관성 등.) 코드와 경험을 기록하기. (접근 방식, 해결의 실마리, 오답의 원인.) 못 푼 경우..
[알고스팟] Jump Game - 동적 계획, 메모이제이션 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 점프 게임(링크) 게임판의 각 지점에 적힌 숫자대로 오른쪽 또는 아래로 이동할 수 있으므로 대략 2^(격자 개수) 가지의 경우의 수가 있다.최대 100 x 100개의 칸이 있으므로 모든 칸에서의 도달 가능 여부를 검사하기는 무리다. 그런데 어떤 지점들은 여러 경로로 도달할 수 있다. 즉, 중복으로 계산되는 경로가 있으므로 한번 계산한 경로는 저장하고 필요할 때 꺼내서 사용한다. #include #include using namespace std; // Initial state: -1, NO: 0, YES: 1 int cache[100][100]; int jumpGame(vector board, int y, int x) { int goal = ..
동적 계획법에 대해서, 이항 계수 문제 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 동적 계획법 기본적으로 문제를 작은 문제로 나누어 계산한 것으로 원래 문제의 답을 계산한다. (분할 정복과 같은 접근 방식) 이 과정에서 어떤 부분 문제는 두 개 이상의 더 큰 문제를 푸는데 사용된다. 즉, 같은 계산이 여러번 반복된다. 계산의 중복 횟수는 분할의 깊이가 깊을수록 지수적으로 증가하므로 (Combinational Explosion) 알고리즘의 속도 개선을 위해 꼭 해결해야 한다. 동적 계획법에선는 각 부분 문제의 계산 결과를 저장한 뒤 필요할 때 사용하여 중복 계산을 막는다. 이를 Memoization 이라 하는데, Memoization 은 입력이 고정될 때 결과가 항상 같은 함수에만 적용 가능하다. (참조적 투명 함수, 함수의..
[알고스팟] 울타리 잘라내기 - 분할 정복, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 울타리 잘라내기(링크) 접근 방법 부분적으로 잘라낸 울타리의 최대 크기를 구하기 위해 분할 정복 기법을 사용했다. 주어진 울타리를 나무 판자 한개가 될 때까지 절반으로 분할하면 한개가 된 나무 판자 (한 조각의 부분 문제) 의 크기가 가장 작은 부분 문제의 답(기저 사례)이 된다. 울타리는 항상 절반으로 나누어져 왼쪽, 오른쪽 부분 울타리의 최대 크기를 가져오는데, 울타리를 합쳤을 때 왼쪽과 오른쪽 울타리에 걸쳐서 잘라낼 수 있는 것의 크기도 고려해 더 큰 울타리를 만들 수 있는지 확인해야 한다. 따라서 합치는 과정에서 중간 두개의 나무 판자로부터 양쪽으로 확장해 나가며 현재 왼쪽, 오른쪽 울타리 중 큰 울타리보다 더 큰 울타리를 만들 수 있..
[알고스팟] 쿼드트리 뒤집기 - 분할 정복, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 쿼드트리 뒤집기(링크) 접근 방법 문제에서는 원본의 흑백 그림에 대해 quad tree는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 순서로 알파벳 코드를 작성해 나간다. 윗줄과 아랫줄을 바꾼다고 할 때, 원본 그림에 대해 왼쪽 아래, 오른쪽 아래, 왼쪽 위, 오른쪽 위의 순서로 알파벳 코드를 작성하면 상하 반전이 된 quad tree를 얻을 수 있다. quad tree는 x를 만나면 4개의 알파벳 (4면의 그림) 을 만나게 되니까, 기본적으로 재귀 함수 형태로 작성했다. 재귀 함수의 인자로 문자열 자체를 넘겨 string.substr(1)을 통해 문자를 하나씩 줄여가는 방식을 취하려 했는데 재귀 내부에서의 변화를 함수 탈출 후에도 유지..

티스토리툴바