이제 실제로 코드를 최적화하는 일만 남았다. 물론 최적화에 앞서 현재 알고리즘의 빅 오를 알아내는 단계가 필요하며, 이를 개선할 수 있는 최상의 빅 오를 '상상'하면서 문제를 풀어나가보자. 1. 룩업 최적화 기법 중 하나는 'O(1) 시간 안에 원하는 정보를 찾을 수 있는지' 자문하는 방법이다. 1) 두 수의 합 문제 두 수의 합으로 10을 만들 수 있는지 확인해보는 함수를 만든다고 생각해보자. 예를 들어, [ 2, 0, 4, 1, 7, 9 ] 같은 배열이 주어졌을 때 두 수를 합해 10을 만들 수 있을까? 단순하게 생각하면 중첩루프를 사용해 모든 수를 더해보는 방법이 있다. >>> 2+0 2+4 2+1 2+7 2+9 ... 없군 >>> 0+2 0+4 0+1 0+7 0+9 ... 없군 >>> 4+2 4+..

여지껏 알고리즘 효율성 분석에서 알고리즘이 얼마나 '빠른가', 즉 시간 복잡도에만 초점을 맞춰왔다. 그러나 알고리즘이 얼마나 많은 메모리를 소모하는지도 효율성의 척도가 되는데, 이를 공간 복잡도(space complexity)라 부른다. 메모리는 무한하지 않으며, 대량의 데이터를 다루거나 메모리가 제한된 작은 장치를 프로그래밍할 때는 공간 복잡도가 매우 중요해진다. 이상적으로는 빠르고 메모리 효율적인 알고리즘이 최고지만, 둘 다 만족시킬 수 없는 상황이 즐비하기때문에 메모리와 속도 사이에서 우선순위를 매기는 능력 또한 중요하다. 1. 공간 복잡도의 빅 오 시간 복잡도와 마찬가지로 공간 복잡도 또한 빅 오 표기법을 사용한다. 애초에 빅 오란 "핵심 질문"에 대한 답을 표현하는 수단이다. 즉, 시간 복잡도에..

친구 관계를 데이터로 조직한다고 해보자. 어떤 방식으로 만들겠는가? 단순하게는 배열로 저장해볼 수 있겠다. 친구관계 = [ ["A","B"], ["B","C"], ["A","C"], ["B","D"], ["E","F"], ... ] 불행히도 A의 친구가 누구인지 확인도 어렵고, 컴퓨터는 확인을 위해 일일이 배열을 뒤져봐야 하므로 O(N)이 걸리는 매우 느린 방법이다. 이럴 때 그래프라는 자료 구조를 사용하면 O(1) 시간 만에 찾아낼 수 있다. 1. 그래프 관계에 특화된 자료 구조로서 데이터가 연결된 모습을 쉽게 이해시켜 준다. 아래 그림처럼 사람을 노드로, 관계를 선으로 표현한다. 진짜로 1.1 그래프 vs 트리 사실 트리도 노드들이 서로 연결돼있는 자료구조였다. 그럼 트리도 그래프 아닌가? 맞다. 사..

자동완성 기능이 어떻게 동작하는지 궁금해본적이 있는가? 단어들을 어떤 자료 구조에 저장해야 효율적으로 구현이 가능할까? 케이스별로 한번 살펴보자 검색과정 시간복잡도 정렬X 배열 모든 단어를 검색해야 한다 O(N) 정렬된 배열 이진 검색 O(logN) 해시 테이블 단어를 통짜로 해싱해서 메모리 위치를 결정하므로 일부의 단어로 찾는다는거 자체가 말이 안된다 X 정렬된 배열이 O(logN)으로 빠르긴 하다. 그런데 트라이 자료구조를 사용하면 O(1)의 속도로 원하는 단어에 접근이 가능하다! 실제로 트라이는 자동완성, 자동수정, IP주소 처리, 전화번호 처리 등의 애플리케이션에 쓰인다. 1. 트라이(trie) 트리의 한 종류로, 자동 완성 텍스트 기능에 매우 이상적인 자료구조. 근데 왜 발음이 트라이일까? 트라..

지금까진 최악의 시나리오에 초점을 맞춰왔으나, 실제가 모두 최악의 시나리오로만 굴러가는 것은 아니다. 따라서 모든 시나리오를 고려하면서 어떤 상황에서든 적절한 알고리즘을 고를 수 있는 능력은 매우 중요 1. 삽입 정렬(insertion sort) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 삽입 정렬을 통해 최악의 경우가 아닌 다른 시나리오 분석에 어떤 의미가 있는지 알아보자 이런 방식인데 두번째 요소부터 마지막 요소까지 값을 임시로 제거하고, 그 이전 값들과 비교하면서 제 위치를 찾아가는 정렬이다. 위 그림의 경우 총 22단계가 소요된다. 2. 삽입 정렬 구현(python) def insertion_sort(a..

빅 오는 분명 훌륭한 판단 지표이긴 하나 유일한 지표는 아니다. 같은 효율성을 갖는다고 해도 실제로는 어느 하나가 더 빠른 경우가 많기 때문이다. 효율성이 같아 보이는 두 알고리즘을 뭐가 더 빠른지 어떻게 골라낼까? 5.1 선택 정렬(selection sort) 매 패스스루마다 가장 작은 값을 찾아서 맨 앞으로 빼내면서 정렬하는 알고리즘 아래 예시는 총 12단계가 소요된다 5.2 선택 정렬의 효율성 ( O(N²) ) 선택 정렬은 비교 function selectionSort(arr: number[]) { for (let i=0; i