목표가 생기면 무작정 달려들어야지. 실패를 두려워 할 여유같은 건 없을 때니까

[주제]- 최소 비용 신장 트리의 개념 [정의]- 트리도 그래프의 한 유형- 경로: 두 개의 정점을 잇는 간선을 순서대로 나열한 것 ■ 그림(그래프의 사이클) - 정점 'B에서 D'에 이르는 경로의 경우의 수▷ B - A - D▷ B - C - D▷ B - A - C - D▷ B - C - A - D - 위 경로는 '단순 경로'에 속함 ※ 동일한 간선을 중복하여 포함하지 않는 경로 - 아래 경로는 단순 경로가 아닌 경우의 예▷ B - A - C - B - A - D - 오른쪽 그림의 경우 시작지점과 종료지점이 같은 경로를 '사이클'이라 함 - 사이클을 형성하지 않는 그래프의 예 - 사이클을 형성하지 않는 그래프는 회전할 시 트리와 같은 모양새를 갖춤- 그래서 이런 그래프를 '산장 트리(Spanning T..

[주제]- 그래프의 탐색 종류와 구현 모델 [정의] 1. 깊이 우선 탐색(Depth First Search, DFS)- DFS 알고리즘은 어떠한 선택을 하건 잘 동작하며, 누구를 우선 선택할 것인지에 대한 기준은 개발자가 결정해도 되는 단순한 문제 ★ 핵심 3가지- 한 사람에게만 연락하면 됨- 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알림- 처음 연락을 시작한 사람의 위치에서 연락은 끝이 남 ■ 그림(깊이 우선 탐색의 과정) - '나나'로부터 연락을 시작한다고 가정 - 나나는 '만수' 또는 '포포'에게 연락이 가능한데 여기서는 '포포'를 선택- 포포는 연결되어 있는 '길동'에게 연락- 길동은 '만수' 또는 '김민' 또는 '철수'에게 연락이 가능한데 여기서는 '철수'를 선택- 최종적으로 '김민..

[주제]- 그래프의 개념과 종류- 구현 모델 [정의]- 정점(Vertex) 사이에 간선(Edge)이 연결된 형태의 자료구조- 정점: 연결의 대상이 되는 개체 또는 위치- 간선: 정점 사이를 연결하는 선 ■ 그림(기본 그래프의 종류) ※ 연락을 돌리는 컨셉을 기준으로 설명 - 무방향 그래프(Undirected Graph): 연결 관계에 있어서 방향성이 없는 그래프- 연락의 시작이 '만수'일 경우 만수는 '나나', '길동'에게 연락할 수 있음- 나나는 '포포'에게 연락할 수 있음- 길동은 '포포', '김민', '철수'에게 연락할 수 있음- 중간에 연락이 끊겨서 다수의 사람이 연락을 받지 못할 확률이 매우 낮음 - 방향 그래프(Directed Graph): 간선에 방향정보가 포함된 그래프. 또는 다이그래프(D..

[주제]- 해쉬 테이블의 개념 [정의] 사원 번호(Key)직원(Data)00150홍길동01320고길동00099아무개 - 표(Table) 형태의 자료구조- 저장되는 데이터가 키(Key) 값과 데이터 값이 하나의 쌍으로 구성됨- 키 값이 없으면 데이터를 저장할 수 없으며, 키 값을 중복될 수 없음 ■ 그림(해쉬 함수) - 일정한 규칙으로 작성된 중복되지 않는 고유 값을 함수를 통해 쉽게 구분할 수 있는 값으로 변경 ※ 해쉬함수(Hash Function): 넓은 범위의 값을 좁은 범위의 값으로 변경하는 역할 - 하지만 해쉬함수가 단순한 산술 연산으로만 되어있으면 값이 중복되어버리는 충돌 현상이 발생됨 - 위 그림은 테이블의 메모리 상황을 표현- 칠해진 영역이 데이터가 저장된 슬롯- 데이터가 저장되는 위치가 골..

[주제]- 균형 잡힌 이진 탐색 트리인 AVL 트리의 개념 [정의]- 이진 탐색 트리는 '저장 순서에 따라 탐색의 성능 차이가 커지는 단점'이 존재- 위 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라고 함- 종류(AVL 트리, 2-3 트리, 2-3-4 트리, Red-Black 트리, B 트리)- 'G. M. Adelson-Velskii와 E. M. Landis'에 의해 고안되었으며, 이름의 앞글자를 따서 AVL 트리라고 함 ■ 그림(균형 잡힌 이진 탐색 트리 예시) ■ 그림(균형 인수) - 균형 인수: 균형의 정도를 표현하는 단위- 균형 인수의 절대값이 크면 클수록 그만큼 트리의 균형이 무너진 상태 ※ 균형 인수 값 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 - AVL 트리는 균형 ..

[주제]- 이진 탐색 트리의 개념 [정의]- 이진 탐색 트리에는 데이터를 저장하는 규칙이 있음. 그 규칙은 특정 데이터의 위치를 찾는데 사용됨- 이진 트리 + 데이터의 저장 규칙 = 이진 탐색 트리 [중요]- 이진 탐색 트리의 노드에 저장된 키(Key)는 유일- 루트 노드의 키는 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크며, 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작음- 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키- 왼쪽/오른쪽 서브 트리도 이진 탐색 트리- 삽입 과정과 탐색 과정은 동일하게 진행 ※ 키는 정수 값으로 설정했다는 가정 ■ 그림(이진 탐색 트리) ■ 그림(이진 탐색 트리의 데이터 삽입 과정) - 비교대상이 없을 때까지 내려감- 비교대상이 없는 때 ..

[주제]- 보간 탐색의 개념 [정의]- 이진 탐색의 비효율성을 개선시킨 알고리즘 [중요]- 효율적인 탐색을 위해서는 '어떻게 찾을까'가 아닌, 효율적인 탐색을 위한 '저장방법'이 무엇인지를 우선 고민해야 함- 탐색 대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작 ※ 예) 고길동이라는 사람의 전화번호를 찾을 때, 전화번호부의 인덱스를 보고 'ㄱ'에 해당하는 앞쪽에서 찾기 ■ 그림(보간 탐색) - 보간 탐색은 찾아야 하는 값이 상대적으로 앞에 위치한다고 판단하면 앞쪽에 탐색 - low: 탐색 대상의 '시작' 인덱스 값- high: 탐색 대상의 '끝' 인덱스 값- S: 찾는 데이터가 저장된 위치의 인덱스 값- 보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정 ■ 1차 공식 A..

