알고리즘을 모르면 개발을 못하나?
선배 개발자들의 의견이 다를지 모르겠지만, 내 생각은 NO다.
그간 개발을 해오면서 단순히 어떤 변수를 처리해서 전달하고 결과값을 얻어내는 기능을 만들어 내는 데에 어떤 알고리즘을 아냐 모르냐는 큰 영향을 끼치지 않았다.
그래서 나는 이 재미없는 알고리즘을 굳이 배워야 하나라는 생각을 머리 한켠에 가지고 있었다.
그럼 알고리즘을 어디에 쓰나?
알고리즘은 효율적인 코딩을 위해 쓴다.
똑같은 동작을 하는데 어떤 코드가 더 빨리 수행되고 메모리를 덜 쓴다면 그게 효율적인 코드라고 할 수 있겠다.
나는 단순히 어떤 기능을 빨리만 만들어 내는 것보다 어떤 코드를 어떻게 효율적으로 만들거나 수정했는지가 스스로에게 더 보람차고 면접관의 눈에도 더 가치 있는 경험이 된다고 확신한다.
(내가 이미 실패 해봤으니까)
복잡도?
알고리즘을 얘기할때 자주 내용인 복잡도는 알고리즘이 수행될때 걸리는 시간이나 메모리의 양을 나타내는 수치이다. 따라서 복잡도가 클수록 비효율적이라고 할수있다.
빅오 표기법
: 복잡도를 설명할때 사용하는 표기법이다.
O는 'Order of' 의 약자로 알고리즘의 성능이 입력 크기에 따라 어떻게 변화하는 지 나타낸다.
O(입력 크기) 와 같이 표기하며 가장 최악의 경우를 가정한다.
시간 복잡도
: 알고리즘이 수행되는 데 걸리는 시간에 따라 결정된다.
주요 복잡도
O(1) (상수 시간): 어떤 값을 입력 받던지 실행 시간이 늘 일정한 경우
이미 만들어지 변수의 값에 접근하는 경우.
O(log n) (로그 시간): 입력 크기에 따라 실행 시간이 로그 비율로 증가하는 경우
이진 검색 알고리즘
O(n) (선형 시간): 입력 크기에 비례하여 실행 시간이 증가하는 경우
배열 내의 모든 값을 조회하는 경우
O(n log n): 입력 크기에 따라 로그 비율로 연산을 여러번 하는 경우
퀵 정렬, 병합 정렬
O(n²) (이차 시간): 입력 크기에 따라 실행 시간이 제곱으로 증가하는 경우
버블 정렬
O(2ⁿ): 입력 값의 모든 경우의 수를 계산하는 경우
피보나치 수열을 재귀적으로 계산할 경우
공간 복잡도
: 알고리즘이 수행되는 데 걸리는 메모리의 양에 따라 결정된다.
주요 복잡도
O(1) (상수 공간): 어떤 값을 입력 받던지 고정된 양의 메모리를 사용하는 경우
하나의 변수를 이용할때 데이터를 저장하는 경우
O(n) (선형 공간): 입력 크기에 따라 비례하여 메모리를 사용하는 경우
1차원 배열을 이용해 데이터를 저장하는 경우
O(n²) (이차 공간): 입력 크기에 따라 메모리 사용량이 제곱 비례하는 경우
2차원 배열이나 그래프로 데이터를 저장하는 경우'
정리하자면
코드를 효율적으로 작성하려면 알고리즘을 공부하자.
시공간 복잡도가 낮을 수록 효율적인 알고리즘이다.
복잡도는 표기법 별로 아래 순서대로 좋고 나쁨을 구분한다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)다음엔 알고리즘 별 처리 방법과 복잡도 차이를 적어보며 공부하겠다.