TIL (2023.1.19.목)
DAY 7
📚 IT 5분 잡학사전
🔖오늘 읽은 범위: episode 22~25
📝 책에서 기억하고 싶은 내용을 써보세요.
22장. 자료구조, 알고리즘
알고리즘: 컴퓨터에게 내리는 지시 사항을 나열한 것
등교 준비하기 알고리즘이 있다고 하면, 효율성이 좋은 알고리즘일 수록 등교 속도가 빨라진다.
- 예) 최대한 빨리 목적지를 찾는 지도 앱에서는 Path finder 알고리즘을 사용한다.
- 예) PNG, JPG 파일은 이미지를 최소 손상하며 효율적으로 용량을 줄이는 압축(Compression) 알고리즘을 사용한다.
자료구조: 데이터를 효율적으로 보관하고 찾기 위해 필요
짐이 마구잡이로 쌓인 택배 창고에서는 물건을 빨리 찾을 수 없다.
- 책을 정리하는 데도 크기 순서대로 정리할지, 가나다 순으로 정리할지, 출판년도 별로 정리할지 등등 자료(data)구조에도 여러 방식이 있다.
- 예) 데이터 크기 기준, 검색을 위한 인덱스 기준, 생성 시간 기준 등
- 그 목적에 맞게 자료구조를 선택하여 사용한다.
23장. 배열(Array)
배열의 특징을 알려면 배열에서 자주 벌어지는 사건을 알아야 한다.
즉, 읽기(lead), 검색(search), 추가(add), 삭제(delete) 과정에서의 시간 복잡도를 알아야 한다.
- 시간 복잡도(Time Complexity)
시간 복잡도는 프로그램의 작업속도가 얼마나 빠른지 측정하는 방법이다. 즉, 얼마나 적은 단계를 거치는지 측정한다.- 5단계가 필요한 코드와 20단계가 필요한 코드가 있다면 적은 단계를 거치는 A 코드의 작업속도를 더 빠르다고 말한다.
이제 램의 관점에서 배열을 보자. 프로그래밍을 공부할 때 가장 먼저 만나는 자료구조인 배열(Array)은 램에 줄줄이 이어진 형태로 공간을 차지하고 있다. 배열의 구체적인 특징은 다음과 같다.
1. 배열을 읽는(lead) 방법과 속도
- 배열은 첫 data에 0 부터 숫자를 매긴다.
- 📌 배열의 원리: 배열은 램에 줄줄이 이어진 형태로 공간을 차지하고 있다.
- 그래서 위치를 지시해서 데이터를 읽을 수 있다.
- 애초에 몇 번째 data를 읽으라고 하기 때문에 1단계 알고리즘을 가지므로 속도가 빠르다.
2. 배열을 검색(search)하는 원리와 속도
- “딸기를 찾아“라고 하면 박스를 모두 뒤지는 방법으로 검색한다
- 따라서 읽기보다 속도가 오래 걸린다.
- 0부터 마지막까지 차례로 검색하는 배열의 자료구조를 선형 검색(linear search)라고 한다.
3. 배열에 데이터를 삽입(add)하는 원리와 속도
- 배열이 비어 있는 경우, 새로운 데이터를 배열의 끝에 추가하는 것은 쉽다.
- 📌 배열의 원리: 컴퓨터는 배열의 시작 주소와 길이를 알고 있다. 그래서 배열은 읽는 속도가 아주 빠르다.
- 배열이 비어 있는 경우, 새로운 데이터를 배열의 중간에 추가하려면 뒤에 있는 데이터를 뒤로 하나씩 옮기는 작업이 필요하다.
- 작업이 더 많아져서 속도가 덜 빠르다.
- 배열이 꽉 찬 경우, 새로운 데이터를 추가하려면 더 큰 배열을 새로 만들고 이전 배열을 복사해서 옮겨야 한다. 그러고 나서 새 데이터를 추가해야 한다.
- 작업에 단계가 많아져서 속도가 느리다.
4. 배열에서 데이터를 삭제(delete)하는 원리와 속도
- 마지막에 있는 data를 삭제하는 것은 쉽고 속도도 빠르다.
- 중간에 있는 data를 삭제하려면 중간에 있는 그 data를 삭제한 뒤, 그 뒤에 있는 모든 data를 차곡차곡 앞으로 당겨야 한다.
- 📌 배열의 원리: 배열은 맨 앞부터 차곡차곡 채워져 있어야 한다. 그래서 배열은 삽입과 삭제가 느리다.
24장. 알고리즘의 속도 표현
빅오(Big-O)표기법
알고리즘으로 작업을 완료할 때 까지 걸리는 절차 수 N을 이용하여 O(N), O(log N)과 같이 표현한다.
-
예시) 선형 검색 알고리즘
: 배열 앞에서부터 하나씩 검사하기 때문에 배열의 길이가 N이면 최대 검색 횟수가 N이다.- 빅오 표기법으로는 시간 복잡도를
O(N)으로 표현한다.
- 빅오 표기법으로는 시간 복잡도를
-
빅오 표기법은 설명을 간단시 해줄 뿐만 아니라, 알고리즘 분석을 빠르게 할 수 있게 한다.
-
알고리즘 선택 전, 빅오표기법을 보고 어떤 알고리즘을 사용할지 파악 할 수 있다.
빅오 표기법 예시
- 시간 복잡도
O(1)
-
첫 번째 데이터를 한 번 출력하는 함수의 시간 복잡도는
O(1)이다.
O(1)을상수 시간(실행 횟수가 고정으로 정해진 것)내에 실행된다고 말하기도 한다. 즉, 배열의 길이가 100이어도 첫 번째 데이터를 출력하는 함수는 실행 횟수가 고정적(첫 번째 데이터니까 실행 횟수가 한 번)으로 정해져 있기 때문에 상수 시간내에 실행된다고 말한다. -
첫 번째 데이터를 두 번 출력하는 함수의 시간 복잡도도
O(1)이다.
왜냐하면 Big-O는 실행단계에 영향주는 요소만 보기 때문이다.
즉, 배열의 길이와 상관없이 첫 번째 데이터를 출력하기 때문에 실행 횟수는 한 번이다.- 예) 이진 검색 (p.147 그래프 참고)
이진 검색은 시간복잡도가 동일하기 때문에 배열의 길이가 길어져도 검색 시간이 확 커지지 않는다.
- 예) 이진 검색 (p.147 그래프 참고)
-
시간 복잡도
O(N)
배열의 모든 데이터를 출력하는 함수의 경우, 배열의 모든 데이터를 출력해야 하기 때문에 배열 길이에 따라 실행 시간이 달라진다.
따라서 시간 복잡도는 O(N)이다. (p.148 그래프 참고) -
시간 복잡도
O(N*N) = O(N제곱)
중첩 반복문 있을 때 발생하는 이차 시간(quadratic time)의 경우, 배열이 길어지면 길어질 수록 시간 제곱배로 느려진다.
O(N*N) = O(N제곱) (p.149 그래프 참고)
25장. 검색 알고리즘(Search Algorithm)
(y= 시간, x=배열 길이)
(p. 151, 153 그래프 참고)
| 선형 알고리즘(linear search) | 이진 검색 알고리즘(binary search) | |
|---|---|---|
| 특징 | 배열 맨 처음부터 검색을 시작하여 배열 끝까지 순서대로 검색 | 배열 중앙 값 기준에서 검색을 시작하여 찾는 값이 중앙값 보다 작은 지 큰지 비교하며 검색 범위를 줄여가며 검색함. 줄인 범위의 중앙값 기준으로 검색하고 또 반복. 단, 정렬이 끝난(data가 순서대로 정렬된) 배열에서만 사용 가능 |
| 배열 길이와 검색 속도 | (y=x), 배열 길이가 길어지면 검색 시간도 길어짐 | (y=logx), 배열길이가 길어져도 검색 시간이 확 커지지는 않음 |
| 예) 1에서 부터 9까지 있는 배열에서 6을 찾으시오 | 배열 맨 처음부터 검색 시작: 검색 6번 째에 6 찾음 | 배열 중앙값인 5부터 검색 시작하여 찾는 값보다 작은 범위는 삭제하며 중앙값으로 검색: 검색 1번 째에 6찾음 |
이진 검색 알고리즘
- 이진 검색 알고리즘은 거대한 배열 다룰 때 효과적이다.
- 하지만 배열이 항상 정렬되어 있어야 한다.
💬 오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요
와.. 알고리즘 너무 재미있어…!!! 눈이 반짝반짝 떠진다.
알고리즘이라고 하면 대기업 면접 볼 때 꼭 쳐야 하는 시험 느낌이 강했는데 이렇게 재밌는지는 꿈에도 몰랐다. 와 너무 재미있다!
❓ 궁금한 내용이 있거나, 잘 이해되지 않는 내용이 있다면 적어보세요.
.
