누구나 자료구조와 알고리즘

대학교를 전자공학부로 나와서 컴공에서 기본적으로 배우는 자료구조와 알고르즘에 대한 지식이 부족한듯 싶어 보게된 책이다. 전공책으로 쓰일법한 두꺼운 바이블 같은 책이 아닌, 쉽고 가볍게 시작할 수 있는 책으로 느껴 졌기도했기 때문에. 

그리고 읽고나니, 정말 가벼운 책인 듯하다. 자료 구조와 알고리즘에 대한 기초를 알 수 있는 그러한 책. 요리로 치면 메인은 아니지만, 맛있는 디저트 혹은 에피타이저 같은. 이제 입문을 했으니 더 깊은 바다로 들어갈 준비가 된 것 같은 느낌이다. 

지은이(제이 웬그로우)가 코딩 전문 교육자라 그런지 이해하기 쉽게 잘 쓴 듯하다. 

   주요 내용 정리

● 빅 오 표기법

원래는 수학 개념이다. 전산학에서 빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계수만을 고려하며, 입력 값이 증가 함에 따라 단계수의 증가 성향(패턴?)을 이해할 수 있다. 따라서 비오 표기법을 이용하여, 각 알고리즘의 복잡도를 비교하면 어떤 알고리즘이 해당 시나리오에 더 효율적일지 알 수 있다. 

하지만 어떤 두 알고리즘의 빅오 표기값이 같더라도 어느 한쪽의 속도가 더 빠를 수 있다. 빅오 표기에는 생략하는 부분이 있기 때문에.  

빅오 표기에서 상수는 무시한다. 예를 들어 O(N/2) 는 O(N)으로 표기한다.

그리고 가장 높은 차수의 N만 고려한다. 예를 들어 O(N^4+N^2) 일 경우, O(N^4)로 표기한다. 

공간 관점(메모리 점유)에서의 복잡도도 빅오 표기법을 이용한다. 

● 자료 구조

자료구조에 사용하는 기본 연산은 읽기, 검색, 삽입, 삭제가 있다. 이들 연산이 "얼마나 빠른가"를 측정할 때 시간 관점이 아닌 얼마나 많은 단계(step)를 거쳐야 하는지에 대해 알아보면서 각 자료구조의 특징을 이해하고, 적합한 자료구조를 선택하는 방법에 대해서 간단히 언급한다. 

• 배열 : 가장 기본적인 자료 구조, 메모리에서 연속적인 공간을 할당 받는다. 중복되는 data를 허용한다.
• 집합 : 배열과 거의 같으나, 중복되는 data의 입력(삽입)을 허용하지 않는다. 따라서 삽입 전에 검색이 우선된다. 
• 해시 테이블 : 읽기가 빠른( O(1)) 자료 구조. 문자를 숫자로 변환하는 과정을 해싱이라고함. 그리고 그 변환 함수를 해시 함수라고 부른다. 좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다. 이상적인 셀과 데이터의 비율(부하율)은 0.7정도 이다. 
• 스택 : 입력(삽입)은 맨뒤에, 삭제도 맨뒤에서만이라는 제약이 있는 자료구조. Last In First Out (LIFO)
• 큐 : 입력은 맨뒤에, 삭제는 맨앞에서 부터라는 제약이 있는 자료구조. First In First out (FIFO)
• 연결 리스트(linked list) : 메모리를 효율적으로 관리 가능한 자료구조. 
• 이진 트리 : 검색, 삽입은 쉽지만, 삭제가 복잡해 보이지만, 검색과 삽입처럼 삭제도 O(logN)이다.
• 그래프 : 데이터들 간의 관계에 특화된 자료 구조. 방향 그래프와 무방향 그래프가 있다. 응용버전으로 가중 그래프라는 것도 있다. 

● 알고리즘

알고리즘이란 문제를 해결하는 절차를 의미한다. 자료 구조를 결정했더라도 어떤 알고리즘을 적용하느냐에 따라 효율성에 큰 영향을 미친다. 

• 선형 검색
• 이진 검색 : 정렬된 자료를 기반으로 검색 방법. 데이터 수가 N일때, O(log N) 단계를 가진다.  
• 버블 정렬 : 가장 기본적인 정렬 알고리즘. 비교와 교환이라는 단계를 포함하고 있다. 데이터수(N) 증가함에 따라  O(N^2)의 단계수 증가
• 선택 정렬 : 비교와 교환 두 단계를 포함한다. 버블 정렬과 같은 O(N^2)의 단계수를 가지지만, 버블정렬보다 약 2배 빠르다. 
• 삽입 정렬 : 삭제, 비교, 시프트, 삽입 네종류의 단계를 가진다. 최악의 시나리오에선 O(N^2), 최선의 시나리오에서는 O(N)의 단계수
• 퀵 정렬 (재귀 알고리즘) : 매우 빠른 정렬 알고리즘. 대다수의 언어가 내부적으로 구현해 놓음. 최악의 시나리오에서도 삽입이나 선택정렬과 비슷한 성능
• 퀵 셀렉트 : 퀵정렬에 이진 검색알고리즘의 특징을 적용한 것. 
• 딕스트라 알고리즘 : 최소 코스트를 찾는 알고리즘 중 가장 기본이되는 것.

   마음에 드는 문장 

모든 상황에 완벽하게 들어맞는 단 하나의 자료 구조나 알고리즘은 거의 없다. 

최선의, 평균, 최악의 시나라오를 구분하는 능력은 기존 알고리즘을 최적화해서 훨씬 빠르게 만드는 것만큼이나 사용자 요구에 맞는 최적의 알고리즘을 고르는 핵심 기술이다. 최악의 경우를 대비하는 것도 좋지만 대부분은 평균적인 경우가 일어난다는 점을 명심하자. 

개발자가 가장 효율적이라고 생각한 결정이 다양한 외부 요인(컴퓨터 언어의 내부적 구현 방식, 하드웨어 내에 메모리가 조직되는 방법 등) 때문에 아닐 수도 있다. 따라서 벤치마킹 도구를 이용해 항상 개발자가 수행한 최적화를 테스트 하는 것이 좋다. 코드 속도와 메모리 소비를 측정 할 수 있는 훌륭한 소프트웨어 애플리케이션이 많다.