문제해결기법

모든 문제를 해결하기 위해서는 단계적으로 접근하는 것이 중요합니다. 단계적으로 접근해야 개선해야 할 점을 더 쉽게 찾을 수 있기 때문입니다. 문제를 읽고 이해한다.문제를 익숙한 용어로 재정의한다.어떻게 해결할지 계획을 세운다.계획을 검증한다.프로그램으로 구현한다.어떻게

단순한 문제는 직관적으로 해결할 수 있지만 어려운 문제일수록 다양한 방법을 시도해 보며 답을 찾아야 합니다. 아래는 답을 찾는 일반적인 전략들입니다.비슷한 문제를 떠올리면 쉽게 해결할 수 있는 문제들이 있습니다. 비슷한 문제를 떠올리려면 많은 문제를 풀어봐야 합니다.문

우리가 문제를 해결하기 위해 계획을 세울 때 어떤 알고리즘을 쓸 지 결정합니다. 사용할 알고리즘을 결정하면 제한시간 내에 답을 얻을 수 있는지 시간복잡도 분석을 해야합니다. 대부분의 알고리즘에서 가장 많은 시간을 차지하는 부분은 반복문입니다. 알고리즘의 종류는 크게

계산 복잡도 이론은 각 문제의 특성을 공부하는 학문입니다. 여기서 말하는 P는 polynomia, NP는 non-polynomial입니다.다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 합니다.NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에

수학적 귀납법은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법입니다. 귀납법 증명은 크게 세 단계로 나누어집니다.단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눕니다.첫 단계 증명: 첫 단계에서 증명하고 싶은 내용이 성립합을 보입니다.귀납

문제를 해결하기 위한 여러 방법이 있지만 구현 난이도가 가장 낮은 방법은 무식하게 푸는 것입니다. 완전 탐색이라고도 부릅니다. 재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

여러 개의 답 중 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제들을 통칭해 최적화 문제라고 부릅니다. 예를 들어 $n$개의 원소 중에서 $r$개를 순서 없이 골라내는 방법의 수를 계산하는 것은 최적화 문제가 아닙니다. 반면 $n$개의 사과 중에서 $r$개를 골라

분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 냅니다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지

카라츠바의 빠른 곱셈 알고리즘은 분할 정복 알고리즘의 한 예입니다. 정수형 타입으로 나타낼 수 없을 정도로 큰 정수를 곱하는 알고리즘입니다. 정수형 타입으로 나타낼 수 없기 때문에 정수형 배열을 이용해 곱셈을 합니다. 기본적인 곱셈 알고리즘은 산수 시간에 배운 방법을

우리는 재귀 함수의 시간 복잡도를 구하는 것이 쉽지 않다는 것을 알고 있습니다. 팩토리얼이나 병합 정렬같은 재귀 함수는 직관적으로 시간 복잡도를 알 수 있지만 쉬트라센 행렬 곱셈같은 $T(n)=7\\times T({n\\over 2}) + 18\\times({n\\ov

동적 계획법은 중복되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법입니다.동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조

모든 답을 만들어 보고 그중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계합니다.전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿉니다.재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한

탐욕법은 가장 직관적인 알고리즘 설계 패러다임 중 하나입니다. 탐욕법을 이용한 알고리즘, 혹은 '탐욕적인 알고리즘'은 우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리

동적 계획법이나 분할 정복 등의 디자인 패러다임은 적절히 적용될 때는 매우 유용하지만, 모든 문제에 적용할 수는 없습니다. 적절한 분할 방법이 없는 문제를 분할 정복으로 풀 수도 없고, 중복되는 부분 문제가 전혀 없거나 메모리를 너무 많이 사용하는 문제에 동적 계획법을

최적화 문제를 결정 문제로 바꾼 뒤, 이것을 이분법을 이용해 해결하는 방법은 굉장히 유용한 디자인 원칙 중 하나입니다. 결정 문제란 예 혹은 아니오 형태의 답만이 나오는 문제들을 가리킵니다. 최적화 문제의 반환 값은 대개 실수나 정수이므로 답의 경우의 수가 무한한 데

현대의 모든 CPU는 이진수를 이용해 모든 자료를 표현합니다. 이와 같은 디자인 결정은 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 할 수 있기 때문에 가끔 중요할 때가 있습니다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰

부분 합이란 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열입니다. 이 배열을 사용해 특정 구간의 합을 $O(1)$에 구할 수 있습니다. 부분 합을 사용하지 않으면 $O(n)$에 구할 수 밖에 없습니다.구간 합을 빠르게 계산하기 위해서

일렬로 늘어선 같은 종류의 자료 여러 개를 저장하기 위한 가장 기초적인 자료구조는 배열입니다. 동적 배열과 연결 리스트는 배열과 비슷하지만, 배열에서 비효율적이거나 할 수 없는 작업들을 효율적으로 할 수 있도록 도와줍니다.배열의 큰 문제 중 하나는 처음에 배열을 선언할

현실 세계의 규칙을 추상화하는 추상화 자료 구조의 대표적인 예로 큐와 스택, 데크가 있습니다. 이들은 일결로 늘어선 자료들을 표현하는 자료구조로, 여기에 자료를 넣고 꺼내는 연산을 지원합니다. 이때 자료는 특정한 순서로 넣고 특정한 순서로만 꺼낼 수 있습니다. 사실 이

온라인 알고리즘이란 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘을 말합니다. 알고리즘 수행 중 새 입력을 받아 계산을 계속하기 때문에, 입력 전체가 메모리에 올라와 있지 않아도 계산을 시작할 수 있습니다.오프라인 알고리즘이란 입력 전체를 이미

우리는 문제를 해결하기 위해 수학의 '집합' 개념을 이용할 수 있습니다. 집합은 여러 가지 방식으로 표현할 수 있습니다.집합에 대한 대표적인 연산으로 검색, 삽입, 삭제가 있습니다. 만약 집합을 배열로 구현한다면 검색은 $O(n)$, 삽입은 $O(1)$, 삭제는 $O(