algorithm정리

선택정렬(Selection Sort) 선택정렬 > 가장 작은 것을 선택해서 가장 앞으로 보내는 알고리즘 각 위치에서 마지막 원소까지 본 뒤 가장 작은 원소를 선택 선택정렬 코드 선택정렬 시간 복잡도 n+(n-1)+(n-2)+(n-3)+...+2+1 = n * (n+1) / 2 O(N * N) = O(N^2) 연산 횟수가 매우 많음 -> 다른 ...

버블정렬 버블정렬(Bubble Sort) 정의 > 옆에 있는 값과 비교해서 더 작은 값을 반복적으로 앞에 보내는 알고리즘 큰 수 부터 정렬(위치 고정)됨 코드 시간 복잡도 n+(n-1)+(n-2)+...+2+1 = n * (n+1) / 2 O(N^2)

삽입정렬 (Insertion Sort) 정의 > 각 숫자를 적절한 위치에 삽입 | 선택정렬, 버블정렬 | 삽입정렬 | | ------------------ | --------------------------- | | 무조건 위치를 변경 | 필요할 때만 위치를 변경 | 삽입정렬은 삽입할 때, 앞 원소 까지는 이미 정렬...

퀵 정렬 (Quick Sort) 정의 > 특정한 값(pivot)을 기준으로 큰 숫자와 작은 숫자를 분할하여 정렬 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤, 배열을 반으로 분할 코드 시간복잡도 > O(N*logN)

동적 계획법 (Dynamic Programming) > 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 1. vs 분할 정복 기법 (Devide and Conquer) 분할정복은 큰 문제 해결이 어려워, 작은 문제로 나누어 푸는 방법임. 작은 문제에서 반복 X Ex) 피보나치 수열 : 특정 숫자 D[i]를 구하기 위해 , D[i-1] 값과 D[i-2]...

탐색할 때 너비를 우선으로함 → 두 노드 사이의 최단경로 or 임의의 경로를 찾고 싶을 때 사용 시작(root node)에서 인접한 노드를 먼저 탐색하고, 멀리 떨어진 node는 나중에 방문하는 탐색 방법깊게 탐색 전, 넓게 탐색노드 방문 여부에 대해 반드시 검사해야함

루트 노드에서 시작해서 다음 branch로 넘어가기 전에 해당 분기를 완벽하게 탐색 → 모든 노드를 방문하고자 하는 경우 선택스택(Stack) 사용 : LIFO시작노드 (Start Node) 스택에 삽입 + 방문처리스택의 최상단 노드 확인최상단 노드가 방문하지 않은