목표: 알고리즘의 설계 및 분석 방법 습득
자료구조, 수학적 백그라운드, 문제에 대한 추상화 능력 및 통찰력이 필요!
[과목 소개]
1. 알고리즘 소개
2. 분할정복 알고리즘
3. 동적 프로그램 알고리즘
4. 욕심쟁이 알고리즘
5. 정렬 알고리즘
6. 탐색 알고리즘
7. 근사 알고리즘
1. 알고리즘의 필요성
컴퓨터를 사용해서 문제를 해결하기 위함
알고리즘: 일련의 단계적인 처리 과정
2. 기본 자료구조
자료구조 : 컴퓨터에서 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법
프로그램 <- 자료구조 + 알고리즘
자료구조나 알고리즘에 대한 고려없이 효율적인 프로그램을 짜는 것은 무의미함
[1] 선형 자료구조
배열 :
같은 자료형을 하나의 변수에 담는 데이터의 집합체, (index, value) 쌍의 집합
논리적인 순서와 물리적인 순서가 같음
데이터에 접근할 때 인덱스로 접근
삽입, 삭제 시 자료의 이동이 발생함. -> 자료가 많을 때는 자료의 이동이 부담 됨
1차원 배열
2차원 배열
3차원 배열
연결리스트 :
노드: 데이터, 링크(화살표)로 구성
논리적인 순서와 물리적인 순서가 같지 않음
데이터를 찾아가는 방식이 순차 접근임.
데이터가 많으면 찾아가는 것이 오래 걸림
데이터 삽입, 삭제 시 링크 필드를 조정하여 간단하게 수정
단일 연결 리스트 : 링크 필드가 1개
이중 연결 리스트: 링크 필드가 2개
단일 원형 연결 리스트
이중 원형 연결 리스트
스택
데이터의 삽입, 삭제가 한 쪽 끝에서만 이뤄지는 선형 리스트
후입선출 Last In First Out
top 변수를 사용
push, pop
큐
한쪽 끝에서는 데이터의 삽입, 다른 쪽 끝에서는 데이터의 삭제가 이뤄짐
선입선출 First In First Out
front/head, rear/tail 변수 사용
[2] 비선형 자료구조
트리 : 노드와 간선
루트 노드가 존재
루트 노드를 제외한 나머지 노드는 n개의 서로 분리된 부분집합으로 나누어지며, 각 서브트리는 트리가 됨.
차수 : 노드가 가지는 나뭇가지
리프노드 : 노드의 차수가 0인 것
비단말노드: 리프노드를 제외한 노드
부모노드, 자식노드, 형제노드
조상, 후손
레벨, 높이(깊이)
숲
이진트리: 각 노드의 차수가 2 이하(0,1,2)인 순서 트리
포화이진트리
- 구현:일차원 배열을 이요한 구현 / 연결 리스트를 이용한 구현
그래프 G = (V,3)
V: 정점의 집합, E: 간선의 집합
무방향 그래프 : 방향이 없음 (1,2) = (2,1) 1에서 2로 이동, 2에서 1로 이동
방향 그래프 : 방향이 존재 <1,2> 1에서 2로 이동
- 구현 : 인접행렬(2차원 배열 사용) / 인접 리스트(연결리스트 사용)