노랑꼬리의 개발 블로그

목차 ※ 정렬 #1 버블 정렬 & 선택 정렬 ※ 정렬 #2 삽입 정렬 & 힙 정렬 1. 분할 정복 알고리즘 2. 병합 정렬 (Merge Sort) 3. 퀵 정렬 (Quick Sort) 1. 분할 정복 알고리즘 - 엄청나게 크고 방대한 문제를 나누어 쉽게 풀 수 있는 작은 크기로 나누어 문제를 해결 한 뒤 합쳐서 해결하는 방식이다. - 어려운 문제를 간단하고 빠르게 해결 할 수 있다. - 함수 재귀 호출을 이용하여 구현하므로 오버플로가 발생할 수 있고 쪼갠 문제를 저장해야 하므로 메모리 사용량이 크다. ※ 3가지 단계를 거쳐 해결한다. 가. 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 나. 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. 다. 조합: 하위 ..

목차 ※ 정렬 #1 버블 정렬 & 선택 정렬 1. 삽입 정렬 (Insertion Sort) 2. 힙 정렬 (Heap Sort) 1. 삽입 정렬 (Insertion Sort) - 배열의 요소를 앞에서 부터 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 정렬 - 1회전 마다 하나씩 요소들을 정렬해나간다. - 배열이 길수록 효율이 떨어진다. (비교할 정렬이 길어지므로) - 본인 위치를 찾아 삽입하여 정렬하므로 삽입 정렬이라 한다. - 시간 복잡도가 버블 정렬, 선택 정렬과 같은 O(n²) 이지만 둘 보다 빠르다. 가. 구현하기 2. 힙 정렬 (Heap Sort) - 완전 이진 트리로 구성되어 최대 힙 트리나 최소 힙 트리를 구성해 정렬. - 정렬된 최대(최소) 힙에서 루트 노드를 꺼내어 배열에 저장한다. -..

목차 1. 정렬 알고리즘 2. 버블 정렬 (Bubble Sort) 3. 선택 정렬 (Selection Sort) 1. 정렬 알고리즘 - 원소들을 번호 순이나 사전 순 같이 일정한 순서로 열거하는 알고리즘 - 다른 알고리즘을 수행 하기 전 최적화를 위해 우선적으로 실행한다. - 대표적인 정렬 알고리즘 6개가 존재한다. ㄴ 버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬, 병합 정렬, 퀵 정렬 ※ 시간 복잡도 Sorting Best Avg Worst 버블 정렬 O(n²) O(n²) O(n²) 선택 정렬 O(n²) O(n²) O(n²) 삽입 정렬 O(n) O(n²) O(n²) 힙 정렬 O(nlog₂n) O(nlog₂n) O(nlog₂n) 병합 정렬 O(nlog₂n) O(nlog₂n) O(nlog₂n) 퀵 정렬 ..

목차 ※ 트리 #1 Tree ※ 트리 #2 DFS 1. 너비 우선 탐색이란? 2. BFS 구현 1. 너비 우선 탐색이란? (BFS : Breath First Search) - 그래프의 인접한 정점을 우선적으로 탐색 - queue를 이용하여 구현한다. - 장점 : 탐색된 경로가 항상 최단 경로이다, queue를 사용하여 다음 탐색 정점을 지정하므로 DFS 보다 메모리를 적게 사용한다. - 단점 : 목표 노드의 깊이가 깊은 경우 탐색이 오래 걸린다. 2. BFS 구현 (※ 입력 기준 : BFS 애니메이션) ※ 참조 위키 백과 너비 우선 탐색 : https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

목차 ※ 트리 #1 Tree 1. 깊이 우선 탐색이란? 2. DFS 구현 1. 깊이 우선 탐색이란? (DFS : Depth First Search) - 그래프에서 깊은 부분을 우선적으로 탐색 - 리프 노드에 도달 할 때 까지 목표 노드를 탐색, 발견 되지 않으면 현재 탐색 중인 노드의 부모 노드에서 탐색 되지 않은 자식 노드를 탐색한다. (백 트래킹 : backtracking) ㄴ 노드 방문 시 방문 여부를 검사해야 무한 루프를 방지할 수 있다 (탐색 된 노드 재탐색 방지) - 장점 : 현재 경로만 저장하며 탐색하므로 메모리를 적게 사용한다 (단순 탐색에 비해), 목표 노드가 깊이 있다면 빠르게 구할 수 있다. - 단점 : 탐색된 결과가 최단 경로가 아닐 수 있다. (목표 경로가 여럿일 경우), 목표 노..

목차 1. 트리의 구성요소 2. 트리 구현 1. 트리의 구성요소 Tree는 컴퓨터 친화적인 선형 자료구조가 아닌 사용자 친화적인 비선형 계층 자료 구조이다. 사용자가 원하는 데이터를 얻기 쉽도록 데이터를 구분하여 연결해 준다. ex) 컴퓨터 파일 경로, 회사 조직도 가. 노드(Node) - 트리의 각 요소 - 데이터를 저장하고 다음 노드로 연결 시켜줄 주소 값이 저장되어 있다. 1) 루트 노드 - 트리 구조에서 최상위 노드 (트리 예시 기준 A) - 부모 노드가 없음 2) 부모 노드 - 해당 노드와 연결 된 윗 노드 (트리 예시 기준 D와 E의 부모 노드 : B) 2-a) 조상 노드 - 해당 노드에서 루트 노드까지 경로 상의 윗 노드 들 (트리 노드 예시 기준 H의 조상 노드 : D, B, A) 3) 자..