본문 바로가기

Algorithm/알고리즘 개념 정리21

[실전 알고리즘] 정렬2(코테용) Counting Sort 수의 범위가 어느 정도 한정적일 때에만 Counting Sort를 쓸 수 있음 수의 범위가 대략 1000만 이하일때에는 카운팅 소트를 쓰고 그렇지 않을 경우에는 카운팅 소트를 쓰지 못한다고 생각하기 1부터 차례로 나온 횟수만큼 적으면 끝 1이 2번 나왔으니 1을 2개 쓰고, 2는 1번이니 1개 쓰고, 이런식으로 하면 너무나 쉽게 정렬이 가능 [백준 15688] 수 정렬하기 5 (tistory.com) Radix Sort 자릿수를 이용해서 정렬을 수행하는 알고리즘 Comparison Sort, Non-comparison Sort Comparison Sort : 버블 소트, 머지 소트, 퀵 소트 원소들끼리 크기 비교 과정 있음 Non-comparison Sort : 카운팅 소트, 라.. 2022. 9. 26.
[실전 알고리즘] 정렬1(면접용) 기초 정렬 Selection Sort / O(N^2) - swap으로 구현 int arr[10] = { 3,2,7,116,62,235,1,23,55,77 }; int n = 10; for (int i = n - 1; i > 0; i--) { int maxIndex = 0; for (int j = 1; j 0; i--) { swap(*max_element(arr, arr + i + 1), arr[i]); } Bubble Sort / O(N^2) int arr[5] = {-2,2,4,6,13}; int n = 5; for (int i = 0; i arr[j + 1])swap(arr[j], arr[j + 1]); } } Merge Sort / O(NlogN) 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법 M.. 2022. 9. 20.
[자료구조와 알고리즘] 동적 배열 구현(size, capacity, reserve, resize) 본 내용은 을 토대로 작성하였습니다. Vector 구현 vector - size() vs capacity() size() : 실제 사용중인 데이터 갯수 capacity() : 할당된, 예약된 총 공간 #include #include using namespace std; int main() { vector v; v.reserve(100); cout 2022. 9. 20.
[실전 알고리즘] 백트래킹 백트래킹 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 연습문제 1- N과 M [백준 15649] N과 M (1) - 백트래킹 (tistory.com) 연습문제 2- N-Queen [백준 9663] N-Queen (tistory.com) 연습문제 3- 부분수열의 합 [백준 1182] 부분수열의 합 (tistory.com) STL next_permutation next_permutation - C++ Reference (cplusplus.com) 왼쪽 그림이 순열(순서 상관 있음) , 오른쪽 {0,1} 넣어서 구현하는게 조합(순서 상관 없음) 조합에서 5개에서 3개를 뽑는 문제라면 배열 a를 {0, 0, 0, 1, 1}로 두면 됨 출처 BaaaaaaaarkingDog | [실전 알고리.. 2022. 9. 15.
[실전 알고리즘] 재귀 재귀 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 사고법 절차지향적 사고 X 귀납적 사고 O ex. '1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다' 까지만 생각한 후에 바로 모든 도미노가 쓰러진다는 결론에 도달할 수 있어야 함 재귀함수의 조건 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야함(Base condition) 모든 입력은 base condition으로 수렴해야 함 재귀에 대한 정보 1. 함수를 명확하게 정의 : 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함 2. 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음 3. 재귀는 반복문으로 구현했을 때에 비해 코드가 간.. 2022. 9. 7.
[실전 알고리즘] DFS DFS? 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 예시 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4. 스택이 빌 때 까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N). BFS vs DFS 거리 측정은 BFS만 할 수 있다. 출처 BaaaaaaaarkingDog | [실전 알고리즘] 0x0A강 - DFS (encrypted.gg) 2022. 9. 7.

티스토리툴바