DATA STRUCTURES
자료구조 소개
주요 내용
- 자료구조란
- 자료구조와 알고리즘
- 자료구조의 추상 데이터 타입
학습 목표
- 자료구조의 필요성을 직관적으로 이해하고, 알고리즘의 관계에 대한 느낌을 갖도록 한다.
- 추상 데이터 탕비에 대해 직관적으로 이해한다.
자료구조
- 데이터를 저장, 조직 관리하는 방법
자료구조란
- 문제 해결에 사용할 부품
- 건축물을 만들려면
건축 재료와 구조 모듈에 대한 이해가 필요하다
철근. 시멘트, 강화 유리, 벽돌...
샷시, 철골, 거푸칩, 배수 구조, 전기/ 인터넷 연결 구조,...
- 프로그래밍과 문제 해결도
데이터와 구조 모듈에 대한 이해가 필요하다.
프로그래밍 언어, 정수, 문자열
리스트, 스택, 큐, 우선순위 큐, 검색 트리, 해시 테이블, 그래프,..
- 생각하는 방법을 훈련하는 도구
- 자료구조는 그 자체로 중요하다 못지않게 생각하는 방법 훈련도 중요하다
자료구조를 이용해서 문제를 해결하는 과정
문제 해결 과정에서 논리의 골격이 구성되는 방법/ 스타일
의미의 단위를 설정하는 방법
자료구조의 종료
- 배열, 연결 리스트, 양방향, 연결 리스튿, 원형 연결 리스트, 행렬
스텍, 그래프, 트리, 최대 합
다루는 자료구조
자료구조와 알고리즘의 관계
- 자료구조는 알고리즘 과목의 직전 단계이기도 하고, 그 자체로 여러 알고리즘을 포함
알고리즘 표기법
- 자연어를 이용한 서술적 표현
서술적일 뿐만 아니라 쓰는 사람에 따라 일관성이나 명확성을 유지하기 어려움
누구라도 쉽게 이해하고 쓸 수 있어야 하는 알고리즘을 표현하는 데는 한계가 있음
- 순서도를 이용한 도식화
명령의 흐름을 쉽게 파악할 수 있지만 복잡한 알고리즘을 표현하는 데는 한계가 있음
- 프로그래밍 언어를 이용한 구체화
추가로 구체화할 필요가 없으나 해당언어를 모르면 이해하기 어려움
다른 프로그래밍 언어로 프로그램을 개발하는 경우에는 다른 프로그래밍 언어로 변환해야 하므로 범영성이
떨어짐
- 가상코드를 이용한 추상화
가상코드는 직접 실행할 수는 없지만 일반적인 프로그래밍 언어와 형태가 유사해 프로그램 언어로 구체화하기 쉬움
일반적인 알고리즘 표기법
move(n, a, b, c)
if(n>0) then {
move(n-1, a, b, c, d);
a에 있는 원반을 b로 옮긴다;
move(n-1, c, b, a);
}
}
-> 일반적인 알고리즘 표기 예: 하노이 탑 알고리즘
강의(교재)에서 사용하는 알고리즘 표기법
1. 함수생략
2. then 생략
3. then 없이 if-else
4. while 루프에 속하는 문장 들여쓰기
5. 주석
03 자료의 추상 데이터 타입
추상
- 세세한 부분을 표현하지 않고 전체적인 이미지를 표현한 것
추상 데이터 타입: ADT
- 세부사항에서 벗어나 추상적으로 정의한 데이터 타입
- 즉, 어떤 데이터 타입이 어떤 작업으로 이루어지는지만 표현한 것
(a) 원소를 첫번째, 두 번째, ..., i번째 원소로 가리킬 수 있는 자료구조
(b) i번째 자리에 새 원소 넣기
원소 x 찾기
i 번째 자리의 원소 삭제하기
-> 리스트의 ADT 표현의 예
2장. 재귀(자기호출)와 귀납적 사고
주요 내용
1. 자료구조와 재귀
2. 재구 구조 예
3. 재귀와 수학적 귀납법
학습목표
- 재귀의 뜻을 이해한다
- 재귀가 사용되는 문제의 예들을 통해 기본적인 수준에서 재귀의 원리를 이해한다
- 재귀와 수학적 귀납법 간의 밀접한 관계를 이해한다
01 자료구조와 재귀
재귀란
- 내 안의 나를 찾는 것
- 성격은 같고 크기는 작은 나를 차장 큰 나와 작은 내가 연결괸 관계를 들어내는 것
- 재귀 알고리즘= 자기호출 알고리즘
자신과 성격은 똑같지만 크기만 작은 알고리즘을 호출하는 알고리즘
복잡한 문제도 간명하게 볼 수 있게 한다
잘 쓰면 보약
(정렬, 탐색,..)
잘못 쓰면 독약
(피보나치 구하기, 최적 행렬곱 경로,...)
재귀 구조 예
수열: 등차수열
- 초항이 1이고, 공차가 3인 등차수열
n번째 원소는 자신과 성격이 똑같고 순소가 하나 작은 (n-1번째) 원소에 3을 더한 것
수열: 피보나치 수열
- 재귀가 치명적인 예
재귀 fib(100)은 얼마나 걸릴까?
mb3 맥북 에어
- fib(50): 10초
- fib(66): 하루정도
- fib(100): 3만년 정도
- fib(136): 1조년 초과
지수함수적 중복 호출로 인해 이런 치명적인 비효율이 발생한다
비재귀 fib(100)?
m3 맥북 애어
- 천만 분의 1초 정도
수열: 팩토리얼
하노이 탑
- 원반 n개, 기둥 3개 (a, b,c)
- 목표: n개의 원반을 기둥 a로부터 기둥 b로 옮긴다.
- 함수의 정의: move(n, source, destimation, spare)
-> n개의 우너반을 source 기둥으로부터 destination 기둥으로 옮긴다.
-> Spare: 보조기둥
- 예 : move(4, a, b,c)
move(3, a, b, c)
a에 있는 유일한 원반을 b로 옮긴다.
move(3, a, b, c)
- 목표: move(n, a, b, c)
선택정렬: 작동 원리
1. 최대 원소를 찾는다
2. 최대 원소와 맨 오른쪽 원소를 자리 바꾼다
3. 맨 오른쪽 자리를 관심 대상에소 제외한다
4. 원소가 1개 남을 때까지 1~3의 순환을 반복
중복, 전위, 후위 표현법
- 수식을 표현할 때 연산자의 상대적 위치에 따라
전위 표현
중위표현
후위 표현
로 나뉜다
- 형식언어로 표현하면
깊이 우선 탐색 알고리즘
노드와 이들을 연결하는 간선으로 이루어진 그래프에서 시작 노드로부터 방문할 수 있는 모든 노드를 방문
이진 탐색
재귀적 성격이 숨어있다. 그러면 아예 재귀 알고리즘을 만들어보자
03 재귀와 수학적 귀납법
재귀 알고리즘의 필수 구비 조건
- 재귀 알고리즘의 필수 구비 조건
경계 조건(base condition, 종료조건): 재귀 호출이 반복되다 궁극적으로 끝나는 조건
재귀호출
관계: 닮은꼴 작은 문제와 본 문제 간의 관계를 나타내는 부분
- 하노이 탑의 예
경계 조건이 없다면?
하노이 타워 문제와 수학적 귀납법
T(n): 하노이 탑 알고리즘이 n개의 원반을 옮기는데 필요한 이동(원반 하나를 옮기는 것)의 총 횟수
