Data Structure
1. Basics
컴퓨터 공학 5대 과목 : 언어, 자료구조, 알고리즘, 운영체제, 컴퓨터 구조
2. 자료구조 vs 알고리즘
- 자료구조 : (램 메모리에) 데이터를 어떤 구조로 저장하고 탐색해야 가장 효율적인가?
- 알고리즘 : 문제를 해결하는 방법론
- 자료구조의 알고리즘 : 데이터를 저장하고 탐색하는 방법에 대한 고민들
- 자료구조를 이용한 알고리즘 : 자료구조를 이용해 어떤 문제를 해결하는 것
3. 자료구조 기본 개념
- recursion, index, sort, binary search
- stack, heap
- process, thread
- call by value, call by reference
- native code (like c, c++)
- MVC architecture
- write simple text-based games
4. 자료구조의 구성
- insert : 데이터를 어떻게 저장할 것인가?
- search : 데이터를 어떻게 탐색할 것인가?
- delete : 데이터를 어떻게 지울 것인가?
5. 재귀함수, recursion
- 재귀는 자기 자신을 재참조하는 방법이다.
- 재귀함수의 단점 : stack overflow를 조심해야 한다.
- 재귀함수는 탈출 조건이 중요하다.
메모리 영역
크게 code 영역, data 영역, stack 영역, heap 영역이 있다.
- code 영역 : 함수에 대한 기계어 코드
- data 영역 : global 변수, 배열, 등
- stack 영역 : 지역 변수나 코드 영역에 올라온 함수들을 가져와 실행
- heap 영역 : 동적 할당 변수
이 때, 재귀함수는 함수를 계속해서 호출하기 때문에 stack overflow가 발생한다.
예제
Hanoi Tower
def hanoi(start, to, end, n):
if n == 1:
print(str(n) + ": " + start + " to " + end)
else:
hanoi(start, end, to, n-1)
print(str(n) + ": " + start + " to " + end)
hanoi(to, start, end, n-1)
hanoi("a", "b", "c", 3)
6. 그 외 개념
- 사건 기반 프로그래밍(Event-driven programming; EDP)은 비주얼 베이직과 같이, 사용자의 명령·마우스 클릭·다른 프로그램의 메시지·키보드 글쇠 입력 등의 ‘사건’에 따라, 제어 흐름이 결정되어 일을 하도록 하게끔 만들어진 프로그래밍 언어 방식을 뜻한다.
- hash : key-value를 갖는 자료구조이다. 주요 동작은 효율적인 검색이다.
- open addressing
- closed hashing
- a star 알고리즘 : ai의 시조새
- priority queue = Heap
- stack (or linked list)
- 피타고라스 정리
- 대소비교
- heap : tree 자료 구조
- 빅오 : 알고리즘의 최악의 경우 성능, 즉 수행 시간의 상한을 나타냄
7. Coder vs Engineer (or Architect )
Coder는 아키텍터가 설계한 UML의 일부를 코드로 구현하는 사람이다. Coder에서 더 성장하기 위해서는 이산수학, 알고리즘을 꾸준히 공부해 Engineer가 되자. 그렇지 않고 coder에 멈춘다면 결국 치킨집 사장님이 된다. Engineer가 되어 영어도 잘한다면 해외진출은 어렵지 않다.
자료구조를 완벽히 익힌 후 알고리즘을 학습하자. (추천도서 : 윤성우의 열혈 자료구조, C언어를 이용한 자료구조 학습서)