[주제]- 기수 정렬에 대한 개념 [정의]- 기수(Radix)란 '주어진 데이터를 구성하는 기본 요소'를 말함 ※ 예) 2진수의 기수: 0, 1, 10진수의 기수: 0 ~ 9 1. LSD(Least Significant Digit) 방식의 정렬- '가장 작은 자릿수'부터 정렬을 진행 ※ 가장 오른쪽부터(숫자로 치면 1의 자리수부터) - 가장 작은 자릿수부터 가장 큰 자릿수까지 비교해야 된다는 단점이 존재하지만, 코드 구현은 MSD에 비해 간결 2. MSD(Most Significant Digit) 방식의 정렬- '가장 큰 자릿수'부터 정렬을 진행 ※ 가장 왼쪽부터 - 코드 구현은 LSD에 비해 추가 작업(정렬 상태 확인)이 필요하지만, 중간에 정렬이 완료될 수 있는 장점이 존재 [중요]- 기수 정렬은 정..

[주제]- 퀵 정렬에 대한 개념과 구현 [중요]- 피벗의 시작 위치는 '맨 왼쪽 or 중간 or 맨 오른쪽'이 될 수 있음- 좀 더 효율적이기 위해 처음:중간:마지막 숫자끼리 비교해서 중간 값을 피벗으로 설정하는 것이 효율적임 또는, 맨 왼쪽(오른쪽) 3개 숫자를 비교- 피벗을 중심으로 영역을 두 개로 분할하여 정렬 ※ 재귀 ■ 그림(퀵 정렬 과정)- 숫자 '5, 7, 4, 2, 1, 8, 3, 6'을 오름차순으로 정렬 - 맨 왼쪽 숫자를 피벗으로 결정- 비교 숫자(low)는 피벗 숫자의 오른쪽부터 시작 - 'low'는 해당 위치의 숫자가 피벗 위치의 숫자보다 높을 때까지 오른쪽으로 이동- 'high'는 해당 위치의 숫자가 피벗 위치의 숫자보다 낮을 때까지 왼쪽으로 이동 ※ 'low'의 이동이 끝나야 '..

