노마드 코더에서 진행하는 챌린지 기록들
노개북 챌린지 5일차
오늘의 범위
- episode 22: 자료구조와 알고리즘은 필수라고?
- episode 23: 배열이 뭐죠?
- episode 24: 알고리즘의 속도는 어떻게 표현할까?
- episode 25: 검색 알고리즘이 뭐죠?
Ep 22 자료구조와 알고리즘은 필수라고?
개발자를 준비하다 보면 자료구조와 알고리즘을 공부하라는 소리를 한 번쯤 들어봤을 것이다. 몰라도 웹이나 앱 개발하는 데는 문제가 없는데 왜 자꾸 배우라고 하는 걸까.
효율적인 코드를 위해
알고리즘은 컴퓨터에 보내는 지시 사항을 나열한 것을 말한다. 효율성이 좋은 알고리즘을 사용하면 컴퓨터의 효율과 속도를 개선할 수 있다.
지도 앱에서도 패스파인더(pathfinder) 알고리즘을 사용하고 이미지 손상을 줄이면서 용량을 효율적으로 줄이기 위해 압축(compression) 알고리즘을 사용하는 등 이미 알고리즘은 우리 실생활에 녹아들어 있다.
데이터를 효율적으로 찾기 위해
자료구조는 데이터를 보기 좋게 정리하고 편리하게 찾기 위해 꼭 필요하다. 어떤 자료구조를 사용하는지에 따라 프로그램 속도가 달라지기 때문에 프로그램 목적에 맞는 자료구조 방식을 채택해야 한다.
효율적인 코드와 데이터 검색을 위해 알고리즘과 자료구조는 꼭 배워두도록 하자.
Ep 23 배열이 뭐죠?
배열(array)은 자료구조를 공부할 때 제일 처음으로 만나게 된다. 배열의 특징을 설명하기에 앞서 시간복잡도의 개념과 램(RAM)에 대해 간단히 알아보자.
시간복잡도와 램
시간복잡도란 프로그램의 작업 속도를 측정하는 방법으로, 작업이 거치는 단계에 따라 빠르다와 느리다를 결정한다. 단계가 적을수록 속도가 빠르고 많을수록 속도가 느리다.
대표적인 휘발성 메모리인 램(RAM)은 프로그램에 필요한 데이터가 저장된다. 배열을 만들게 되면 램에 줄줄이 이어진 형태로 공간을 차지하게 된다.
배열의 특징
배열은 첫 번째 인덱스가 1이 아닌 0으로 시작한다. 배열에서 특정 인덱스의 데이터를 읽는 것은 1단계에 해당하는 알고리즘으로 속도가 매우 빠르다.
반면에 특정 데이터를 찾는 과정, 검색은 속도가 빠르지 않다. 선형 검색의 경우 첫 인덱스부터 데이터를 찾는데, 운 좋게 해당 데이터가 앞에 위치하면 금방 찾을 수 있지만 아예 존재하지 않거나 뒤쪽에 있으면 찾는 데 시간이 오래 걸리기 때문이다. 선형 검색 이외에도 다른 검색 방법들이 존재하지만, 기본적으로 배열 검색은 속도가 빠르지 않다는 것이 핵심이다.
배열에 데이터를 삽입할 때는 어떨까. 삽입은 세 가지로 분류할 수 있다. (1과 2는 배열에 데이터가 꽉 차 있지 않을 경우이다.)
1. 데이터를 맨 마지막에 삽입하는 경우
컴퓨터는 배열의 시작과 길이를 기억하고 있기 때문에 시작점을 찾고 길이만큼의 뒤쪽에 데이터를 추가하면 된다. 간단하다.
2. 데이터를 중간에 삽입하는 경우
삽입할 위치의 뒤에 있는 데이터를 하나씩 뒤로 옮긴 후 빈 자리에 데이터를 삽입한다. 배열의 길이가 짧으면 옮겨야 할 데이터도 적지만 길이가 길수록, 또 삽입해야 할 자리가 앞쪽에 위치할수록 옮겨야 할 데이터가 많아지므로 작업 속도는 느려지게 된다.
3. 배열에 데이터가 꽉 차 있는데 삽입해야 하는 경우
배열에 남는 공간이 없다면 이전보다 큰 새 배열을 만들고 배열을 복사해 옮긴 후 데이터를 추가해야 한다. 딱 봐도 과정이 복잡하므로 데이터를 삽입하는 방법 중에 속도가 가장 느리다.
마지막으로 배열에서 데이터를 삭제하는 과정은 삽입과 비슷하다. 배열은 앞부터 채워져야 하는 특징이 있어 삭제도 뒤쪽에 위치할수록 빠르며 앞쪽에 위치할수록 느리다. 중간이나 맨 처음의 데이터를 삭제하려면 뒤의 데이터부터 끌어당겨야 하기 때문이다.
🎯 배열의 특징
- 배열은 램에 이어진 형태로 공간을 차지
- 배열 읽기는 속도가 빠름
- 배열 삽입과 삭제는 속도가 느림
- 배열 검색은 속도가 빠르진 않음
Ep 24 알고리즘의 속도는 어떻게 표현할까?
알고리즘의 속도, 즉, 시간복잡도는 알고리즘으로 작업을 완료할 때까지 걸리는 절차 수 N을 이용해 표기한다.
알고리즘의 속도를 표현하는 방법 Big-O
시간복잡도를 표기하는 방법을 Big-O라고 하며 O(N), O(1), O(log N)과 같이 표현한다.
O(1)
한 번만 실행하는 코드는 시간복잡도를 O(1)으로 표기한다. 아래 코드를 보자.
def print_first(arr):
print(arr[0])
그래도 시간복잡도는 O(1)이다. 왜? 출력이 몇 번이든 함수는 단 한 번만 실행되니까!
Big-O는 실행 단계에 영향을 주는 요소만 본다.
O(N)
for 문과 같은 반복문은 시간복잡도를 O(N)으로 표기한다.
def print_twice(arr):
for n in arr:
print(n)
그럼 for 문이 중첩된다면? 시간복잡도는 N*N인 O(N^2)이다.
이외에도 Big-O 표기법은 많으니 따로 공부하자.
Ep 25 검색 알고리즘이 뭐죠?
위에서 설명했던 배열에서 검색하는 과정을 통해 검색 알고리즘에 대해 알아보도록 하자. 대표적으로 선형 검색(Linear search)과 이진 검색(Binary search)이 있다.
선형 검색(Linear search)과 이진 검색(Binary search)
선형 검색은 배열의 앞에서부터 검색하는 방법이다. 찾는 데이터가 가장 마지막에 있을수록, 배열의 길이가 길수록 속도가 느려진다.
배열의 크기가 크면 선형 검색보다 이진 검색을 활용하는 편이 훨씬 좋다. 다만 이진 검색은 데이터가 정렬된 배열에서만 사용할 수 있다는 특징이 있다. 배열의 데이터가 숫자인 경우를 예로 들어 보겠다.
이진 검색은 배열의 중앙에서 검색을 시작하여 찾는 값보다 중앙에 위치한 값이 큰지 작은지 확인한다. 오름차순 정렬일 때, 중앙값이 더 크다면 찾는 값은 왼쪽에 있다는 뜻이므로 중앙값보다 왼쪽의 범위에서 또 중간을 찾고 크기를 비교한 후 왼쪽 또는 오른쪽 범위에서 같은 방법으로 점차 거리를 좁혀간다.
이진 검색이 속도가 빠른 이유는 단계마다 절반을 제외할 수 있기 때문이다. 배열의 길이가 길어져도 검색 시간이 크게 증가하지 않아 데이터가 많을수록 큰 효율을 보인다. 데이터를 정렬한 상태로 시작해야 한다는 부담도 있지만 큰 배열을 다룰 때는 도움이 된다.
🎯 이진 검색 알고리즘
- 이진 검색 알고리즘은 큰 배열을 다룰 때 효과적
- 이진 검색을 사용하고 싶으면 배열이 정렬되어 있어야 함
느낀 점
여태 알고리즘을 풀면서 단순히 시간복잡도가 빠른 것에만 집중해 푸는 데만 급급했었다. 단순히 그냥 최대한 빠른 걸 쓰면 되겠지라고 생각했었는데 특정 상황에서 필요한 알고리즘을 적절히 사용하는 것도 중요하다는 것을 알게 됐다.
아직 알고리즘에 대해서 능숙하지는 않지만, 많이 풀어보면서 효율적인 코드를 짤 수 있게 노력해봐야겠다.
References
book - IT 5분 잡학사전