Data structure & Algorithm
1. Data Structure
1-1. Selecting a Data Structure
Data structure를 고르는데 고려해야할 것
-> DS별로 프로그램의 수행 시간이 달라진다.
-> memory space와 time의 제한 조건에 따라 골라야하는 DS가 달라진다.
DS(Data Structure)를 고르는 방법
1. 꼭 수행되어야 할 기본 연산을 알기 위해서 문제를 분석해야한다.
2. 각 연산에 주어진 메모리와 시간의 제한을 수량화한다.
3. 이러한 조건에 딱 맞는 DS를 고른다.
1-2. Costs and Benefits
DS는 장점과 단점(costs and benefits)을 동시에 지닌다. => 다른 DS에 비해 모든 부분에서 뛰어난 DS는 존재하지 않는다.
각 문제(problem)는 가능한 메모리 공간과 시간 제한을 가지고 있다.
문제의 특성에 대한 자세한 분석 이후에 알맞은 DS를 고를 수 있다.
시간 제한의 예)를 들면
은행의 경우
계좌 이체와 계좌 개설은 수 초내에 일어나야 하지만
계좌 폐쇄는 오랜 시간이 걸려도 상관 없다.
1-3. Some Questions to Ask
DS를 고르기 위한 질문
- 데이터가 문제가 시작될 때 모두 저장되나, 아니면 중간중간에 삽입되고 삭제되는가?(ex. 영어사전 / 페이스북 포스트)
- 데이터가 삭제될 수 잇는가?
- 데이터들이 특정한 순서대로 정렬되어야 하는가, 아니면 랜덤으로 정렬되어야 하는가?
특정 값을 가진 데이터를 찾는데 유리한 DS => Hash table. "exact query"
특정 범위에 해당하는 값을 가진 데이터를 찾는데 유리한 DS => B-tree. "range query"
1-4. Abstract Data Type
ADT의 필요성과 DS 간의 차이를 안다.
ADT(Abstract Data Type) : 구체적인 기능의 완성과정을 언급하지 않고, 순수하게 기능이 무엇인지를 나열한 것
Encapsulation : 안의 구현과정을 보여주지 않는 것
DS는 이러한 ADT의 구체적인 구현
DS는 메인 메모리(main memory, RAM)의 데이터를 이용한다. <-> FS(File Structure) : 하드 디스크의 데이터들의 구조
ADT는 추상화를 통해서 복잡성을 조절한다. => set 헤더 파일 선언하면 set이 어떻게 구현되어 있고 이런 것들은 몰라도 됨. 어떻게 사용하는지만 알면 된다.
Data의
Logical Form : 논리적으로 어떻게 동작하는가(DS의 제약 없이 계산할 때 어떤 값을 내는가) (user 친화적)
ex) Integers in mathematical sense
Physical Form : 실제 어떻게 구현되어 있는가(구현 상으로 어떤 제약을 가지는가, overflow) (computer 친화적)
ex) 16/32 bits integer, overflow
2. Algorithm
2-1. Problem vs Algorithm vs Program
문제(problem) : 수행되어야 하는 일
- 주어진 인풋과 바라는 아웃풋이 존재
- 어떻게 문제를 푸는지는 문제에 주어져 있지 않음.
ex)
신체 활동과 센서 데이터를 결합하는 classifier를 만드는 딥러닝 알고리즘을 만들어라 => 문제가 아님(해결책이 미리 나와 있음)
신체 활동과 센서 데이터를 결합하는 classifier를 만들어라. => 좋은 문제
알고리즘(Algorithm) : 문제를 푸는 방법이나 과정
- 문제는 하나 또는 하나 이상의 알고리즘으로 풀린다.
- 알고리즘은 옳아야 한다.
- 몇 가지 확실한 단계로 이루어져 있다, 다음 단계로 넘어가는데에 애매성이 존재하지 않는다.
- 유한한 개수의 단계를 가진다.(런타임 오류로 빠지지 않기 위함). 알고리즘은 무조건 끝나야 한다!
프로그램(Program) : 프로그래밍 언어로 구현된 알고리즘