Algorithm7 DFS(깊이 우선탐색) 깊이 우선탐색이란? 그래프를 탐색할 때 쓰이는 알고리즘 특정한 노드에서 가장 멀리 있는 노드를 먼저 탐색하는 알고리즘 주어진 맵전체를 탐색하며 한번 방문한 노드는 다시 방문하지 않는다. // 수도코드 DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) 어떠한 정점 u의 visited를 참으로 바꾸고 u로부터 연결되어 있는 v지점을 탐색한다. 방문되어 있지 않은 노드에 대해 재귀적으로 DFS를 호출. 1번 노드에서 시작하여 4번노드까지 가장 멀리 떨어져있는 정점까지 방문한 다음 그 다음 정점들을 차례로 방문한다. DFS 구현방법 - 1 void dfs(int here){ visited[here] = 1; for(in.. 2022. 6. 24. Prefix sum(누적합) 누적합이란 미리 요소들의 합을 저장해 두는 누적된 수의 합 앞에서 부터 더하는 prefix sum 뒤에서 부터 더하는 suffix sum 구간에 대한 많은 쿼리가 나올때 생각해야 할 것이 트리와 누적합 구간 내의 요소가 변하지 않는 정적요소인 경우 누적합을 사용한다. A 1 2 3 4 psum[1] O psum[2] O O psum[3] O O O psum[4] O O O O 1 3 6 10 예제) N개의 카드를 주고 M개의 경우의 관하여 A번째부터 B번째까지의 합을 구하라 입력 수의 개수 N, 합을 구해야하는 횟수 M, 그 이후에 N개의 숫자가 주어진다. 수는 100이하의 자연수 그 이후 M개의 줄에 합을 구해야하는 구간 A,B가 주어진다. 출력 M개의 줄에 A부터 B까지의 합을 구하라 범위 1 b >.. 2022. 6. 20. Recursion Function(재귀 함수) 재귀함수란? 함수를 정의할 때 자신을 재참조하는 함수 계속해서 자기 자신의 함수를 호출하며 같은 로직을 반복해나가고 인덱스를 변화시켜 진행되는 문제에서 사용 ex) 피보나치 F(0) = 0, F(1) = 1 이며 N>=2일 때 F(N) = F(N-1) + F(N-2) 코드로 구축했을 때 #include using namespace std; int fibo(int idx){ if(idx == 0 || idx == 1) return idx; return fibo(idx - 1) + fibo(idx - 2); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout 2022. 6. 20. Time Complexity(시간 복잡도) 시간복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 알고리즘의 로직이 얼마나 오랜 시간 걸리는지 나타내는데 사용 보통 빅-오 표기법으로 표시 ex) 입력크기 n에 대하여 모든 입력에 대한 알고리즘에 필요한 시간이 "8n^2 + 2n" 이라면 다음과 같은 코드로 표현 가능 for(int i = 0; i O(2^n) > O(n!) 자료구조에서의 시간복잡도 STL에서의 시간 복잡도 sort() : nlogn find() : n fill() : n unique() : n lower_bound(), upper_bound() : nlogn 2022. 6. 20. Selection Sort(선택 정렬) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다. 키값과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다. # include # define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) ) # define MAX_SIZE 5 void selection_sort(int list[], int n){ // 선택 정렬 int i, j, least, temp; for(i=0; i 2022. 6. 14. GCD(최대공약수), LCM(최소공배수) C++ 구현 최대공약수(GCD, Great Common Divisor)과 최소공배수(LCM, Least Common Multiple)을 구해보자 최대 공약수 최대공약수는 나머지 연산을 활용하는 유클리드 호제법을 이용하여 쉽게 구할 수 있다. 입력으로 들어온 두 수 a,b에 대하여 b = a*k +r이라 표현하면 a,b의 최대 공약수는 a,r의 최대공약수와 같다는 원리를 이용한다. 1) 반복문을 사용 int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; } 2) 재귀함수 사용 int gcd(int a, int b){ if(b == 0) return a; // b == 0 인경우 더 이상 최대 공약수를 갖지 않아서 a 반환 el.. 2022. 6. 14. Bubble Sort(버블 정렬) 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 두 원소를 선택하여 비교하고 왼쪽이 오른쪽보다 크면 swap하며 바꾼다. 배열 내 전체 원소가 오름차순으로 정렬될 때까지 과정을 반복한다. # include # define MAX_SIZE 5 void bubble_sort(int list[], int n){ // 버블 정렬 int i, j, temp; for(i=n-1; i>0; i--){ // 0 ~ (i-1)까지 반복 for(j=0; j 2022. 6. 13. 이전 1 다음
