Hello Coding 그림으로 개념을 이해하는 알고리즘

 

Hello Coding 그림으로 개념을 이해하는 알고리즘

- 책 소개 -

어떠한 문제에 맞닥뜨렸을때 어떤 알고리즘을 선택할 수 있는지 기본적인 선택지를 주는 책이다. 여러가지 상황에서 사용되는 대표적인 방법을 소개하고 그 알고리즘의 성능과 장/단점, 한계에 대해서 설명한다. 그림 형태로 알고리즘의 동작 원리에 대해 설명하여 이해하기가 쉽다. 아쉬운점은 활용 방안에 대한 예시? 어떤 상황에 어떤 알고리즘을 떠올려야 하는지 설명은 해주는데 완전히 흡수한 것 같지는 않다.

이 책을 시작으로 관심을 가지고 공부를 시작하라는 책의 의도가 많이 보인다. 목차에 나와있는 내용을 설명하면서 여러가지 알고리즘을 소개한다. 다익스트라 알고리즘의 한계(음의 가중치를 가질수 없다)를 설명하면서 벨만-포드 알고리즘을 소개하는 식이다.

 

알고리즘 문제 풀이에 앞서서 기본적인 알고리즘에 대한 이해와 학습에 관성을 만들려고 매일 아침 일찍 출근해서 짬짬이 읽었다. 내일 학습한거 공유하는 시간을 가지고, 이 다음에는 각 알고리즘을 직접 짜보거나 바로 문제 풀이 단계로 넘어갈 생각인데 문제 풀이도 문제의 식별과 설계, 구현 단계로 나눠서 정리하고 분류해놔야 남는게 있을것 같다. 따로 React로 개발할게 있어서 학습도 해야되는데 병행할지는 고민하고있다.

 

문제에 대한 기본 선택지가 생긴다

의사결정트리 피피티로 만들어서 추가

- 요약 -

• 빅오 표기법
  • 데이터량이 증가함에 따른 알고리즘의 연산 횟수를 비교하기 위한 표기법
  • 직접적인 처리 속도를 나타내지는 않는다. 빅오 표기법은 최대차수항만 표현한다.
  • 빅오 표기법은 최악의 경우를 나타낸다. 평균 실행 시간을 살펴보는 것도 중요
• 배열과 연결 리스트
  • 배열과 연결 리스트는 장단점이 존재한다.
  • 배열과 연결 리스트를 복합적으로 사용하면 둘의 장점만 가져올 수 있다. 단점을 상쇄할 수 있다.
  • 자료에 접근하는 방식은 임의 접근(Random Access)과 순차 접근(Sequencial Access)이 있다.
  • 배열은 임의 접근이 가능하다. == O(1) == 데이터의 수량에 상관없이 조회 속도가 빠르다.
• 분할 정복 & 재귀
  • 알고리즘은 분할 정복이 많다. 분할정복은 재귀로 한다.
  • 분할 정복 개념은 프로그래밍 할때도 적용하면 좋다.
  • 내가 재귀를 사용했을 때는 이 단계에서 결정된 결과로 그 다음 단계를 진행해야 하는 경우 였다.
  • 코딩할떄도 큰그림 그릴때 단계별로 분할하고 각 기능은 블랙박스화(Stateless) 해서 자기 역할은 자기가 책임지고 한다고 딱 정하는 식으로 하면 막짜는것보다 훨씬 빠르다. 일단 분할해서 빈 메서드, 객체들을 쭉 만든다.
• 퀵 소트 & 머지 소트
  • 퀵소트는 분할 할 때 정렬된다. 마지막에 합칠때는 후다닥 합친다.
  • 머지 소트는 분할하고 합칠때 정렬된다. 분할할때는 반으로 딱딱 바로바로 쪼갠다.
  • 머지 소트는 분할 스택이 예쁘게 균일하게 나눠진다. 균일한 성능을 보인다.
  • 퀵 소트는 기준(pivot)을 잘못 고르면 한쪽으로 다 쏠려서 O(n^2)도 나올 수 있다.
  • 검색하다 나온 키워드 중에 introsort, heapsort 가 나온다. 요런건 최악의 경우에도 O(n*logn)이라고 한다.
  • 그럼에도 퀵 소트가 더 빠르고 좋다고 하는데 그 이유는..
  • https://qastack.kr/programming/70402/why-is-quicksort-better-than-mergesort
  • https://medium.com/pocs/locality%EC%9D%98-%EA%B4%80%EC%A0%90%EC%97%90%EC%84%9C-quick-sort%EA%B0%80-merge-sort%EB%B3%B4%EB%8B%A4-%EB%B9%A0%EB%A5%B8-%EC%9D%B4%EC%9C%A0-824798181693
  • 더 공부하기 : http://www.secmem.org/blog/2019/04/10/special-sorts/
• 해시 테이블이 왜 빠른가? 알아보니 아 이래서 빨랐구나 싶다. 써도되면 무조건 써야된다.
• 다익스트라 알고리즘 아주 깔끔하고 좋다.

병합 정렬보다 빠른 정렬이 더 좋은 이유는 무엇입니까?

Locality의 관점에서 Quick sort가 Merge sort보다 빠른 이유