1. Greedy 알고리즘이란?개념- 현재 순간에 최적이라고 생각되는 선택을 반복하며 문제를 해결하는 방식- 과거의 선택이나 미래 결과는 고려하지 않음- 단순해 보이지만, 특정 문제에서는 매우 효율적이고 최적해를 보장함 구조선택 selection : 현재 가장 좋아 보이는 항목 선택유효성 확인 feasibility check: 지금까지 선택한 것들이 전체 해결 가능성 있는지 검사해결 여부 확인 solution check: 현재 선택 집합이 전체 문제의 해인지 확인 예제 - 동전 거스름돈 문제 (coin change problem): 금액 n을 최소 개수의 동전 {25, 10, 5, 1}로 표현하기 ex) 30 -> 25+5 - Brute-force 방식: 가능한 모든 조합 다 시도해보기, 매우느림 -> ..

1. Dynamic Programming의 등장 배경- Divide and Conquer의 한계: 분할 정복은 서로 독립적인 하위 문제를 나눌 때 효과적임. BUT 피보나치 수열처럼 같은 하위문제를 반복적으로 푸는 문제에서는 비효율적ex. F(5) = F(4) + F(3) → F(3) 이 여러번 계산됨 → 중복 계산이 심함 → 비효율적 2. Dynamic Programming의 개념- Bottom-up 방식으로 작은 문제부터 해결해서 결과를 배열에 저장해두고 필요할 때 재사용함.- 이로 인해 중복 계산을 제거하고 성능을 대폭 향상시킴 두 단계 구조재귀적 성질 (recursive property) 정립작은 문제부터 순차적으로 (bottom-up) 해결3. 이항계수 (Binomial Coefficient) ..

1. Divide and Conquer 분할 정복 개념: Divide and Conquer는 문제를 해결하기 위해 다음과 같은 3단계를 거친다.Divide(분할): 문제 인스턴스를 하나 또는 여러 개의 더 작은 인스턴스로 나눈다.Conquer(정복): 작은 인스터스를 재귀적으로 해결한다. → 충분히 작아지면 더 이상 분할하지 않고 직접 해결Combine(결합): 작은 인스턴스의 해를 합쳐서 원래 문제의 해를 만든다.이 방식은 Top-down 접근이며, 재귀적으로 구조화된다. 2. 이진탐색: 대표적인 Divide & Conquer 문제정의- 입력: 정렬된 배열 S (크기 n), 찾을 값 x- 출력: x의 위치 (없으면 0) 수행 방법 배열의 중간값 S[mid]를 기준으로x가 작으면 왼쪽 반, 크면 오른쪽..

1. Algorithms알고리즘이란?알고리즘은 컴퓨터 프로그램을 구성하는 개별 모듈들을 설계하는 것이며, 각 모듈은 정렬 같은 특정 작업을 수행한다.이러한 작업들은 우리가 해결하고자 하는 문제(problem)이고, 문제는 본질적으로 우리가 답을 찾고자 하는 질문이다. 알고리즘은 단순한 아이디어가 아니라 문제를 해결하기 위한 단계적 절차이다.이 절차는 신중하게 설계되어야 하며, 입력을 받아 출력(해결책)으로 변환한다. 문제는 특정 값이 정해지지 않은 parameter(매개변수)를 포함하고 있다.이 parameter에 값을 넣으면 하나의 문제 instance가 된다.즉, 하나의 문제는 다양한 instance의 집합이라 볼 수 있다. 2. 알고리즘 표현 방법C와 같은 구현 언어pseudocode영어 서술중요한..

Search vs Sorting탐색: 원하는 데이터를 찾는 것 (검색)정렬: 데이터를 어떤 기준에 따라 순서대로 배치하는 것 -> 정렬은 탐색을 더 빠르게 하기 위한 사전 작업으로 자주 활용된다. SearchList: 하나 이상의 field로 구성된 record의 집합Key: 각 record를 구분하기 위해 사용하는 field (ex. 학번, ID 등) 1. Sequential Search : 순차 탐색데이터를 왼쪽에서 오른쪽, 또는 그 반대로 하나씩 검사시간 복잡도: O(n)평균적으로 비교되는 키의 수 : List 전체의 절반 정도 -> n/2template int SeqSearch(E *a, const int n, const K& k) { int i; for(i = 1; i n) retu..