본문 바로가기

T아카데미/컴퓨터 알고리즘 초급

 (21)
컴퓨터 알고리즘 초급 이수증
19강. 탐욕 알고리즘 [ 목차 ] 1. 탐욕 알고리즘 2. 탐욕 선택 3. 동적 프로그래밍 4. 가중 무방향성 그래프 5. 신장트리 6. 최소신장트리 1. 탐욕 알고리즘 1) 현재 상황에서 가장 좋아 보이는 답을 선택하는 방법 2) 각 부분에서 최적을 선택하면 전체에서도 최적이 될 것이라는 가정을 전제로 함 3) 선택은 항상 하위 문제에 대한 해답이 나오기 전에 선택 2. 탐욕 선택 1) 하위 문제를 풀기 전에 선택 2) 항상 하나의 문제만을 고려 3. 동적 프로그래밍 1) 하위 문제를 풀고 나서 선택 2) 동시에 여러 개의 하위 문제를 고려 4. 가중 무방향성 그래프 1) G = (V,E) 2) 간선 집합에 속하는 각 간선(u,v)는 w(u,v)를 가짐 5. 신장트리 1) 트리가 그래프 G의 모든 정점을 포함할 대 그래프 ..
18강. 플로이드-와샬 알고리즘 [ 목차 ] 1. 플로이드-와샬 알고리즘 2. 중간 정점 3. 재귀해법 4. 수행과정 1. 플로이드-와샬 알고리즘 1) 각 간선의 값은 다음과 같이 표시 2) 최단 경로 행렬 d 3) 직전 정점 행렬 2. 중간 정점 1) 단순 경로 가 있을 때, v1과 vi 사이에 있는 정점을 지칭 2) 플로이드-와샬 알고리즘은 중간 정점을 모두 실험 3) 정점 집합이 v = {1, 2, ..., n}이라고 하면 i, j가 v에 속할 때, i와 j 사이에 정점 집합 v에 속하는 모든 정점을 넣어보고 경로의 값이 가장 작아지는 경로를 찾음 4) 수행시간 3. 재귀해법 1) 정점 i부터 j까지 최단경로 2) {1, 2, ..., k}는 중간 정점의 집합 3) 얻어지는 재귀식 4. 수행과정
17강. 벨만-포드 알고리즘 [ 목차 ] 1. 최단 경로 문제 2. 최단 경로 문제의 구분 3. 음수 간선 값 4. 직전 정점 하위 그래프 5. 완화 6. 벨만-포드 알고리즘 1. 최단 경로 문제 1) 최단 경로 : 정점 u에서 다른 정점 v까지의 경로의 값이 가장 작은 경로 2) 정점 u를 시작점, v를 도착점이라 지칭 3) 최단 경로 값 2. 최단 경로 문제의 구분 1) 시작점과 도착점의 숙에 따라 구분 2) 싱글 소스 & 싱글 데스티네이션 3) 싱글 소스 4) 싱글 데스티네이션 5) all pairs 3. 음수 간선 값 1) s에서 g로 가는 최단 경로 : s - a - b - g 2) s - e - f - e - f ..... - g 의 경로는 음수의 간선 값을 가짐 3) 음수 간선이 문제가 되는 것은 아니지만 음수 순환(모..
16강. 다익스트라 알고리즘 [ 목차 ] 1. 가중 경로 2. 다익스트라 알고리즘 3. 수행시간 분석 1. 가중 경로 1) 경로에 속하는 모든 간선의 값을 더한 값 2. 다익스트라 알고리즘 1) 하나의 시작점에서 하나의 도착점을 가는 최단경로를 찾는 알고리즘 2) 정점을 하나씩 추가하며 완화를 통해 새로운 경로에서 경로값을 계산하여 새로운 경로를 추가하여 최단 경로를 탐색 3) 간선이 음의 값을 가지면 불가능 3. 수행시간 분석
15강. 깊이 우선 탐색 [ 목차 ] 1. 깊이 우선 탐색 2. 타임스탬프 3. 깊이 우선 탐색 숲 4. 간선의 분류 1. 깊이 우선 탐색 1) 시작점을 기준으로 인접해 있는 V를 차례대로 이동하는 방식 2) 점점 거리가 깊어졌다가 되돌아오는 방식으로 탐색이 진행 3) 거리를 기준으로 하는 넓이 우선 탐색과 달리 시간, 순서를 기준으로 함 4) 수행 시간 2. 타임스탬프 1) 각 정점은 타임탬프를 두 개씩 가지고 있음 2) v.d 발견 시간 : 이전의 정점으로부터 현재의 정점이 발견되기까지 얼마나 걸렸는가? 3) v.f 완료 시간 : 현재 정점이 더이상 인접한 정점이 없어 탐색할 필요가 없을 때 4) 초기화한 정점 : 흰색, 발견된 정점 : 회색, 완료된 정점 : 검은색 5) 이동 가능하지만 이미 종료된 정점이 있을 경우 점선으..
14강. 넓이 우선 탐색 [ 목차 ] 1. 트리 탐색의 방법 2. 넓이 우선 탐색 3. 거리 계산 4. 직전정점 그래프 5. 정점의 색 구분 6. 수행과정 7. 수행시간 분석 1. 트리 탐색의 방법 1) 넓이 우선 탐색 2) 깊이 우선 탐색 2. 넓이 우선 탐색 1) 시작점을 기준으로 동일한 거리에 있는 노드들을 먼저 탐색하는 것 2) 그래프 G(v,e)와 시작점 s가 주어졌을 때 s에서 도달 가능한 모든 간선을 탐색하여 찾는 과정 3) 거리 : 점점 u부터 정점 v까지의 최단 경로에 있는 간선의 수 4) 시작점으로부터 거리를 하나씩 늘리면서 정점을 탐색 5) 그래프 안의 모든 정점을 탐색한 후 종료 3. 거리 계산 1) 탐색을 하면서 시작점으로부터 거리를 계산 2) 시작점으로부터의 거리 : u.d = 3 3) 바로 직전 정점 ..
13강. 그래프의 표현 [ 목차 ] 1. 그래프 표현 2. 인접 리스트와 인접행렬의 비교 3. 가중 그래프 1. 그래프 표현 1) 인접리스트 표현 Adjacency-list representation 1] 정점 하나당 리스트 하나인 크기가 V인 배열 2] 정점 하나에 인접한 모든 정점을 리스트에 저장 3] 비방향성 그래프에서는 방향성 그래프로 변환해서 저장하며, 공간을 많이 쓴다는 단점을 보유 2) 인접행렬 표현 Adjacency-matrix representation 1] 크기가 V x V인 행렬 2] 두 정점 i와 j를 잇는 간선이 있다면 행렬의 (i,j)는 1 아니면 0 3] 무방향성은 양방향으로 간선이 존재하므로 하위 삼각 행렬이 상위 삼각 행렬과 대칭 2. 인접 리스트와 인접행렬의 비교 1) G가 성기면 인접리스트가 ..
12강. 그래프의 기초 [ 목차 ] 1. 그래프 G 2. 방향성 그래프 3. 무방향성 그래프 4. 인접 5. 차수 6. 경로 7. 순환과 단일순환 8. 그래프 9. 강한 연결과 강한 연결 요소 10. 무방향성 그래프와 방향성 그래프의 변환 11. 완전 그래프 12. Dag 13. 트리 14. 간선의 개수 1. 그래프 G 1) 그래프 G는 (V, E)의 쌍 2) V는 정점의 집합이고 E는 간선의 집합 3) 정점은 독립된 개체로 동그라미로 표현 4) 간선은 두 정점을 잇는 개체로 선이나 화살표가 있는 선으로 표현 2. 방향성 그래프 1) 방향성을 있는 간선을 가지고 있는 그래프 2) 간선이 방향을 가지기 때문에 화살표가 잇는 선을 사용 3) 각 간선은 한 정점을 떠나서 한 정점으로 들어감 4) 일반적으로 각 정점은 숫자나 이름으로..
11강. 해쉬 알고리즘(2) [ 목차 ] 1. 오픈 어드레싱 2. 선형 프로빙 3. 삽입 연산 4. 해쉬 삽입의 Pseudo Code 5. 해쉬 검색의 Pseudo Code 6. 해쉬 삭제 7. 세 가지 오픈 어드레싱 기술 8. 선형 프로빙 9. 선형 프로빙 장단점 10. 이차식 프로빙 11. 이차식 프로빙의 단점 12. 이중 해싱 13. 이중해싱의 주의점 1. 오픈 어드레싱 1) Collision을 피하기 위한 다른 방법으로 key를 hash table에 직접 저장 2) 포인터를 사용하지 않아도 되므로 구현이 간편 3) 포인터를 사용하지 않으므로 추가 메모리 공간 사용이 가능 4) 공간의 충돌 문제가 줄어들며 자료 검색이 미세하게 빨라짐 5) 자료를 직접 기록하는 방법으로 검색, 삽입, 삭제가 빠르지만 충돌의 가능성이 있어서 리니..
10강. 해쉬 알고리즘(1) [ 목차 ] 1. Direct-address table 2. Direct-address table의 주요 함수 3. Direct-address table의 공간복잡도 4. 해슁 Hashing 5. 해쉬테이블 수행시간 분석 6. 해쉬 테이블 충돌 문제 7. 체인을 이용한 충돌문제 해결법 8. 최악의 경우의 수행시간 9. 평균적 수행시간 10. 좋은 해쉬 함수는? 11. 해쉬 함수와 key 12. 나눗셈 방법 13. 효율적인 m의 선택 방법 1. Direct-address table 1) 크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식 2) 중복되는 key는 없다고 가정 3) 시간복잡도가 굉장히 빠름 4) 검색, 삽입, 삭제가 빠르지만 실제 사용하는 공간이 낭비되는 단점 2. Di..
9강. 선형시간 정렬 알고리즘 [ 목차 ] 1. 비교정렬 2. 비교정렬의 하한값 3. 계수정렬 4. 계수정렬의 특징 5. 수행시간 6. 기수정렬 7. 기수정렬의 Pseudo Code 8. 기수정렬의 수행시간 1. 비교정렬 1) 이전까지의 정렬 알고리즘은 비교연산으로 정렬 2) 비교연산은 두 개의 원소의 관계를 다음 중 하나로 판단하는 것 2. 비교정렬의 하한값 1) 비교연산의 정렬방법은 아무리 빨라도 Ω(n log n)보다 느림 3. 계수정렬 1) 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록 2) x라는 입력은 x보다 작은 원소의 개수가 i-1개라면 정렬 후에 i번째에 위치해야 함 3) x보다 작은 원소의 개수는 원소의 개수를 세어서 확인할 수 있음 4) 입력 받은 배열에 있는 숫자의 범위를 확인하고 몇 개가 잇는지를 세어보고..
8강. 퀵 정렬 (Quick Sort) [ 목차 ] 1. 퀵 정렬 2. 파티션 3. 퀵 정렬의 Pseudo code 4. 퀵 정렬의 수행시간 5. 정렬 알고리즘 수행시간 비교 1. 퀵 정렬 1) Divide-and-Conquer paradigm을 사용, 풀기 힘든 큰 문제를 쉬운 여러 개의 작은 문제로 만드는 것 2) partition을 사용해서 Divide-and-Conquer paradigm를 수행 2. 파티션 1) Pivot이라는 기준을 정해 이보다 크거나 작은 집단으로 분리 2) 작은 값들은 앞, 큰 값들은 뒤로 이동 3) 모든 값들을 이동 후 Pivot과 뒤의 큰 값 중 가장 앞선 값과 교체 3. 퀵 정렬의 Pseudo code 1) A : 배열 2) p : 첫 번째 인덱스 값 3) q : Pivot 4. 퀵 정렬의 수행시간 1) P..
7강. 힙정렬(Heap Sort)(2) [ 목차 ] 1. 힙 구조 만들기 2. 힙 구조 만들기의 수행시간 3. 최대값 추출 Extract-Max 4. 힙 소트 Heap Sort의 Pseudo Code 5. 힙 소트의 수행시간 1. 힙 구조 만들기 1) Build-Max-Heap(a) 2) MAX-HEAPIFY(A,i)는 자식을 가지는 마지막 노드부터 시작 2. 힙 구조 만들기의 수행시간 3. 최대값 추출 Extract-Max 1) Heap에서 가장 큰 값을 제거하고 Max-Heap 구조를 복원하는 연산 2) root에 있는 최대값을 추출하고 트리의 가장 마지막에 있는 값을 root로 옮기고 다시 MAX-HEAPIFY 2) 수행시간 4. 힙 소트 (Heap Sort)의 Pseudo Code 5. 힙 소트의 수행시간
6강. 힙정렬(Heap Sort)(1) [ 목차 ] 1. 힙정렬 2. 힙의 형태 3. 힙 구조 4. 힙의 배열 저장 방식 5. 노드의 높이 6. Max-Heapify 7. Max-Heampify의 수행시간 1. 힙정렬 1) 힙 구조의 특성을 이용한 정렬 2) 합병정렬과 동일한 수행시간 3) 삽입정렬과 동일한 제자리 정렬 4) 시간복잡도 2. 힙의 형태 1) 완전 이진 트리에 가까운 형태 2) 이진 트리 : 각 노드의 자식 수가 2개 이하인 경우 3) 완전 이진 트리 : root 노드부터 leaf 노드까지 빠짐없이 채워져 있는 트리 4) 완전 이진 트리는 왼쪽부터 채웠을 경우에만 해당 3. 힙 구조 1) 최대힙 특성 Max-Heap Property 1] 부모 노드의 값은 항상 자식 노드의 값보다 큼 2] 따라서 전체 트리의 root 노드 값이 ..
5강. 합병정렬 [ 목차 ] 1. 합병정렬 알고리즘 2. 합병 정렬의 수행시간 3. A divide-and-conquer approach 4. 합병정렬의 Pseudo Code 5. 재귀트리 1. 합병정렬 알고리즘 1) 3강의 정렬문제 중 하나 2) 두 개의 이미 정렬된 배열이 주어졌을 때 정렬된 하나의 배열로 합치는 알고리즘 2. 합병 정렬의 수행시간 1) 두 개의 정렬된 배열의 길이를 각각 n1, n2 라고 가정 2) 주요 함수 : compare(비교), move(이동) 1] comparison 횟수
4강. 삽입정렬 [ 목차 ] 1. 삽입정렬 알고리즘 2. 삽입정렬 방법 3. 삽입정렬 수행시간 분석 4. 삽입정렬의의 공간복잡도 5. 삽입정렬의 시간복잡도 1. 삽입정렬 알고리즘 1) 3강의 정렬 문제 중 하나 2) key값을 정렬된 배열에 알맞은 위치에 삽입하여 정렬문제를 푸는 알고리즘 ex, 배열에 key값 3을 오름차순에 맞게 알맞게 삽입 2. 삽입정렬 방법 1) 주어진 배열 A[1...n]에 원소를 하나씩 추가하면서 배열 속 값과 비교하여 정렬 2) 첫 번째는 A[2]를 정렬된 배열 A[1]에 삽입 3) 두 번째는 A[3]를 정렬된 배열 A[1...2]에 삽입 4) N-1 번째는 A[n]를 정렬된 배열 A[1...n-1]에 삽입 3. 삽입정렬 수행시간 분석 1) 최선의 경우 1] 배열 A[1...n]가 이미 정렬..
3강. 정렬문제 [ 목차 ] 1. 정렬문제 2. 선택정렬 알고리즘 3. 선택정렬 정확성 증명 4. 선택정렬 성능분석 1. 정렬문제 1) 컴퓨터가 이해할 수 있게 입력과 출력으로 명확하게 정의해주어야 함 2) 입력 : n개의 숫자들의 배열 3) 출력 : 입력받은 숫자들을 점점 커지거나(오름차순) 작아지는(내림차순) 순서로 재배열 2. 선택정렬 알고리즘 1) 현재 상황에서 가장 작거나 큰 숫자를 선택하여 재배치하는 아이디어 2) 최소값 선택 정렬 : 가장 작은 값을 선택(오름차순) 1] 정렬되지 않은 숫자 중 가장 작은 숫자를 선택 2] 선택한 숫자를 정렬되지 않은 숫자들 중 첫 번째 숫자와 자리를 바꾸면 선택된 숫자는 정렬된 것 3] 모든 숫자를 옮길 때까지 1-2과정을 반복 3) 최대값 선택 정렬 : 가장 큰 값을 선택..
2장. 컴퓨터 알고리즘 개요(2) [ 목차 ] 1. 컴퓨터 알고리즘의 분석 2. 점근적 표기법 1. 컴퓨터 알고리즘의 분석 1) 수행시간 분석 1] 특정 기계에서 수행시간을 측정하는 것은 공정하지 않음 2] 따라서 조건이 동일한 특정 기계에서 모든 알고리즘의 수행시간을 측정해야 하나 비현실적 3] 수행연산의 횟수를 비교하는 방식으로 성능을 분석 4] 수행시간은 입력으로 크기가 커질수록 시간이 많이 걸리기 때문에 수행시간은 입력크기 n에대한 함수로 표현 5] 종합하면, 공정하고 공평한 비교를 위해 점근적 표기법에 의해 기술 2) 성능 분석의 비교대상 1] 산술 연산 : add, multiply, exponent, modurar, ... 2] 데이터 입출력 : copy, move, save, load, ... 3] 제어 연산 : if, wh..
1장. 컴퓨터 알고리즘 개요(1) [ 목차 ] 1. 컴퓨터 알고리즘 2. 컴퓨터 알고리즘 4단계 1. 컴퓨터 알고리즘 1) 컴퓨터 언어 : 컴퓨터와 대화하기 위해서 사용하는 언어 2) 컴퓨터 알고리즘 : 컴퓨터를 이용하여 주어진 문제를 풀기 위한 방법이나 절차로, 어떤 작업을 하기 위해서는 컴퓨터에게 할 일을 하나씩 차례대로 알려줘야 함 3) 컴퓨터 프로그램 : 컴퓨터가 특정 작업을 수행하기 위해 짜여진 명령의 순서 2. 컴퓨터 알고리즘 4단계 1) 문제정의 1] 해결하고자 하는 문제는 무엇인가? 2] 입력과 출력의 형태로 정의가 가능한가? 3] 컴퓨터가 수행할 수 있는 형태로 전환 가능한가? 2) 알고리즘 설명 1] 컴퓨터가 수행해야 할 내용을 하나씩 차례대로 정의한 과정 3) 정확성 증명 1] 과정대로 수행하면 출력으로 항상 올바른 ..
개요 주소 https://tacademy.skplanet.com/live/player/onlineLectureDetail.action?seq=83 컴퓨터 알고리즘 초급 | T아카데미 온라인강의 컴퓨터 알고리즘은 성공적인 프로그래밍을 위한 필수적인 과목입니다. 본 과정에서는 컴퓨터 알고리즘의 정의에 대해 학습하고 필요성을 인식하며 이에 대한 기본내용을 학습합니다. 또.. tacademy.skplanet.com 학습내용 컴퓨터 알고리즘은 성공적인 프로그래밍을 위한 필수적인 과목입니다. 본 과정에서는 컴퓨터 알고리즘의 정의에 대해 학습하고 필요성을 인식하며 이에 대한 기본내용을 학습합니다. 또한 컴퓨터 알고리즘의 분석 방법을 이해하고 컴퓨터 알고리즘을 응용하여 주어진 문제를 해결하는 방법을 배웁니다. 학습대상 컴퓨..

티스토리툴바