본문 바로가기

분류 전체보기75

[알고리즘] 너비 우선탐색(BFS) 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 너비 우선탐색(Breadth First Search) 시작 노드를 큐에 넣는다. Deque로 가져온 노드를 방문한 노드를 체크하는 v[]배열에 체크한다. 인접한 노드 중 방문하지 않은 노드를 큐에 넣어준다. 2~3번을 반복해준다. 소스코드 #define __main #ifdef __main #include #define MAX 128 typedef struct __Que { int* que; // 큐 int max; // 큐의 최대입력 개수 int num; // 현재 큐에있는 데이터 개수 int front; // Deque할 위.. 2020. 11. 21.
[알고리즘] 재귀 함수 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 재귀함수 재귀 함수란 자기 자신을 재참조 하는 방법이다. 이때 주의할 점은 함수를 작성 할때 종료 조건을 반드시 작성해야 된다. 만약 그렇지 않으면 무한 루프에 빠지게 되고 결국 메모리 부족 현상이 발생할 것이다. 팩토리얼 int factorial(int n) { int tmp = 1; for (int i = 2; i = 1]) = n * factorial(n - 1) 소스코드 #define __main #ifdef __main #include int factorial(int n) { if (n == 1) return 1; //.. 2020. 11. 19.
[정렬] 힙 정렬 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 힙 정렬(Heap Sort) 힙 정렬은 완전 이진 트리의 조건을 만족해야한다. 완전 이진 트리란 마지막 LEVEL를 제외한 나머지 LEVEL의 노드가 모두 NULL이 아니여야하고 마지막 LEVEL은 왼쪽부터 채워져 있는 이진트리를 말한다. Heapify(최대힙 구성) 각 노드의 값이 자식노드(왼쪽, 오른쪽)보다 항상 큰값을 가진 이진트리를 만든다. 1번 노드부터 부모 노드와 비교하며 크면 교환해준다.(0번 노드까지) Heap Sort 마지막 노드와 0번째 노드를 교환하다. 마지막 노드를 제외한 나머지 노드로 최대힙을 구한다. 1.. 2020. 11. 17.
[정렬] 퀵 정렬 자료구조 연결 리스트 이진 트리 스택 큐 해시 정렬 버블 정렬 선택 정렬 삽입 정렬 퀵 정렬 힙 정렬 알고리즘 재귀 함수 너비 우선탐색(BFS) 깊이 우선탐색(DFS) 다익스트라 퀵 정렬(Quick Sort) 퀵정렬은 이름 그대로 아주 빠른 속도를 자랑한다. 중앙값(Key)을 기준으로 왼쪽에는 작은값 오른쪽에는 큰값을 넣어주고 2파트로 나눠서 반복한다. 이처럼 큰 문제를 작은 문제로 나눠서 해결하고 이를 합치는 방법을 분할 정복이라고 한다. 퀵 정렬은 분할 정복을 이용한 정렬이다. 시간 복잡도 : O(n * log(n)) 소스코드 #define __main #ifdef __main #include #include #include #define MAX_SIZE 10 void Init(int arr[]) {.. 2020. 11. 10.

티스토리툴바