다락방

2798 블랙잭 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int num, goal, sum,max = 0; cin >> num >> goal; vector num_arr(num); for (int i = 0; i > input; num_arr[i]= input; } for (int i = 0; i < num-2; ++i) { for (int j = i + 1 ;j < num - 1; ++j) { for (int k = j + 1; k < num; ++k) { sum = num_arr[i] + num_a..

11653 소인수분해 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int num, n=2; cin >> num ; while (num > 1) { if (0 == num % n) { num = num / n; cout

10798 세로읽기 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector str_arr(5); string input_string; for (int i = 0; i > input_string; str_arr[i] = input_string; } for (int j = 0; j < 15; ++j) { for (int i = 0; i < 5; ++i) { if (str_arr[i].size()-1 < j) continue; cout

https://www.acmicpc.net/problem/2566 2566 최댓값 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int row = 9, col = 9 ,max =0, idi=0, idj=0; vector ij_arr(row, vector(col)); for (int i = 0; i > input_num; if (input_num > max) { max = input_num; idi = i; idj = j; } } } cout

1436 영화감독 숌 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int input,check_num = 0; cin >> input; int num = 666; while (true) { if (to_string(num).find("666") != string::npos) ++check_num; if (check_num == input) break; ++num; } cout

AVL Tree 자가균형 이진 탐색트리의 한 유형 각 노드의 서브트리 높이 차이가 최대 1을 유지하도록 스스로 균형을 유지하는 트리 이 서브트리의 높이 차이를 균형계수(BalanceFactor, BF)라 한다. 그렇기 때문에 삽입, 삭제 연산을 수행할 때마다 트리의 균형계수를 체크하고, 균형계수가 1보다 커질 때 회전(Rotation) 연산을 통해 균형을 유지한다. 검색, 삽입, 삭제 모두 O(logN) 하지만 삽입, 삭제시마다 회전연산을 수행하기에 연산속도가 느릴 수 있다. 회전연산의 종류 왼쪽 - 왼쪽 오른쪽 - 오른쪽 Single rotation 왼쪽 - 오른쪽 오른쪽 - 왼쪽 double rotation 특징 이진 검색 트리 모든 노드의 두 하위 트리의 높이는 최대 1까지 차이가 난다. 트리의 모..

최장 공통 부분수열(Longest Common Subsequence) 최장 공통 문자열Longest common substring 점화식 if i == 0 or j == 0: LCS[i][j] = 0 elif string_A[i] == string_B[j] LCS[i][j] = LCS[i-1][j-1] + 1 else: LCS[i][j] = 0 동작 문자열 A, 문자열 B의 한 글자씩 비교한다. 두 문자가 다르다면 LCS[i][j]에 0을 표시 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 + 1 위 과정을 반복한다. 이 과정이 성립하는 이유는 공통 문자열은 연속 되어야 하기 때문에 현재 두 문자가 같을 때 두 문자의 앞 글자 까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 ..

동적계획법(DP : Dynamic Programming) 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘 중복 계산을 줄여서 계산속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있다 일반적으로 재귀로 구현되며 메모이제이션(memoization) 기법을 사용하여 중복 계산을 피한다 메모이제이션 - 이전에 계산된 결과를 저장하고 다음에 동일한 계산에 필요할 때 저장된 결과를 이용하여 중복계산을 피함으로서 성능을 향상 시킬 수 있다. 구현단계 문제를 하위 문제로 쪼갠다 하위 문제를 재귀적으로 해결한다 결과를 저장한다(메모이제이션, 테블레이션) 저장된 결과를 이용해 큰 문제를 해결한다. 동적 계획법 조건 최적부분구조(Optimal Substucture) 전..

그리디 알고리즘(Greedy Algorithm) 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론 각 단계에서 최적이라고 생각되는것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘 이다. 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 ‘근시값’을 목표로 하고 있다. 그리디 알고리즘 주요속성 탐욕선택속성(Greedy Choice Property) 각 단계에서 ‘최선의 선택’을 했을때 전체 문제에 대한 최적해를 구할 수 있는 경우 최적부분구조(Optimal Substructure) 전체 문제의 최적해가 부분 문제의 최적해로 구성 될 수 있는 경우 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 다음 이를 조합해 전체 문제의 최적해를 구하는 것을..

Prim 알고리즘 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법 동작 시작 단계에서는 시작 정점만이 MST에 포함 앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 즉, 낮은 가중치를 먼저 선택한다. 위의 과정을 트리가 (N-1) 개의 간선을 가질 때까지 반복한다. 정점선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장트리를 확장하는식