1. 신장 트리 ( Spanning Tree )가중 무방향 그래프에서 모든 정점을 포함하는 트리 ( 사이클 존재X )특징모든 정점이 연결됨간선 수 = 정점 수 - 1|V| = n 이면 간선은 n-1개2. 최소 신장 트리 ( MST, Minimum Spanning Tree )최소 신장 트리란?신장 트리 중에서 가중치의 합이 가장 작은 것간선 (u, v)마다 가중치 w(u, v)를 가진 연결된 무방향 그래프 G = (V, E)에 대해서 다음을 만족하는 트리 G' = (V, E')조건간선 일부만을 선택했을 때, 선택된 간선들의 가중치 합이 최소E' ⊆ E, w(E') = min { ∑(u,v)∈E' w(u,v) }3. 최소 신장 트리를 구하는 알고리즘모든 간선 중에서 정점을 모두 연결하면서 가중치의 합을 가장..
1. 그래프그래프 G → G = (V, E)V : 정점(vertex)의 집합 ( 원 )E : 간선(edge)의 집합 ( 정점을 연결하는 선 )간선에 방향이 없으면 무방향 그래프ex ) 간선표시 : (1,4), (4,1)간선에 방향이 있으면 방향 그래프ex ) 간선표시 : ( 1 → 4 )ex ) 간선표시 : ( 4 → 1 )간선에다가 의미나 값( 가중치 )을 부여하면 가중 그래프트리트리가 되는 조건무방향 그래프일 것모든 정점이 연결되어있을 것사이클이 존재하지 않을 것그래프 표기 예시V(G₂) = {1, 2, 3, 4, 5}E(G₂) = {(1,2), (1,4), (2,5), (3,5)}2. 그래프의 주요 용어인접( adjacent ), 부수( incident )부분 그래프( subgraph )경로( ..
1. 레드-블랙 트리이진 탐색 트리, 균형 탐색 트리성질 모든 노드는 검정이거나 빨강이다. 루트 노드와 리프 노드는 검정이다.→ 모든 리프 노드는 NULL 노드이다. 빨강 노드의 부모 노드는 항상 검정이다.→ 빨강 노드가 연달아 나타날 수 없음 임의의 노드로부터 리프 노드까지의 경로상에는 동일한 개수의 검정 노드가 존재한다., → 이진 탐색 트리의 성질노드 구조Left ( 왼쪽 자식 노드 )Color ( 노드 색깔 )Key ( 키값 )Right ( 오른쪽 자식 노드 )Parent ( 부모 노드 )Sibling ( 형제 노드 )2. 레드-블랙 트리 : 탐색연산이진 탐색 트리의 탐색 방법과 동일3. 레드-블랙 트리 : 삽입 연산 1탐색이 실패한 NULL 노드에 빨강 노드를 추가하고, 두 자식 노드를 NUL..
1. 탐색 관련 기본 개념탐색이란?여러 개의 원소로 구성된 데이터에서 원하는 값을 갖는 원소를 찾는 것데이터의 형태 → 리스트, 트리, 그래프 등구분 → 내부 탐색 vs 외부 탐색관련연산 → 탐색 + ( 초기화, 삽입, 삭제 )탐색방법리스트 형태 → 순차 탐색, 이진 탐색트리 형태 → 이진 탐색 트리, 2-3-4 트리, 레드-블랙 트리, B-트리해시 테이블 → 해시 함수, 충돌 해결 방법2. 순차 탐색리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로(“순차”) 비교하면서 원하는 값을 갖는 원소를 찾는 방법3. 순차 탐색 : 탐색 연산입력 : A[0..n-1] : 입력 배열n : 입력 크기(탐색할 데이터의 개수)x : 탐색 키출력 : x가 배열 내에 존재하면 인덱스, 아니면 n을 반환기능 : 원하는 데..
1. 힙 자료구조힙 정렬이란?‘힙’ 자료구조의 장점을 활용한 정렬힙 자료구조의 장점임의의 값 삽입과 최댓값 삭제가 쉬움(최대) 힙 heap완전 이진 트리 ( complete binary tree )각 레벨별로 노드가 있어야 함마지막 레벨에서 왼쪽부터 오른쪽으로 노트를 확인했을 때 빈자리가 없어야 함각 노드의 값은 자신의 자식 노드의 값보다 크거나 같아야 함최소 힙완전 이진 트리 ( complete binary tree )각 노드의 값은 자신의 자식 노드의 값보다 작거나 같아야 함2. 힙의 구현일차원 배열로 구현레벨을 인덱스로 노드값을 원소 값으로 구현간단한 인덱스 조작을 통해 자식 노드를 확인할 수 있다.자식 노드 찾는 방법 : 2 * 부모노드인덱스 + 1, 2 * 부모노드인덱스 + 2간단한 인덱스 조작..
1. 퀵 정렬 - QuickSort( )특정 데이터를 기준으로 주어진 배열을 2개의 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식피벗( Pivot ) : 분할 원소주어진 배열을 두 부분배열로 분할하는 기준이 되는 특정 데이터보통 주어진 배열의 첫 번째 데이터로 지정2. 퀵 정렬의 원리피벗이 제자리를 잡도록 하여 정렬하는 방식예시입력배열 A에 저장된 원소 중 첫번째 원소인 30을 피벗으로 지정피벗 30을 제자리 잡도록하여 왼쪽 부분 배열과 오른쪽 부분 배열로 구분피벗을 기준으로 왼쪽은 피벗보다 작은 원소, 오른쪽은 큰 원소가 위치왼쪽 부분배열의 모든 데이터 왼쪽 부분배열에서 가장 큰 데이터 왼쪽 부분배열의 모든 값 3. 퀵 정렬 알고리즘QuickSort (A[ ], n) {..
1. 정렬이란?주어진 데이터를 값의 크기 순서에 따라 재배치하는 것ex ) 오름차순, 내림차순정렬 구분기준 : 정렬 수행 시점에 데이터가 어디에 저장되어 있는가?내부 정렬전체 데이터를 주기억장치에 저장한 후 정렬을 수행하는 방식외부 정렬모든 데이터를 주기억장치에 저장할 수 없는 경우,모든 데이터를 보조기억장치에 저장해 두고그중 일부 데이터만을 반복적으로 주기억장치로 옮겨와서 정렬을 수행하는 방식2. 내부 정렬 알고리즘비교 기반 알고리즘 : 키값의 비교 횟수O(n2)선택 정렬버블 정렬삽입 정렬셸 정렬O(nlogn)퀵 정렬합병 정렬힙 정렬데이터 분포 기반 알고리즘 : 데이터의 이동 횟수O(n)계수 정렬기수 정렬버킷 정렬3. 정렬관련 개념안정적 정렬 ( Stable )동일한 값을 갖는 데이터가 여러 개 있을 ..
2강. 알고리즘 소개 ( 2 )
1. 알고리즘 분석정확성 분석유효한 입력에 대해 유한 시간 내에 정확한 결과의 생성 여부수학적 기법을 사용한 이론적인 증명 과정효율성 분석알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정 / 평가공간 복잡도 ( Space Complexity )메모리의 양 = 정적 공간 + 동적 공간시간 복잡도 ( Time Complexity )수행시간 = 알고리즘의 실행에서부터 완료까지 걸리는 시간주로 알고리즘 분석은 시간 복잡도 분석을 의미2. 시간 복잡도시간 복잡도는 컴퓨터에서 실행시켜 실제 수행시간을 측정하는 방법을 의미하는가?실행 환경에 종속적이므로 일반성이 결여된 방법컴퓨터 속도, 구현에 사용된 프로그래밍 언어, 프로그램 작성 방법, 컴파일러의 효율성 등에 따라 시간이 달라짐 → 효율성 분석을 하는데 적합하지 X..
1. 컴퓨터 과학에서 알고리즘이란?컴퓨터과학 = 컴퓨터 + 데이터 + 프로그램 + 알고리즘컴퓨터의 한계는 해당 문제와 관련된 알고리즘의 존재 여부와 관련이 있다.컴퓨터 과학은 알고리즘의 과학이라고도 부른다.2. 알고리즘 강의의 학습 목표잘 알려진 특정 문제를 위한 알고리즘의 설계 및 분석 방법의 습득 →컴퓨터를 이용한 문제 해결 방법에 대해 체계적으로 생각하는 훈련 →주어진 문제에 대한 지적 추상화 능력 및 통찰력 향상3. 컴퓨터 과학이란?컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문이때 문제 풀이를 위한 절차나 방법을 알고리즘이라고 한다.4. 알고리즘이란?문제 해결을 위한 레시피레시피의 단계적인 조리 절차를 따르면 음식을 만들 수 있듯이알고리즘의 단계적인 처리 절차를 따르면 주어진 답을 구할 수 ..