[주제]- 병합 정렬에 대한 개념과 구현 [중요]- 정렬의 과정 => 1단계: 복합(Divide) → 2단계: 정복(Conquer) → 3단계: 결합(Combine)- 정렬할 배열을 중간을 기준으로 2개로 나눠서 따로 정렬- 1:1로 비교될 때까지 분할- 다시 거꾸로 숫자를 비교해가면서 정렬 ※ 재귀 ■ 그림(병합 정렬 과정)- 숫자 '5, 7, 4, 2, 1, 8, 3, 6'을 오름차순으로 정렬 [소스]■ Merge.javapackage sortMerge; public class Merge { public Merge() {} ///// 분할된 숫자들을 병합 public void MergeTwoArea(int arr[], int left, int mid, int right) { int fIdx = lef..

[주제]- 해시맵(HashMap)의 사용 방식 [중요]- 'TreeMap'을 사용하여 출력하면 자동으로 정렬이 됨 ※ 오름차순 정렬. '1, 2, 3, ...', '가, 나, 다, ...', 'A, B, C, ...' [소스]■ Dto.javapackage hasMapTest; public class Dto { int num; String name; public Dto(int num, String name) { this.num = num; this.name = name; } public void output() { System.out.println("num: " + num + ", name: " + name); }}Colored by Color Scriptercs ■ mainClass.javapackag..

[주제]- 정렬 알고리즘 종류 중 선택 정렬에 대한 개념과 구현 [중요]- 첫 번째 위치에 있는 숫자는 정렬된 상태로 간주 ※ 자신보다 앞에 비교할 대상이 없기 때문 - 자신보다 앞에 위치한 숫자랑 비교해가면서 배치(정렬)을 같이 진행 ■ 그림(삽입 정렬 과정)- 숫자 '2, 4, 3, 1'을 오름차순으로 정렬 - 두 번째 위치의 숫자를 임시 공간에 저장- 임시 공간의 숫자와 앞에 위치한 숫자와 비교- 임시 공간의 숫자가 더 높으므로 앞에 위치한 숫자 뒤에 배치 - 다음 위치의 숫자를 임시 공간에 저장- 임시 공간의 숫자와 앞에 위치한 숫자와 비교- 임시 공간의 숫자가 더 낮으므로 앞에 위치한 숫자는 뒤로 이동 - 다시 임시 공간의 숫자와 더 앞에 위치한 숫자와 비교- 임시 공간의 숫자가 더 높으므로 앞..

[주제]- 정렬 알고리즘 종류 중 선택 정렬에 대한 개념과 구현 [중요]- 모든 비교를 끝낸 뒤 맨 왼쪽으로 이동- 이동된 숫자는 정렬이 완료된 상태이기 때문에 다음 정렬된 숫자는 완료된 숫자 다음의 위치로 이동됨 ■ 그림(선택 정렬 과정)- 숫자 '3, 4, 2, 1'을 오름차순으로 정렬 - 전체 값 중에 가장 작은 숫자를 찾을 때까지 비교- 찾은 값의 위치와 맨 왼쪽 위치와 교체 - 정렬된 숫자를 제외하고 남은 숫자 중 작은 값을 찾을 때까지 비교- 찾은 값의 위치를 정렬 완료된 숫자의 오른쪽 위치에 있던 숫자와 교체 - 위와 같음 ■ 실행결과 [첨부 파일]

[주제]- 정렬 알고리즘 종류 중 버블 정렬에 대한 개념과 구현 [중요]- 오름차순 정렬 시(내림차순 정렬 시) 가장 큰(작은) 값을 오른쪽으로 이동- 마지막 숫자는 정렬이 완료된 상태기 때문에 더 이상 정렬 진행하지 않음 ※ 전체 길이의 '-1'한 만큼 정렬 진행 ■ 그림(버블 정렬 과정)- 숫자 '4, 2, 1, 3'을 오름차순으로 정렬 - 첫 번째 숫자와 두 번째 숫자 비교- 첫 번째 숫자가 더 높으니 위치 교체 - 두 번째 숫자와 세 번째 숫자 비교- 두 번째 숫자가 더 높으니 위치 교체 - 세 번째 숫자와 네 번째 숫자 비교- 세 번째 숫자가 더 높으니 위치 교체 - 1회전 정렬 종료- 다시 처음부터 반복 [소스]■ BubbleSort.javapackage sortBubble; public cl..

[주제]- 앞서 구현한 힙 구조에서 일부분 업그레이드하기 [변경되는 부분]- 프로그래머가 우선순위 판단 기준을 설정해놓기- 우선순위 비교 함수를 만들어서 우선순위 비교하기 [중요]- 우선순위 비교 함수의 기능1. 첫 번째 인자의 우선순위가 높으면: '0'보다 큰 값을 반환2. 두 번째 인자의 우선순위가 높으면: '0'보다 작은 값을 반환3. 각 인자의 우선순위가 동일하면: '0'을 반환 [소스]■ UsefulHeap.h#ifndef SIMPLEHEAP_H_#define SIMPLEHEAP_H_ #define TRUE 1#define FALSE 0 #define HEAP_LEN 100 /* * 'Heap' 구조체에 통합 *//*typedef struct _heapElem{ int pr; char data;..

[배열 기반의 힙 구현]- 연결 리스트 기반으로 구현 시 새로운 노드를 '마지막 위치'에 추가하는 것이 쉽지 않음- 각 노드마다 고유번호가 존재하며, 그 번호가 배열의 인덱스와 동일 ■ 그림(배열 기반의 힙)- 노드 인덱스와 배열 인덱스와 동일하게 만들기 위하여 배열의 0번째는 사용하지 않음 [고유 번호(인덱스)를 통해 부모/자식노드 구하기 규칙]- 왼쪽 자식노드의 인덱스: 부모노드의 인덱스 * 2- 오른쪽 자식노드의 인덱스: 부모노드의 인덱스 * 2 + 1- 부모노드의 인덱스: 자식노드의 인덱스 / 2 ※ 소수점을 무시하고 정수로 몫을 계산 [힙 구현의 개념 및 규칙]- 힙은 완전 이진 트리로 구성됨- 노드 번호와 배열의 인덱스는 동일하며, 마지막 노드 번호는 존재하는 노드의 개수와 동일한 개념으로 판..

[힙의 데이터 저장과정]- '최소 힙'을 기준으로 설명 ※ 데이터의 저장 값이 낮은 것이 우선순위가 높음 - 자식 노드 데이터의 우선순위 ≤ 부모 노드 데이터의 우선순위- 새로운 데이터는 우선순위가 제일 낮다는 가정하에 '마지막 위치'에 저장 ※ 마지막 위치: 트리의 마지막 레벨의 가장 오른쪽 - 그리고 부모 노드와 우선순위를 비교해가면서, 해당 우선순위 위치를 찾을 때까지 거슬러 올라가면서 교환을 반복 ■ 그림(추가과정) - 완전 이진 트리 예시 - 새로운 노드가 마지막 위치에 생성됨 - 부모 노드와 우선순위 비교- '2 > 10' 우선순위가 더 높으므로 위치 교환 - 다시 부모 노드와 우선순위 비교- '2 > 3' 우선순위가 더 높으므로 위치 교환 - 다시 부모 노드와 우선순위 비교- '2 < 1' ..

[우선순위 큐의 개념]- 기존 큐와 다르게 데이터가 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 꺼내짐- 데이터에 우선순위가 별개로 지정되지 않으며 값을 기준으로 순서가 동적으로 지정 ※ 데이터 값의 오름차순 또는 내림차순으로 기준을 잡을 수 있으며, 개발자가 결정 - 구현 방법에는 '배열, 연결 리스트, 힙'이 있음 [배열과 연결 리스트 구현 시 문제점] ■ 배열- 데이터의 우선순위가 높을수록 배열의 앞쪽에 위치시킴- 우선순위가 높은 데이터의 반환과 소멸이 쉬움★ 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 앞으로 또는 뒤로 옮기는 연산이 필요★ 삽입의 위치를 찾기 위해서 모든 데이터와 우선순위를 비교하면서 진행해야 함 ■ 연결 리스트★ 배열과 다르게 데이터 위치를 옮기는 작업은 없으..

[소스 코딩] ※ 이진 트리는 이전에 구현한 'BinaryTree2.h', 'BinaryTree2.c'를 활용※ 스택은 이전에 구현한 'ListBaseStack.h', 'ListBaseStack.c'를 활용 ■ ExpressionTree.h#ifndef EXPRESSIONTREE_H_#define EXPRESSIONTREE_H_ #include "BinaryTree2.h" BTreeNode * MakeExpTree(char exp[]); // 입력 받은 후위 표기법 수식을 수식 트리로 변환int EvaluateExpTree(BTreeNode * bt); // 수식 트리의 연산 void ShowPrefixTypeExp(BTreeNode * bt); // 변환된 수식 트리를 전위 표기법으로 출력void Sh..

[수식 트리의 개념]- 전위/중위/후위 표기법과 같은 하나의 수식을 표현하는 방식 ■ 그림(수식 트리의 예) ※ 수식 예: 9 – 6 / 2 + 4 ■ 그림(수식 트리의 연산 과정) [수식 트리의 구현 과정]- 중위 표기법의 수식을 입력 받음 → 수식 트리로 표현- 연산자, 피연산자는 스택으로 관리 [수식 트리의 표현]- 후위 표기법의 수식에서 앞쪽에 등장하는 피연산자와 연산자로 트리의 하단을 만들고, 계속해서 뒤 (피)연산자들을 그 위로 계속해서 구성해 나감 ■ 그림(수식 트리의 구성 과정) - 후위 표기법 수식 '8 2 - 2 /'를 스택을 활용하여 수식 트리로 구성 - 수식에서 조회된 문자가 '피연산자'이면 스택에 넣음 - 위와 동일 - 수식에서 조회된 문자가 '연산자'이면 스택에 저장된 피연산자를..