Falling in Love with Coding

깊이 우선 탐색(Depth-First Search:DFS) - 바이너리 트리를 순회할 때 사용하는 방법의 inorder, preorder, postorder를 사용 - 인접 노드를 타고 인접 노드가 없을 때까지 도달 후 다시 거슬러 올라오며 순회 Stack을 이용하여 구현 스택에 시작 노드를 넣어준 후 방문처리(Visited) 한다. 스택의 노드 하나를 꺼낸다(Pop). 꺼낸 노드가 인접(Adjacent) 노드가 있으며 방문하지 않았다면, 스택에 넣어준 후(Push) 방문처리한다. 스택이 비워질 때까지 2, 3번 과정을 반복한다. Recursion(재귀호출)을 이용한 구현 시작 노드를 먼저 방문처리 후 인접 노드를 방문한다. 방문한 인접 노드를 방문처리 후 인접 노드가 있다면 차례로 방문한다. 방문할 인..

정렬의 개요 1. 실행 방법에 따른 분류 1) 비교식 정렬과 분산식 정렬 - 비교식 정렬(Comparative Sort) ▪ 비교하고자 하는 각 키 값들을 한번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법 - 분산식 정렬(Distributive Sort) ▪ 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법 2. 정렬 장소에 따른 분류 1) 내부 정렬과 외부 정렬 ① 내부 정렬(Internal Sort) ▪ 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 ▪ 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨 ▪ 내부 정렬 방식 ② 외부 정렬(External Sort) ▪ ..

2-3-4 트리 1. 개요 - 2-3-4 트리의 정의 ▪ O(log2N)과 O(log4N) 사이의 탐색 효율을 가짐 ▪ 추가로 4-노드를 정의 - 자식 노드로 가는 링크(Link)가 4개이고 키가 3개인 노드 - 왼쪽 자식(Left Child), 오른쪽 자식(Right Child), 왼쪽 중간 자식(Left Middle Child), 오른쪽 중간 자식(Right Middle Child)으로 구분 - 2-3-4 트리의 노드 구성 2. 2-3-4 트리의 필요성 1) 2-3-4 트리의 장단점 ▪ 높이를 log4N으로 조금 더 낮추기 위함 ▪ 리프 노드 근처의 널 포인터 공간도 2-3 트리에 비해서 더 많아짐 ▪ 필요시 최대 3개의 키를 비교해야 하는 시간적 부담 2) 단일 패스 삽입 ▪ 2-3 트리는 리프 노..

2-3트리 개요 - 2-3트리의 특징 ▪ AVL은 균형 트리를 지향하는 반면 2-3 트리는 완전 균형 트리를 지향함 ▪ AVL 트리에 비해 상대적으로 단순한 논리 ▪ 2-노드 또는 3-노드 모두 가능 ▪ 이진 탐색 트리와 마찬가지로 리프 노드에 삽입 - 삽입 시 높이 변화의 특성 * 2-3트리 ▪ 반복된 삽입에도 2-3 트리의 높이는 좀처럼 증가하지 않음 ▪ 3-노드를 사용해서 최대한 많은 레코드를 높이 변화 없이 수용 * 이진 트리 ▪ 이진 탐색 트리의 높이는 삽입할 때마다 리프 노드 아래로 1만큼 증가 - 여러 가지 방법 ▪ 삽입, 삭제를 위해서는 삽입 대상 노드의 부모 노드를 접근해야 함 ▪ 삽입 시에 중간 키를 올리기 위해서, 또 삭제 시에 부모 노드의 키를 아래로 내리기 위해서 이진 트리는 부모..

탐색 연산 1. 탐색 연산의 기본 방법 - 연산 방법 ▪ 루트에서 시작함 ▪ 탐색할 키 값 x를 루트 노드의 키 값과 비교함 * 키 값 x = 루트 노드의 키 값 인 경우 => 원하는 원소를 찾았으므로 탐색 연산 성공 * 키 값 x 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행 * 키 값 x > 루트 노드의 키 값 인 경우 => 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행 ▪ 서브 트리에 대해서순환적으로 탐색 연산을 반복함 2. 탐색 연산 알고리즘 1) 이진 탐색 트리에서의 탐색 연산 알고리즘 searchBST(bsT, x) p ← bsT; if (p = null) then return null; if (x = p.key) then return p;..

