책 <(일상 속 스마트한 선택을 위한) 알고리즘 라이프>를 정리했습니다.
배열의 대안 : 연관배열 = 사전 = 해시표
- 둘의 공통점
- 하나의 집합에 데이터를 보관한다
- 둘의 차이점
- 해시표는 즉각적 검색 (=상수시간 검색)
- 상수시간 검색의 공식이 해시함수
- 해시함수는 특정 더미에 어떤 항목을 포함 시켜놓고, 그 항목을 빨리 찾을 수 있게 한다.
- 상수시간 검색의 공식이 해시함수
- 해시표는 즉각적 검색 (=상수시간 검색)
- 이런 식으로 이미 알고있는 사실(기억력)을 이용한 해결방법은 반복 작업에 유용하다.
로그시간
선형시간에서 로그시간으로 바꾸는 이점은 아주 많다.
로그시간은 물건이 정렬되어있을 때 유용하다.
- 로그시간의 예시 : 사전, 전화번호부, index ⇒ 정보폐기 방법 → 이진검색!
로그는 천천히 증가한다 = 방법이 항목의 수에 크게 영향을 받지 않는다는 뜻
역추적
미노스 아리아드네의 실 이야기 = 미로 탐색할 때, 실패 시 갈림길로 돌아가서 다른 경로를 탐색하는 방법
⇒ 트레마의 알고리즘 (개미도 사용한다!)
- 이미 미로에 들어가있을 때 빠른 방법이다
- 미로 같은 제한적인 환경의 경로 탐색에 유용하다
- 예시 : 네트워크, 로봇청소기, 길찾기
- edge가 통로고, vertex가 교차로고!
이차시간quadratic 알고리즘
하나를 찾아내기 위해 전체 집합을 살피는 것.
인접항목을 비교하면 여기에 해당. n^2
삽입, 선택, 버블
분할정복
작은 문제로 쪼개라!
즉, 반으로 쪼개고 쪼개고 쪼개서 / 이 집합을 정렬하는 것이다.
반으로 쪼개기에 당연히 로그시간이 걸리고 / 이 집합을 합치는 과정에서 선형시간이 된다 (모든 항목을 한번씩만 방문하니까) ⇒ 선형로그시간
n^2보다는 빠르고, 선형시간보다는 약간 느리다 ⇒ n log n
퀵 힙 병합
링크 분석
링크=관계
⇒ 이것들 중 어떤 것이 가장 중요한가
예시 : 논문은 인용수가 많을 수록 좋은 논문, 이를 활용한 구글 검색
이 관계는 연결정도degree와 유사성similar로 나뉜다
연결정도 degree
도식화하면 네트워크 같은 모양이 된다.
그러나 간접적인 연결 관계는 나오지 않는 문제가 있다.
이를 해결하기 위한 행렬 복합! (2차원 배열의 형태)
예시 : 다른 부품과 가장 많이 연결된 부품 목록
유사성similar
예를 들어 노래의 유사성을 찾으려면, 그 음악가의 음악을 듣는 사람들이 어떤 음악을 많이 듣는지 조사하면 된다.
이는 자카드 지표라는 것을 이용 시 유용
ex. 검색 엔진의 고객님이 좋아할만한 품목, 팔로워 추천, 스트리밍 추천
좋아하는 노래를 찾을 때까지 걸리는 시간
- 레코드를 전부 사서 좋아하는 노래를 찾을 때까지 무작위로 다 들어보는 방법 ⇒ 최악의 경우 n^2
- 내가 좋아하는 가수가 영향을 준 노래의 집합 안에서 골라 들어보는 방법 ⇒ O(1)
Reference
- <(일상 속 스마트한 선택을 위한) 알고리즘 라이프>, 알리 알모사위
