[수학] 분할정복을 이용한 거듭제곱

수학적 정의를 이용하여 거듭제곱을 하는 방법이다.기존 거듭제곱의 경우, 모두 곱하기 때문에 O(N)의 시간이 걸리지만,분할정복을 이용하면 O(LogN)에 결과 도출이 가능하다. 그냥 단순하게 2, 3등분하여 한방에 구한다는 뜻이다. 재귀함수와 반복문 두 가지 방법으로 구현이 가능하다. 반복문의 경우 코드를 먼저 보자.void powFunc(int a, int b) { int res = 1; while(b) { if (b % 2 != 0) { res *= a; } a *= a; b /= 2; } cout - 2, 3 등분으로 나누기 위해 b가 1이상일 동안 이루어진다.- 만약 홀수인 경우, (위 식 그림에서) 마지막에 C가 추가적으로 곱해지기 때문에, 초기에 곱한다.- 짝수의 경우, 마지..

• format_list_bulleted 📊알고리즘/이론
• · 2024. 5. 1.

[문자열 매칭 알고리즘 #1] KMP 알고리즘

특정 패턴 A를 문자열 B에서 찾는 알고리즘이다. 무식하게 풀수 있는 방법도 존재한다. 이중 for문을 돌면서 첫글자와 일치하는 곳에서 패턴을 돌면서 확인하는 방법이 존재하나 O(N*M) 이기 때문에 매우 비효율적이다. 중복되는 부분을 건너띄고자 KMP 알고리즘은 개발되었다. 접두사 접미사 A B C A 접두사 접미사 A B C B A 접두사 접미사 A B C A B A B C 먼저 접미사, 접두사를 이용하면 중복되는 부분을 해결할 수 있다. 예시를 들어보자 문자열(P): A B C D A B C D A B D E 패턴(T): A B C D A B D 라고 가정해보자. 1 2 3 4 5 6 7 8 9 … T : [ A B C D A B C D A B D E ] | | | | | | X P : [ A B ..

• format_list_bulleted 📊알고리즘/이론
• · 2023. 8. 22.

[ C로 구현하는 ] 그래프

그래프란? 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G=(V, E) 이다. 그래프의 표현 방법 인접 행렬 다음과 같은 그래프를 행렬로 표현해보자 0 1 2 3 4 0 0 1 0 0 1 1 1 0 1 1 1 2 0 1 0 1 0 3 0 1 1 0 1 4 1 1 0 1 0 이렇게 표현이 가능하다. 당연한 얘기지만 무방향성 그래프 (위와 같이 양방향 그래프)는 대각선을 기준으로 대칭을 이루고, 방향성 그래프는 대각선을 기준으로 오른쪽에 나타난다. 인접 리스트 정점 인접 정점 0 1, 4 1 0, 2, 3, 4 2 1, 3 3 1, 2, 4 4 0, 1, 3 이를 링크드 리스트로 구현할 수 있을 것처럼 보인다. 장단점 인접 행렬 - 정점 간의 인접 여부 확인 빠름 - 정점의 크기 X N^..

• format_list_bulleted 📊알고리즘/이론
• · 2023. 8. 8.

[C++] 개행문자 기준으로 입력 받기

알아두어야 할 내용 - getline()은 표준입력 버퍼에 "\n"(계행문자)를 남기지 않는다! 사용 방법 및 원리 과일의 개수 입력 후, banana와 apple을 연속으로 입력하는 프로그램. #include #include int main() { int n; std::cin >> n; string* arr = new string[n]; getline(cin, arr[0]); getline(cin, arr[1]); return 0; } 위 코드에서 n을 입력하고 엔터를 누르면, 엔터("\n")가 표준 입력 버퍼에 입력된다. 따라서, arr[0]에는 "\n"가 입력되는 사태가 발생한다. 그러므로, 우리는 "\n"를 표준입력버퍼에서 삭제해줘야한다. `cin.ignore()`를 이용하자. 수정된 코드는 다음..

• format_list_bulleted 📊알고리즘/이론
• · 2023. 6. 4.

[리스트ADT] 원형 리스트 문제

촛불이 N개 꽃혀있는 케이크에서 k번개씩 건너 뛰면서 촛불을 끌 때, 마지막으로 남아 있는 촛불을 어떻게 될까? [ 배열로 구현 ] int runSimulation(int* arr,int N, int n, int k) { int cur = 0; while (n > 1) { int cnt=1; while (cnt < k) { cur=(cur+1)%N; if (arr[cur] != 0) { cnt++; } } arr[cur] = 0; n--; while (arr[cur] == 0) { cur = (cur + 1) % N; } } return cur; } [ 원형 리스트 ] int runSimulation(Node* list,int N, int n, int k) { Node* cur = list; while ..

• format_list_bulleted 📊알고리즘/이론
• · 2023. 4. 1.

[자료구조] 원형배열 ADT

원형배열이란? 기존 배열은 입력 시, 첫번째 인덱스에 값을 입력 시 뒤에 있는 원소들을 뒤로 밀어내야한다. 이를 해결하기 위해 첫번째 인덱스 앞이 배열에 뒤쪽과 연결되어 있는 앞과 뒤의 입력 및 삭제가 유연한 배열을 만들기 위해 구상된 ADT이다. #include #include void invalidRankException(); void fullListException(); void emptyListException(); int Size(int N, int f, int l); void Get(char* arr, int N, int f, int l, int r); void Set(char* arr, int N, int f, int l, int r, char data); void Add(char* arr,..

• format_list_bulleted 📊알고리즘/이론
• · 2023. 3. 31.