컴퓨터 과학에서 어떤 문제가 쉬운지 어려운지, 더 나아가 해결 가능한지 불가능한지를 판단하는 척도가 있다. 바로 P-NP 문제이다. P-NPP-NP는 컴퓨터 과학에서 어떤 문제가 쉬운 문제인지 어려운 문제인지, 더 나아가 해결이 가능한지 불가능한지를 판단하는 척도가 되는 개념이다.결정 문제와 최적화 문제먼저, 문제의 유형을 이해해야 한다.결정 문제 (Decision Problemn)어떤 문제가 주어졌을 때 yes 또는 no로 대답할 수 있는 문제를 말한다."이 배열이 정렬되어 있는가?" → Yes/No"이 그래프에서 A에서 B로 가는 경로가 존재하는가?" → Yes/No 최적화 문제 (Optimization Problem)어떤 상황이 주어졌을 때 최적의 해를 찾는 문제이다."배열을 정렬하라""가장 짧은 ..

같은 계산을 반복하는 것은 비효율적이다. 예를 들어 피보나치 수열에서 fib(5)를 계산할 때, fib(3)을 여러 번 중복 계산한다.한 번 계산한 결과를 저장해두면 훨씬 빠를 것이다.이것이 바로 동적 프로그래밍(Dynamic Programming)의 핵심 개념이다. 동적 프로그래밍 (Dynamic Programming)동적 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다.동적 프로그래밍은 크게 두 가지 방식으로 구현할 수 있다. 메모이제이션타뷸레이션방식하향식 (Top-down)상향식 (Bottom-up)구현재귀 + 캐싱반복문 + 테이블계산필요한 값만 계산모든 값을 미리 계산메모리스택 + 캐시 공간테이블 공간만문제: 피보나치 수열피..

책장에 있는 책들을 키 순서대로 정리한다고 생각해보자. 작은 책부터 큰 책 순서로 나열하는 방법은 여러 가지가 있다.어떤 방법은 간단하지만 느리고, 어떤 방법은 복잡하지만 빠르다. 이것이 바로 정렬 알고리즘이다.정렬 (Sort)정렬은 데이터를 특정 순서대로 배열하는 알고리즘이다.오름차순(작은 것부터 큰 것), 내림차순(큰 것부터 작은 것) 등 다양한 기준으로 정렬할 수 있다.정렬 알고리즘 비교 시간복잡도난이도특징버블 정렬 O(n²)쉬움인접한 원소를 교환선택 정렬 O(n²)쉬움최솟값을 찾아 교환삽입 정렬 O(n²)쉬움적절한 위치에 삽입병합 정렬 O(n log n)어려움분할 정복, 안정 정렬퀵 정렬 O(n log n) ~ O(n²)어려움분할 정복, 실정네서 빠름 버블 정렬 (Bubble Sort)인접한 두 ..