자료구조와 알고리즘의 필요성 : 효율적으로 빠르고 안정적인 프로그램을 만들기 위함이다.
개발은 요리와 비슷하다.
원하는 요리 혹은 프로그램을 만들기위해서 재료(데이터)가 필요하다.
이 재료(데이터)를 다룰 공간도 필요하다(자료구조)
재료(데이터)를 가지고 요리(프로그램)을 만들기 위한 레시피(알고리즘)도 필요하다.
세상엔 수많은 재료가있다. 그 수많은 재료들을 한개의 도마에 모두 올려둘순없다.
내가원하는 요리를위해 목적에맞는 재료와 도마를 선택하고 맛있고 빨리 요리를 만들고싶은게 사람욕심이다.
마찬가지로 수많은 세상의 데이터를 다루기위해 그 데이터를 저장할 적절한 구조를 선택하고 데이터를 통해 어떤 순서를 걸쳐서 만들어나갈지 순서를 복잡하지않게 잘 만들어야한다.
데이터란?
데이터는 한국말로 자료
즉 하나의 정보를 위한 재료이다.
우리 삶속엔 이미 수많은 정보들이 존재한다.
EX) 정보(사람들이 가장좋아하는 제로음료 Top3 1위는 펩시제로 2위는 코카콜라제로 3위는 티즐제로)
자료(펩시제로를좋아하는사람, 코카콜라제로를좋아하는사람 여러가지제로음료를좋아하는사람.)를 모을수있음
자료구조
자료구조라는것은 이러한 하나하나의 정보의 재료들인 자료를 어떤방식으로 담아낼지 결정하는것이다.
회사에서 시민들을 상대로 투표한 제로음료 선호도 Top3라는 주제의 PPT를 발표해야되는시간이다.
순위를 보여주기전에 각각 여러음료선호도가 몇표가나왔는지 최종결과를위해 나온 각각 여러음료들의 투표수에 대한
자료들을 이미지로 어떻게 보여줄지 고민하는상황이다.
(표로 보여주기위해서 일렬로나란히배치할수도있고, 위로쌓아올리는형태로만들수도있음 여러개의 자료를 담아내는 방식 = 자료구조)
| 1번음료선호도 | 2번음료선호도 | 3번음료선호도 | 4번음료선호도 | 5번음료선호도 |
이 방식으로 자료를 나열하였을때의 장점을 생각해본다.
참고로 자료를 담아내는 방법인 자료구조는 4가지연산의 시간복잡도(아래에서설명) 고려해야한다.
1.검색
2.읽기
3.삽입
4.삭제
위의 표는 자료가 5가지밖게없어서 각각 음료선호도 자료의 위치를 눈에알아보기쉬운상황이다. (좋은 상황)
4가지연산과 비교해서 장점을 생각해본다.
1.검색: 표안에 자료가 5개밖에 되지않아서 눈으로 금방 5개가 있다는 사실을 금방 알아낼수있다.
2.읽기: 음료번호가 쓰여있어서 원하는 음료선호도에 대한 자료를 금방 찾는다.
3.삽입: 순서대로 정렬되어있으니깐 6번음료선호도에대한 자료는 5번음료선호도옆에 쉽게붙여넣음면된다.
4.삭제: 순서대로 정렬되어있으니깐 3번음료선호도에대한 자료가필요없으면 그냥 바로삭제하면된다.
-위의 케이스는 자료가적고 순서대로 정렬된 최상의 케이스
-현실적으로 자료가 무수히많을거임.
| 1번 | 2번 | ... | ..... | ... | ... | ... | ... | 9999999번 |
즉 항상 최악의 케이스일때에서 자료를 어떻게 담아낼까를 고민해야한다.
- 엄청 많은 자료면 검색하려면 하나하나씩 다 읽어보면서 접근해야됨
- 삽입과 삭제시에도 하나하나 다세본다음에 순서가맞는지 확인하고 추가하고 삭제해야함.
그리고 자료를 담아낼때 상황에맞는 자료구조를 선택해야한다.
위에서 ppt에 발표할 표에 자료들을 어떻게 담아낼지 고민하는것인데. 상황에맞는 목적은 결국 ppt를 보는사람들이 보는것(읽기)이다. 그에맞는 적합한 방법을 고려해서 표(자료구조)를 만들어내면된다.
4가지연산 조건을 완벽하게 수행하는 자료구조는없다.
자료구조의 종류 : 1. 단순 구조 , 2. 선형 구조 , 3. 비선형 구조
- 단순 구조(자료형) : 정수, 실수, 문자열, 논리형(true / false)
- 선형 구조 : 배열 , 연결리스트, 스택 , 큐
-> 한 원소 뒤에 하나의 원소만이 존재하는 선형으로 나열된 자료구조 앞뒤 원소의 관계가 1:1
- 비선형 구조: 트리, 그래프
-> 원소 간 다대다 관계를 가지는 구조 계층구조 or 망형구조 표현에 적절하다.
정해진 일련의 절차, 방법을 공식화한 형태로 표현하는것을 의미한다.
알고리즘의 유명한 예시로 전화번호부에서 특정이름 찾기(cs50 강의 참조)로 들수 있다.
전화번호에서 "홍길동"이라는 이름을 찾기위해 다음과같은 여러가지 방법을 고려할수 있다.
1. 첫페이지부터 "홍길동"이라는 이름을 찾을때까지 계속 폐이지를 넘기면서 찾아본다.
2. 두페이지씩 넘기면서 "홍길동"이 나올때까지 책을 넘긴다
3. 책의 중간을 핀다음 홍길동의 'ㅎ' 보다 앞의 글자인지 뒤의글자인지를 고려하여
(전화번호부가 가나다라마바사순서로 정렬되어있다는 가정하에) 책을 찢어가면서 찾는다.
ex) 'ㅅ'으로 시작하는 이름이나온다면 뒤쪽을 전부 찢은뒤에 다시 남아있는 'ㅅ'의 다음페이지들의 중간페이지를 핀다음 글자를 확인하고 맞으면 완료 아닐시 다시 찢는과정 반복
자료구조와 알고리즘의 목표
자료구조안에서 연산(검색,탐색,삽입,삭제)횟수 혹은 알고리즘에서 입력값횟수를 고려해서
연산의 증가함에 따라 늘어나는 연산횟수를 최소화 즉 문제를 빠르고 효율적으로 해결 할 수 있어야 한다
- 효율적인 프로그램을 위해 시간복잡도를 고려할 필요가있다.
시간복잡도 : 상대적인 프로그램 성능 우수성 판별법
효율적인 자료구조와알고리즘을 선택한다는것 =입력값의 크기에 따라 변화하는 연산횟수를 최소화한 알고리즘
시간 복잡도를 표기하는 방법
1. 최악의경우(상한 점근표기) Big-O(빅-오)표기법
2. 중간의경우(평균) Big-θ(빅-세타)표기법
3. 최선의경우(하한 점근표기) Big-Ω(빅-오메가)표기법
프로그램을 실행하는 시간은 항상 최악으로 가정해야한다.
일반적으로 시간복잡도를 이야기한다는것은 최악의경우인 Big-O(빅-오)표기법에 대한 이야기다.
Big O 표기법의 종류
O(1) : 입력값이 증가하더라도 시간이 늘어나지않는다 EX) 배열(Array)에서 배열의 크기와 상관 없이 인덱스값을 통해 즉시 값을 출력할수 있음
O(n): 입력값이 증가함에 따라 시간도 같은 비율로 증가한다. Ex) 반복문(for, while)에서 반복문이 반복횟수만큼의 시간을 걸쳐서 반복문을 돌게된다.
O(log n): 컴퓨터과학에서 로그 밑의 기본값은 2이다. 즉 O(log₂N)이다.(N을 2로 몇번 나눠야 1이 나올까?) <> 지수와의 역관계 2³ = 8 == log₂ 8 = 3
Ex)위에서 전화번호부 알고리즘에서 3번의경우가 이 케이스임. 또다른 예시로는 UP and Down game이 있음.
O(n²) : 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가함. EX) 이중 반복문에서 반복문 안에 반복문을만듬으로써 반복횟수의 두배만큼의 시간을 걸쳐서 반복문을 돌게된다.
'자료구조 - 알고리즘' 카테고리의 다른 글
| 2-2 빅오표기법 - 공간복잡도 (0) | 2024.03.11 |
|---|---|
| 2. 빅오 표기법 - 시간복잡도 (0) | 2024.03.11 |