자료구조와 알고리즘이란?
개념 이해하기
자료란?
모든 유형의 데이터. 예) 숫자, 문자열, 불리언 등
자료구조란?
자료를 조직하는 방법. 예) 배열, 해시, 트리 등
알고리즘이란?
문제를 해결하는 절차
코끼리를 냉장고에 넣는 방법
- 냉장고 문을 연다
- 코끼리를 넣는다.
- 냉장고 문을 닫는다.
배열의 자료구조와 알고리즘
자료구조가 중요한 이유
소프트웨어를 문제없이 빠르게 실행할 수 있는 코드를 작성하기 위해 다양한 자료 구조를 알고 각 자료구조가 프로그램 성능에 어떤 영향을 미칠지 확실히 이해해야 한다. 자료 구조의 성능을 알려면 코드가 자료구조와 어떻게 상호작용하는지 알아야 한다. 이것을 연산으로 부르며 대부분 읽기, 검색, 삽입, 삭제의 네 가지 방법을 사용한다.
성능 측정 방법
연산이 얼마나 빠른가를 측정할 때는 시간이 빠른가가 아니라 얼마나 많은 단계가 필요한지 알아야 한다.
배열의 연산
배열이 메모리에 들어가는 방법
배열을 메모리에 담을 때는 배열의 길이만큼 연속적으로 비어있는 곳을 발견해 제일 첫번째 메모리의 주소를 기억한다. 그렇기 때문에 배열 읽기 시 매우 효율적으로 검색할 수 있다.
메모리의 특징
- 메모리는 엑셀의 테이블처럼 생겼다.
- 메모리 한칸에 1비트(컴퓨터의 최소 단위)이다
- 메모리는 각 칸마다 고유주소를 가지고 있다.
- 고유주소는 16진수로 이루어져 있다.
- 메모리는 주소를 알면 한번에 해당 주소까지 갈 수 있다.
배열의 읽기
fruits[3]
- 메모리에 배열이 저장될 때는 해당 배열의 첫번째 데이터의 메모리 주소를 기억한다.(1010)
- 배열을 읽을 때 첫번째 메모리 주소에 해당 인덱스값을 더한 주소 값으로 데이터를 해당 데이터를 읽는다.(1010+3)
배열의 검색
배열 안에 “datas”를 포함하는가?
배열을 처음부터 차례대로 읽어가며 원하는 데이터를 찾아냅니다. 이를 선형 검색이라고 하며 최소 1단계, 최대 N단계가 걸리기 때문에 메모리 주소로 한번에 찾아가는 것에 비해 매우 비효율적인 방법입니다. 이러한 비효율적인 방법을 개선하기 위해 알고리즘을 이용합니다. 배열의 검색의 경우에는 이진 검색(Binary Search)가 대표적인 예입니다.
배열의 삽입
마지막에 삽입
배열의 마지막에 데이터를 삽입할 경우 1단계의 과정을 거칩니다.
중간에 삽입
배열의 중간에 삽입할 경우 삽입할 부분에 데이터를 비우기 위해 뒤에 오는 데이터를 한칸씩 뒤로 이동한 후에 삽입합니다. 이를 감안하면 가장 오래 걸리는 경우는 맨 앞에 삽입할 경우로 N번의 이동과 1번의 삽입이 필요한 N+1단계이다.
배열의 삭제
배열의 삭제는 삽입과는 반대로 먼저 데이터를 삭제한 다음 비어있는 공간을 메우기 위해 다른 데이터를 한칸씩 이동한다. 이를 감안하면 마지막 데이터를 삭제할 경우가 가장 효율적인 1단계이며 중간 데이터를 삭제할 경우 최대 N단계가 필요하다.
배열과 집합 비교하기
집합이란?
중복을 허용하지 않는 자료 구조이다.
집합의 삽입
집합의 삽입의 경우 중복된 데이터가 있는지 확인하기 위해 한번의 검색과 삽입이 필요하기 때문에 최소 N+1 단계가 필요하다. 최악의 경우는 배열의 가장 앞에 데이터를 삽입하는 경우로 N번의 검색과 N+1 삽입이 필요한 2N+1단계이다.
| 배열 | 집합 | |
| 읽기 | 1 | 1 |
| 검색 | N | N |
| 삽입 | 1 or N+1 | N+1 or 2N+1 |
| 삭제 | 1 or N | 1 or N |
이진 검색과 선형 검색
정렬된 배열
정렬된 배열은 일반 배열보다 배열의 검색을 함에 있어서 보다 효율적으로 검색을 할 수 있다. 예를 들어, 일반 배열 [17, 3, 75, 202, 80] 에서 배열에 없는 22 값을 찾으려고 하면 모든 원소를 찾아야 한다. 하지만 정렬 배열 [3, 17, 75, 80, 202] 에서는 75에 도달하면 22가 없다는 것을 바로 알 수 있다.
이진 검색
정렬된 배열이 전제 조건이라면 이진 검색이라는 알고리즘을 이용하면 선형 검색보다 더 빨리 연산을 할 수 있어 효율적으로 프로그램을 돌릴 수 있게 된다. 선형 검색과 이진 검색을 그래프로 나타내면 다음과 같다. 
이진 검색 알고리즘
- 중간값을 구한다.
- 중간값과 원하는 값을 비교한다.
- 중간값이 더 크다면 중간값보다 큰 값은 버리고 중간값보다 작다면 중간값보다 작은 값을 버린다.
- 이것을 원소가 1개 남을 때 까지 반복한다.
| 배열 | 집합 | 정렬된 배열 | |
| 읽기 | 1 | 1 | 1 |
| 검색 | N | N | log N |
| 삽입 | 1 or N+1 | N+1 or 2N+1 | N+1 |
| 삭제 | 1 or N | 1 or N | 1 or N |
빅 오 표기법
빅 오 표기법이란?
빅 오 표기법이란 알고리즘의 평가 단계를 표기하는 표기법이다. 예를 들어 배열의 읽기는 배열의 크기에 상관없이 1단계롤 끝나는데 이를 빅 오 표기법으로 나타내면 O(1)이며, 선형 검색의 경우 O(N)으로 표기한다 이처럼 빅 옾 표기법은 알고리즘의 효율성을 나타낸다. 여기서 주의해야 할 점은 데이터의 수에 상관없이 단계수가 일정하다면 이도 O(1)으로 표기한다는 것이다.
| 배열 | 집합 | 정렬된 배열 | |
| 읽기 | O(1) | O(1) | O(1) |
| 검색 | O(N) | O(N) | O(logN) |
| 삽입 | O(N) | O(N) | O(N) |
| 삭제 | O(N) | O(N) | O(N) |