분할 기법 1. K 번째 작은 수 찾기 1) 문제 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수는? 2) 문제 풀이 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수 구하기 1. 10, 7, 2, 8과 3, 1, 9, 6으로 분할 2. 10, 7, 2, 8 중 세 번째 작은 수는 8 3. 3, 1, 9, 6 중 세 번째 작은 수는 6 4. 작은 문제의 해결책이 큰 문제의 해결책으로 이어지지 않는다. 2. 분할(Partition) ① 임의로 피벗 설정 ② 다운 포인터와 업 포인터 설정 ③ 다운은 피벗보다 작거나 같은 것, 업은 피벗보다 크거나 같은 것 찾음 ④ 스와핑 ⑤ 포인터가 일치하거나 교차할 때까지 ③, ④를 반복 ⑥ 업 포인터 ..

재귀란? - 수학이나 컴퓨터 과학 등에서 자신을 정의할 때, 자기 자신을 재참조하는 방법 - 재귀 함수의 형태로 많이 사용 재귀 호출의 개요 1. 재귀 호출이란? 1) 정의 "자기 자신을 호출하여 순환 수행되는 것" ▪ 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출 방식 보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있음 2) 특성 대표적인 분할 정복 알고리즘 ① 문제의 크기 N ② 큰 문제를 작은 문제로 환원 ③ 작은 문제 역시 큰 문제와 유사함 ④ Self Call, Boomerang 2. 재귀 호출의 예 1) 팩토리얼(Factorial) 연산 ▪ 1~n의 모든 자연수를 곱하여 구하는 연산 ▪ 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 ..

시간 복잡도 - 알고리즘이 시간적으로 얼마나 효율적인지를 나타내어 주는 지표 - 데이터 양에 따른 처리 시간 증가가 완만할 수록 알고리즘 효율이 좋음 1. 알고리즘 - 알고리즘이란? * 추상적, 개략적으로 기술한 조리법 * 알고리즘을 구체적으로 표현한 것이 프로그램 - 사세성 * 기본 동작을 언급하되 너무 추상적이거나 구체적이어서는 안됨 - 정확성 * 허용된 입력에 대해서 제대로 동작해야 함 * '정확히 우리가 기대하는 것'을 수행해야 함 2. 프로그램 오류 - 문법적 오류 * 명령문 끝에 세미콜론 * 프로그래머와 컴퓨터 간에 정확한 의사소통 * 모호성(Ambiguity)을 배제하기 위한 약속 - 의미 상의 오류 * 프로그래머와 컴파일러 사이의 오해 * 연산자의 오사용 등 - 논리적인 오류 * 문법은 맞..

* 자료구조와 알고리즘의 관계는 의존적 메모리 할당 1. 메모리 할당의 개념 - 기본적 예제 연속적(Contiguous) : 배열 연결적(Linked) : 연결 리스트 2. 연속적 할당 - 하나의 배열로서 단일 연속적인 메모리 공간에 n객체가 저장됨 - 더 많은 메모리가 필요할 때에는 새로 메모리 공간을 요구하고 할당 받고, 이전 메모리의 모든 정보를 새 메모리에 복사해야 함. - 일반적으로 OS에게 추가로 연속된 n객체의 공간할당을 받을 수 없음 ex) ABCD 3. 연결적 할당 - 두 데이터를 연결적으로 저장할 수 있도록 할당 - 객체 자기 자신 그리고 자신과 연결되어 있는 다음 아이템에 대한 참조로 구성 - C++ 객체에서의 노드란 다음 노드의 주소(Pointer)를 지칭함 ex) A→B→C→D -..