Algorithm

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 더보기 이름에 의미부여 하지 말자.... 다이나믹 = 아무 의미 없음 목차 다이나믹 프로그래밍을 이용해 풀 수 있는 문제의 특징 다이나믹 프로그래밍 구현 방법 다이나믹 프로그래밍 문제 풀이법 다이나믹 프로그래밍 문제 유형 ▶ 다이나믹 프로그래밍을 이용해 풀 수 있는 문제의 특징 1. 중복되는 부분 문제 → 동일한 작은 문제를 반복적으로 해결해야함 ex) 피보나치 수 F0 = 0 F1 = 1 Fn(큰문제) = Fn-1(작은문제) + Fn-2(작은문제) // 점화식을 반복적으로 해결해야 함 2. 최적 부분 구조 → 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다 ex) 피보나치 수 F0 = 0 F1 = 1 Fn(큰문제) ..

나머지 연산 최대공약수 / 최소공배수 (유클리드 호제법) 소수 (에라토스테네스의 체) 팩토리얼에서 0의 갯수 구하기(소인수분해) 조합에서 0의 갯수 구하기(소인수분해) ▶ 나머지 연산 (A + B) % M = (A%M + B%M) % M (A * B) % M = (A%M * B%M) % M : 뺄셈의 경우 A%M - B%M가 음수가 나올수도 있으므로 M을 더해준다 (A - B) % M = (A%M - B%M + M) % M : 성립하지 않는다 ! ▶ 최대공약수(GCD) / 최소공배수(LCM) 최대공약수 : A, B 두 수의 공통된 약수중에 가장 큰 수 최소공배수 : 두 수의 공통된 배수 중에 가장 작은 정수 ⊙ 최대공약수 구하기 int g = 1; for (int i=2; i

그래프를 탐색하는 알고리즘 [깊이 우선 탐색(DFS)] 이름처럼 한길만 깊이 파고드는 알고리즘이다 (depth) 1. 하나의 정점에서 다른 하나의 정점만 탐색한다(한 사람에게만 연락한다) 2. 스택을 이용하여 경로를 되돌아간다★ 3. 처음 탐색을 시작한 정점의 위치에서 탐색은 끝이 난다 ▶ DFS의 구현 스택 : 경로 정보의 추적을 목적 (내가 이미 탐색을 완료해서 탐색할 기회를 다른 정점에게 넘긴 애들만 들어옴) 배열 : 방문 정보의 기록을 목적 그래프 구현한 내용에서 DFS 탐색 기능(스택+연결리스트)만 추가 정점의 이름 // 정점의 이름들을 상수화 enum {A, B, C, D, E, F, G, H, I, J}; 그래프를 표현한 구조체 (탐색이 완료된 정점의 정보 추가 by 배열) typedef s..

▶ 재귀 문제를 풀 때 생각의 흐름 반복되는 작업을 찾는다 (반복되는 부분은 재귀함수나 반복문으로 해결할수 있다) 반복되는 작업을 함수로 생각하고 input과 output의 형식을 각각 정한다 (output이 있을 경우 이 output이 다음번 input으로 사용될 수 있다) input은 한단계씩 점진적으로 변한다 (보통 크기나 길이가 줄어든다) 종료 조건을 설정한다 ▶ 재귀 문제 TIP 1. 문제의 정의를 명확히 표기한다 (ex. 피보나치 수열이란 어떤 수열의 항 = 앞의 두항의 합) 2. 종료조건을 정확히 설정한다 3. 재귀는 목적만 설정해주는 디클래러티브적 프로그래밍 (선언적 프로그래밍) 을 해야한다는것을 인지하자 4. 내가 생각한 컴퓨터가 알아서 슈슉 돌리고 결과를 짠하고 보여주는것은 불가능함 저..