순열, 조합 알고리즘은 코딩테스트에서 빈번하게 출제 된다. 그럼에도 항상 마주치면 구글링을한다.. 따라서 오늘 순열, 조합 완벽하게 이해하고 끝내보려고 한다. 조합 재귀 구현 조합의 수도코드는 다음과 같다. 배열 [1, 2, 3, 4] 에서 3개를 선택하는 조합을 구할때 1을 고정 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다. -> [1(고정) + 각각 뽑은거] 2를 고정 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다. -> [2(고정) + 각각 뽑은거] 3을 고정 -> 나머지 [4] 중에서 2개씩 조합을 구한다. 4를 고정 -> 나머지 [] 에서 2개씩 조합을 구한다. 여기서 나머지 배열에 대해 조합을 구할 때는, 재귀함수를 사용하면 된다. - 기저조건 : 1개를 뽑을때, 모든 배..

이진 탐색은 정렬된 매우 큰 범위 내에서 최적의 해를 찾는 경우에 유리하다. 이진탐색 알고리즘은 O(logN)의 복잡도를 보장한다. 재귀함수를 이용한 이진탐색 let arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]; let target = 11; function b_search_recur(arr, target, left, right) { let mid = parseInt((left + right) / 2); if (left > right) { return -1; } if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return b_search_recur(arr, target, mid + 1, right); } ..

✏️구현 할 그래프 ✏️그래프의 인접 리스트 위 그래프에 대한 인접리스트는 다음과 같다. 인접리스트를 만드는 방법은 이전 글을 참고해 만들 수 있다. https://jaeyunim00.tistory.com/11 [알고리즘] 인접 행렬을 통한 인접리스트 구현, DFS(1) ✏️그래프 형태 구현할 그래프는 다음과 같다. 가중치가 없는 무향그래프 이다. ✏️인접행렬(Adjacenty Matrix) -> 인접리스트(Adjacenty List) 구현 위 그래프의 인접행렬은 다음과 같다. 각 정점별로 jaeyunim00.tistory.com 이제 dfs재귀 호출을 통해 그래프를 탐색하는 과정을 알아보자. ✏️코드 dfs함수의 코드는 다음과 같다. void dfs(int v) { node* w; visited[v] ..

✏️그래프 형태 구현할 그래프는 다음과 같다. 가중치가 없는 무향그래프 이다. ✏️인접행렬(Adjacenty Matrix) -> 인접리스트(Adjacenty List) 구현 위 그래프의 인접행렬은 다음과 같다. 각 정점별로 간선이 있으면 1, 없으면 0 으로 표현한다. #define N 9 int matrix[N][N] = { {0,1,0,0,0,0,0,0,0}, {1,0,1,1,0,0,0,0,0}, {0,1,0,1,1,0,0,0,0}, {0,1,1,0,1,1,0,0,0}, {0,0,1,1,0,0,0,0,0}, {0,0,0,1,0,0,1,1,0}, {0,0,0,0,0,1,0,1,1}, {0,0,0,0,0,1,1,0,0}, {0,0,0,0,0,0,1,0,0}, }; 인접리스트를 위한 구조체 선언 및 초기화..

🌿삽입정렬이란? 기본 정렬 알고리즘 중 하나이며, KEY를 선택후 배열의 값들과 비교해가며 삽입을 할지 안할지 결정한다. 최적의 경우 -> 이미 정렬된 배열에서는 O(n)의 시간복잡도를 가진다. 최악의 경우 -> O(n^2)의 시간 복잡도를 가진다. 🌿최적의 경우가 O(n)인 이유 다른 기본 정렬알고리즘들과는 다르게 삽입 정렬은 정렬된 배열에서 O(n)을 가지는데 void insertion_sort(int* arr, int size) { int i, j, key; for (i = 1; i = 0 && arr[j] > key; j--) { //***여기 부분때문에 최적의 경우 O(n)을 가짐! arr[j + 1] = ar..

🌿버블 정렬이란? 기본 정렬 알고리즘 중 하나이며, 인접한 두 원소의 크기를 비교하며 교환한다. 2중 for문으로 이루어지며 O(n^2)의 시간 복잡도를 가진다. 🌿작동 방식 편의상 오름차순 정렬을 기준으로 설명! - 첫 루프에서 1번째와 2번째 비교 후 교환 2번째와 3번째 비교 후 교환 . . size-1번째와 size번재 비교후 교환 이러면 최댓값이 맨뒤에 하나 옮겨지게 된다. - 두번째 루프에서 1번째와 2번째 비교 후 교환 2번째와 3번째 비교 후 교환 . . size-2번째와 size-1번재 비교후 교환 역시 맨뒤 - 1 번째에 최댓값이 옮겨진다. - 위 과정 반복!! ⭐그림을 통해 이해해 보자 여기서 중요한건 [i]와 [i+1]번째 비교시[ i+1]의 값이 더 작을때 교환을 해준다는 것이다...

🌿선택 정렬이란? 기본 정렬 알고리즘 중 하나이며, 그중에서도 가장 단순한 원리로 작동되는 알고리즘이다. 2중 for문으로 이루어지며 O(n^2)의 시간 복잡도를 가진다. 🌿작동 방식 각 루프마다 - 최솟값을 탐색. - 비교하는 값과 최솟값을 교환. 하나의 원소가 남을때 까지 위의 루프를 반복 ⭐그림을 통해 이해해 보자 🌿코드 #include void selection_sort(int* arr, int size) { for (int i = 0; i arr[j]) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } } int mai..