자바로 배우는 핵심 자료구조와 알고리즘 - 1. 시작하기

처음 소개글: https://steemit.com/kr/@yudong/62rzgy

오늘부터 "자바로 배우는 핵심 자료 구조와 알고리즘"을 시작합니다. 이 연재에서는 책에 있는 내용을 그대로 다루기 보다는 "번역"을 하면서 독자분들께 제가 들려드리고 싶은 내용 위주로 전개합니다.

원서는 CCL 라이센스를 따르고 있습니다.
링크: http://greenteapress.com/thinkdast/html/index.html

1. 책의 소스코드 받기

요즘의 IT서적은 거의 소스 코드를 github에서 제공합니다. 이 책도 다르지 않은데요.

다음의 URL에 접속해보세요

https://github.com/yudong80/ThinkDataStructures

만약 git이 익숙하지 않으시다면 zip 파일을 다운로드할 수도 있습니다.

https://github.com/yudong80/ThinkDataStructures/archive/master.zip

원래 저자의 github은 따로 있었는데 IDE 기반이 아니라서 그것을 바탕으로 인텔리제이(IntelliJ) 프로젝트를 추가하였습니다. 기존의 예제와 중복되지 않도록 별도의 폴더를 만들었습니다.

만약 인텔리제이를 쓰신다면 소스코드의 다음 폴더에서 프로젝트를 여시면 됩니다.
/intellij/code : 실습용
/intellij/solutions: 정답용

2. 자바 자료구조 기본 클래스

자바 언어에서 자료구조를 이루는 기본 클래스들에는 무엇이 있을까요?
책에서 언급된 클래스(인터페이스)는 다음과 같습니다.

1. List 인터페이스

• ArrayList 클래스 예제: https://github.com/yudong80/ThinkDataStructures/blob/master/intellij/solutions/src/main/java/com/allendowney/thinkdast/MyArrayList.java
• LinkedList 클래스 예제:
  https://github.com/yudong80/ThinkDataStructures/blob/master/intellij/solutions/src/main/java/com/allendowney/thinkdast/MyLinkedList.java

1. Map 인터페이스

• HashMap 클래스 예제:
  https://github.com/yudong80/ThinkDataStructures/blob/master/intellij/solutions/src/main/java/com/allendowney/thinkdast/MyHashMap.java
• TreeMap 클래스 예제:
  https://github.com/yudong80/ThinkDataStructures/blob/master/intellij/solutions/src/main/java/com/allendowney/thinkdast/MyTreeMap.java

일반적인 자바 프로젝트에서는 List와 Map 클래스정도만 활용해도 왠만한 상황을 커버할 수 있습니다. 그외에 Queue 계열의 클래스들(ArrayBlockingQueue 등)도 때에 따라 사용할 수 있습니다.

3. 알고리즘의 복잡도 분석

학부에서는 배우지만 (현업?)에서는 잘 쓰지 않게 되는 것들중에 하나는 빅오표기법입니다. 저도 번역하면서 부끄러웠던것이 대부분의 경우 for문이 1개면 O(n) 이고 for문이 중첩되면 O(n^2)라고 단순화해서 생각해왔기 때문입니다.

아마도 앱을 주로 개발하다보니 성능에 대해 많이 챌린지를 받지 않아서 그런것 같습니다.

하지만 다량의 데이터를 다루는 경우에는 복잡도 분석이 중요한 역할을 할 수 있습니다. 이유없이 느려지는 상황에서는 이러한 기본기가 특히 중요해집니다.

책을 번역하면서 새롭게 배우게 된 것은 분할 상환 기법(Amortized Analysis) 입니다.
위키: https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0%EC%83%81%ED%99%98%EB%B6%84%EC%84%9D

위키의 내용이 딱딱하긴 하지만 한번쯤 (기본기)를 위해서 읽어볼만하고 책에도 다양한 사례를 들어 친절하게 설명해주고 있습니다.

오늘은 여기까지 하고,
다음에는 성능 분석에 대해서 좀더 알아보도록 하겠습니다.

활기찬 6월 시작하세요 :-)
감사합니다.

2018.6.3

yes24 책링크: http://www.yes24.com/24/Goods/61198657?Acode=101

#kr #kr-dev #java #datastructure #jjangjjangman