우대비의 블로그

2747번: 피보나치 수 (acmicpc.net) 피보나치는 수는 0과 1로 시작하며 2번째 부터는 앞의 두 수를 더해서 이어 나갑니다.즉 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 --------으로 이어집니다. N번째 피보나치 수를 구하기를 여러번 반복하게 되는 상황에서매번 0부터 N까지 수를 구해나가면 굉장히 비효율 적입니다. 그렇기에 문제를 반복되는 작은 문제로 바꿀 수 있어야합니다.또한 문제들을 DP 테이블에 저장하여 재사용할 수 있게하여 속도를 높여야합니다.(메모이제이션 기법)이러한 것을 동적계획법이라 부르는데 톱-다운 방식과, 바텀-업 방식으로 구현할 수 있습니다.  톱 - 다운 방식#include #include using namespace std;static ..

N개의 수 중 K개를 선택하는 경우의 수를 구하는 방법은 점화식을 구하는 것에서 부터 시작합니다. 5개중 3개를 선택하는 경우의 수 점화식의 경우D[5][3] = D[4][2] + D[4][3]5개중 3개를 선택하는 경우의 수는[4개의 수 중 2개를 선택한 경우의 수 + 4개의 수 중 3개를 선택한 경우의 수] 입니다. = 104개의 수 중 2개를 선택하는 경우의 수는[3개의 수 중 1개를 선택한 경우의 수 + 3개의 수 중 2개를 선택한 경우의 수] = 6 4개의 수 중 3개를 선택하는 경우의 수는[3개의 수 중 2개를 선택한 경우의 수 + 3개의 수 중 3개를 선택한 경우의 수] = 43개의 수 중 3개를 선택하는 경우의 수는[2개의 수 중 2개를 선택한 경우의 수 + 2개의 수 중 3개를 선택한 경..

세그먼트 트리(Segment Tree)구간 쿼리와 수정이 빈번하게 일어나는 상황에서 유용하게 사용할 수 있는 자료구조입니다.배열의 특정 구간에 대한 정보를 빠르게 구하거나 업데이트할 때 사용되며구간의 최소값, 최대값, 합 등을 구할 수 있습니다.세그먼트 트리의 구조세그먼트 트리는 이진 트리 형태로, 각 노드가 배열의 특정 구간을 대표합니다.트리의 루트는 배열의 전체 구간을 대표하고, 각 리프 노드는 배열의 하나의 원소를 대표합니다.내부 노드는 자식 노드의 구간을 합쳐서 더 큰 구간을 대표합니다. 세그먼트 트리의 장점특정 구간에 대한 다양한 연산 결과를 빠르게 구할 수 있습니다.중간 데이터가 변경되어도 전체 구조를 재구축하지 않고 빠르게 반영할 수 있습니다.세그먼트 트리는 주로..

트리 순회(Tree Traversal) 트리 자료구조 내의 모든 노드를 체계적으로 방문하는 과정을 말합니다 이러한 순회는 데이터의 구조적 특성을 분석하거나 특정 연산을 수행하기 위해 사용됩니다. 대표적인 트리 순회 방법으로는 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 가 있습니다. 여기서는 이진 트리를 기준으로 설명하겠습니다. 1. 전위 순회 (Preorder Traversal) 전위 순회는 다음과 같은 순서로 노드를 방문합니다: 현재 노드를 방문한다. 왼쪽 서브트리를 전위 순회한다. 오른쪽 서브트리를 전위 순회한다. 이 방식은 노드를 처리한 후 자식 노드를 순차적으로 처리합니다. 따라서 트리의 루트를 먼저 처리하고자 할 때 유용합니다. 2. 중위 순회 (I..

트라이 (Trie) 자료구조 트라이 자료구조는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다 - 트라이의 형태 -예시 코드 class Node { public: Node* childs[26]; bool isEnd = false; Node() { fill(childs, childs + 26, nullptr); } void insert(const char* key) { if (*key == 0) { isEnd = true; return; } int nextID = *key - 'a'; if (childs[nextID] == nullptr) childs[nextID] = new Node(); childs[nextID]->insert(key + 1); } Node* find(const..

유클리드 호제법은 두 자연수의 최대공약수(Greatest Common Divisor, GCD)를 찾는 알고리즘임 큰 수에 대해서도 빠르게 최대공약수를 계산이 가능 두 자연수 A와 B가 있을 때 (A>B), A를 B로 나눈 나머지를 R이라고 합시다. 이때, A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다. 이 성질을 반복적으로 사용하여 나머지가 0이 될 때까지 과정을 반복합니다. 나머지가 0이 되는 단계에서의 나누는 수가 A와 B의 최대공약수입니다. 예시 #include using namespace std; int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } int main() { int A = 252..

오일러 피 함수 P(N)은 1~ N까지 N과 *서로소인 자연수의 개수를 반환함 *서로소 - 두 수의 최대 공약수가 1인 수 즉, 둘다 소수라는 뜻 - 오일러 피 함수 구현 int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long n; cin >> n; long result = n; for (long p = 2; p 1) result -= result / n; cout 1이라면 n이 가장 큰 소인수, 이 경우, n과 서로소인 수 중 n의 배수를 제외해야 하므로, 마찬가지로 result에서 result− (result / n)​을 수행

병합정렬(Merge Sort)은 분할 정복(divide and conquer) 알고리즘 중 하나로, 주어진 배열을 반으로 나누고, 각 부분 배열을 재귀적으로 정렬하며, 정렬된 부분 배열을 병합하여 전체 배열을 정렬하는 방식입니다. 아래는 병합정렬의 구체적인 과정입니다. 주어진 배열을 반으로 나눕니다. 이때, 배열의 크기가 1 이하가 될 때까지 계속해서 반으로 나누어줍니다. 각 부분 배열을 정렬합니다. 이때, 재귀적으로 정렬을 수행합니다. 정렬된 부분 배열을 병합합니다. 병합할 때는 각 부분 배열의 첫번째 원소를 비교하여 작은 값부터 새로운 배열에 추가해줍니다. 전체 배열이 정렬될 때까지 위 과정을 반복합니다. 아래는 C++ 코드로 구현한 병합정렬 예시입니다. #include #include using n..

선택정렬 가장 작은 수를 선택하여 앞으로 보내는 정렬법 크기가 N인 배열에서의 선택정렬은 가장 작은 수를 찾는 행위를 N번 하게됩니다. 0번 인덱스에 들어갈 가장 작은 수를 1 ~ N번 인덱스에서 찾아서 넣고 1번 인덱스에 들어갈 가장 작은 수를 2 ~ N번 인덱스에서 찾아서 넣고 2번 인덱스에 들어갈 가장 작은 수를 3 ~ N번 인덱스에서 찾아서 넣고 N - 1번 인덱스에 들어갈 가장 작은 수를 N번 인덱스에서 찾아서 넣고 .... #include using namespace std; int arr[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; for (int i = 0; i ..

큐 - FIFO 가장 먼저 들어온 놈이 가장 먼저 나감 우선순위 큐 - 우선순위가 높은 놈 먼저 나감 우선순위 우선순위 큐를 어떻게 구현할까? 우선순위가 가장 높은 애가 먼저 나간다고 했으니까 데이터를 삽입하거나 삭제할때마다 정렬을 해서 가장 앞에 있는 수를 내보내면 되지않을까? 그렇게 한다면 데이터 삽입 or 삭제시마다 정렬하는데 O(N^2)의 시간이 걸리기 때문에 안됨 우선순위 큐는 단순히 가장 큰 or 가장 작은 수를 맨 앞으로만 보내면 되기 때문에 모든 요소를 정렬을 하는 것이 아니라 루트가 가장 큰 값or 작은 값을 가지는 힙 트리를 이용하여 정렬을 함 그렇게 되면 삽입, 삭제하는 과정에서 O(logN)의 속도로 가장 우선순위가 높은 요소를 맨 앞으로 보낼 수 있음 힙 구조를 이용한 우선순위 선..