![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/dr1b3k/btqBL7wORvE/IBiSmUo2LCkN0Fv9M1mX60/img.png)
1. 탄생 배경 이 알고리즘의 저자인 다익스트라는 1956년 암스테르담에서 ARMAC이라는 새로운 컴퓨터의 성능을 보여주기 위한 적절한 주제를 고민하고 있었다고 한다. 그러던 어느 날 오전에 쇼핑을 하던 중 지쳐서 카페에서 커피를 마시다가 최단 경로 탐색 법을 고민하게 되었고 이 알고리즘을 약 20분(...!) 만에 완성했다고 한다. 2. 이해하기: 다익스트라 알고리즘 2-1. 기본 로직 다익스트라 알고리즘은 하나의 시작점에서 다른 모든 점들까지의 최단 경로를 구한다. 어떠한 원리로 최단 경로를 찾아가는지 직관적으로 이해를 돕기 위해 아래의 예시처럼 가장 기초적인 그래프부터 살펴보겠다. 1) 첫 단계는 현재 노드를 기준으로 나머지 노드들까지의 거리를 계산을 하는 것이다. 인접해 있는 노드들은 해당 거리(..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/szDqT/btqBj7bvRx1/LWDgMXZIEq21K3MM4Kvk1k/img.png)
1. 탄생 배경 Trie는 1959년 René de la Briandais의 라는 논문에서 처음으로 등장하였다. (Trie라는 단어 자체는 2년 후에 만들어졌지만 Trie의 기본 알고리즘은 이 논문이 최초라고 한다) 논문의 내용을 정말 간단하게 요약하자면, 모든 Search의 성능은 주어진 데이터의 크기 (N)가 가장 큰 결정 요소인데 이것을 해결하기 위해 고안된 자료구조이다. 즉, Search 연산에 대한 전체 복잡도를 주어진 데이터 크기와 최대한 상관이 없도록 만들어진 것이다. 하지만 이러한 문제점을 극복하기 위해 HashTable이라는 자료구조도 나오지 않았는가? 그러나 당시 컴퓨터들에게는 Hash 방식을 비롯한 기존 방식들이 가지고 있는 몇 몇 문제점들이 있었다. 1) Hashing의 문제점 Tr..
- Total
- Today
- Yesterday
- 스프링
- 2020 KAKAO
- Kakao Blind
- 모던 자바 인 액션
- behavior parameterization
- PatternSyntaxException
- WORA
- 2019 Kakao Blind
- trie 소스코드
- Java #JIT #JVM
- 2021
- decorator
- jvm
- 디자인패턴
- WORE
- 신규 아이디 추천
- nginx 내부
- okhttp3
- 카카오 인턴
- 코테
- Java
- IOC
- 프로그래밍 모델
- KAKAO 2021
- 카카오
- 카카오 코테
- digital tree
- 카카오코테
- Java #GC #가비지콜렉터 #Garbage Collector
- 스프링 컨테이너
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |