b4failrise@devgraphy

0. 정렬 알고리즘 장단점, 수행시간 비교, 속도 비교, 종류

정렬 알고리즘 종류 정렬 알고리즘은 그 특지엥 따라 몇 가지로 분류할 수 있다. 비교 정렬 비교 정렬은 원소들을 정렬할 때 원소들의 순서에만 의존하는 알고리즘들을 일컫는다. 예를 들어 거품 정렬(bubble sort)은 비교하는 원소들이 숫자거나, 문자열이거나, 심지어는 복잡한 객체에 대해서도 순서가 결정되어 있다면 적용할 수 있다. 비교 정렬 알고리즘들은 아무리 빨라도 최악의 경우 Ω(nlogn)시간을 필요로 한다. 이는 이 알고리즘들을 결정 트리의 형태로 기술할 수 있다는 점에서 증명할 수 있는데, {\displaystyle n}개의 원소들의 순열은 n!가지로 이들을 잎 노드로 가지는 결정 트리의 깊이는 스털링 근사에 따라 적어도 [logn!] ≒nlogn이어야 하기 때문이다. 비교 정렬이 아닌 알고..

탐색 알고리즘

1. 선형 탐색 배열 처럼 요소가 직선 모양으로 늘어선 자료구조에서 순회하는 것을 말한다. 순차적으로 요소를 방문하기 때문에 순차검색이라고도 한다. 시간 복잡도: o(n) 2. 이분 탐색(binary search) 탐색 범위를 두 부분으로 분할하면서 찾는 방식 시간 복잡도: o(logN) 알고리즘 우선 정렬을 해야 함 left right로 mid값 설정 mid와 내가 구하고자 하는 값과 비교 구할 값이 mid보다 높으면: left = mid + 1, 구할 값이 mid 보다 낮으면 right = mid -1 left > right가 될 때까지 계속 반복하기 3. 깊이 우선 탐색(Depth First Search) DFS 개념 루트 노드(혹은 다른 임의 노드)에서 시작해서 다음 분기(branch)로 넘어가기..

시간 복잡도 차트

백트래킹

제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제 (모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것) 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음 만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감 재귀로 푸니까 스택 메모리 제한 확인해야됨 시간복잡도 O(N!) 개 오 래 걸 림 (N이 클 경우 백트래킹을 적용하면 시간초과 남) 12! = 479001600 = 4*10^8 기본 틀 void backtracking(int cnt, int idx) { if (cnt == m) { //조건 만족시 해야될 일 적음 return; } for (int i = idx; i < n; i++) { if..

스택

생활 속 자료구조와 알고리즘 초콜릿맛, 바닐라맛, 딸기맛이 차례대로 쌓여 있는 아이스크림 콘을 만드는 과정을 생각해 보자. 아이스크림 콘을 만들 때 우선 가장 아래쪽에 초콜릿을 녹여 넣은 후 그 위에 커피맛을, 그 위에 바닐라맛을, 그 위에 딸기맛을 쌓았을 것이다. 즉, 아이스크림을 쌓은 차례는 초콜릿->커피->바닐라->딸기 순이다. 그런데 철수는 아이스크림 맨 아래쪽에 있는 초콜릿을 좋아한다. 좋아하는 초콜릿을 먹으려면 어떻게 해야 할까? 순서대로 쌓여 있는 딸기->바닐라->커피를 차례대로 먹어야 초콜릿을 먹을 수 있다. 즉, 아이스크림 콘을 쌓았던 순서와 반대로 먹어야 한다. 이렇게 가장 먼저 넣은 초콜릿을 가장 나중에 먹을 수 있는 구조가 스택 구조다. 스택의 기본 1.스택의 개념 스택 자료구조는 ..