[리뷰]쓰면서 익히는 알고리즘과 자료구조

 

[목차]

chapter 1 배열(Array)

chapter 2 문자열(String)

chapter 3 연결 리스트(Linked List)

chapter 4 스택(Stack)과 재귀(Recursion)

chapter 5 큐(Queue)

chapter 6 트리(Tree)

chapter 7 동적 프로그래밍(Dynamic Programming)

chapter 8 정렬(Sorting) 알고리즘

 

[서평]

왜 알고리즘을 배워야 할까?

알고리즘을 그냥 네임드 회사의 코딩 인터뷰&테스트를 위한 용도로만 생각 했었다. 하지만 현업 개발을 하다보면 ‘시간 복잡도’, ‘공간 복잡도’ 같은 개념을 알고 프로그래밍하는 차이는 나중에 엄청나게 차이가 나게 된다. 개발과정에서 현실적인 문제 해결을 위해 어떤 자료구조와 알고리즘을 써야 하는지 고민하게 되는 좋은 습관이 생겼고, 다른 개발자들의 코드를 리뷰 하는 과정에서 좋은 제안도 할수 있을 것이다.

 

노트 레이아웃을 이용한 알고리즘 문제 풀이 접근 방법

• 문제 분석과 함께 어떤 알고리즘과 자료구조가 적절한지 파악한다.
• 문제로 부터 요구사항과 제한 사항을 수집한다.
• 어떤 식으로 접근할지 다양한 아이디어를 제시한다.
• 코딩을 통합개발환경 도움 없이 화이트 보드나 종이에 연습한다.
• 시간/공간 복잡도를 고려한다.
• 어떤 테스트 케이스를 통과 하는지에 대해 고려한다.

 

노트 레이아웃 소개

알고리즘 문제를 접하고 바로 코딩을 시작하게 되면 종종 제한사항을 잘못 인지하거나 고려하지 못한 테스트를 보는 경우가 생긴다. 하지만 이 레이아웃을 활용하게 되면 제한 사항과 테스트를 미리 적을 수 있어 이러한 실수를 줄일 수 있다.

 

Constraints(범위, 제한 사항)

알고리즘 문제를 풀다 보면 기본 변수 타입의 범위를 벗어나는 경우가 있다. 예를 들어 정수형이 가질수 있는 값보다 크거나 작아지는 경우, 배열이나 리스트 범위를 벗어나는 경우, 문자열의 길이를 제한하는 경우, 추가적인 메모리 할당을 제한하는 경우 등 다양하게 나타 날 수 있는데 이러한 제한사항을 미리 파악해야 한다.

 

문자열, 배열 그리고 숫자

배열은 얼마나 많은 요소들을 가질수 있는가?

문자열의 경우는 길이가 얼마나 길어질 수 있는가?

배열에서 요소들이 유일한 값으로 채워져 있는지, 중복을 허용하는지 확인 하자.

 

반환값

문제의 반환값은 어떤 형태이고 어떤 값을 원하는지 정확히 파악하자. 만약에 배열에서 증가하는 최장 공통부분 수열을 구한다고 하자. 이때 반환해야 하는 것은 길이 인지 시작 인덱스인지 혹은 둘다 인지 확인할 필요가 있다.

 

Ideas(문제 풀이 접근 방법)

보통 문제 풀이 방식은 1~3개 정도다. 예를 들어, 배열에서 특정 값을 찾는다면 배열의 처음부터 하나씩 확인하며 해당 값을 찾아갈 수도 있고, 정렬된 배열이라면 이진 탐색을 진행할 수도 있다. 이런 식으로 어떤 알고리즘 혹은 자료구조를 활용할지 접근해보는 연습을 해보자.

 

Complexity(복잡도)

자신이 생각한 알고리즘이나 자료구조를 사용하여 문제를 해결하는데 얼마나 시간이 걸리지, 얼마나 많은 공간을 사용해야 하는지에 대한 지표를 제공해주기 때문에 얼마나 최적화되어 만들어 졌는지 쉽게 인지할 수 있다.

 

Code(코드 작성)

아이디어에 해당하는 내용을 코드를 작성한다. 본인이 사용하는 언어로 개발도구에 의존하지 않고 작성하는 연습을 해보자. 또한 자신이 생각하는 알고리즘에 대한 구현은 어떻게 해야 할지 고민을 해야 한다.

 

Test Cases(테스트 케이스 검토)

가장 기본적인 입력에 대한 검증이 가장 중요하다. 우선 본인이 구현한 코드로 문제에서 제공하는 입력 해결을 해야 한다.

책의 구성

자료구조와 알고리즘을 분류하고, 각 자료구조와 알고리즘에 해당하는 문제를 분석하고 문제 풀이를 진행 하는 방식으로 구성되어 있다.

 

자료구조 및 알고리즘 설명

다양한 자료구조와 알고리즘의 기본적인 설명을 기술한다. 코드는 파이썬으로 만들어졌으며, 라이브러리 호출이나 사용법을 설명이 잘되어 있다. 각 챕터별 자료구조 기분으로 코딩 문제 풀이를 파이썬으로 설명하고 있다. 

 

이책에서 언급한 자료구조를 중심으로 학습한다면 온라인 코딩 테스트 사이트의 쉬운,보통 수준의 문제를 어느 정도 해결이 가능 할것이며, 코딩 테스트 및 코딩 인터뷰를 준비하는데 크게 무리가 없을것이라 생각한다.

 "한빛미디어 <나는 리뷰어다> 활동을 위해서 책을 제공받아 작성된 서평입니다."