알고리즘 라이프

 제목에도 있다시피 일상 속에서 알고리즘을 발견할 수 있다. 단순히 책에서 접하는, 코딩으로 접하는 알고리즘보다 어떻게 일상에서 쓰이는지 코드설명이 아닌 스토리텔링형식의 책을 보았다.

 

1. 양말 짝 찾기 = 해쉬이용(상수시간)(순서상관없음) // 배열이용x

 

2. 셔츠 쓸어담기 = 로그탐색,이진검색(logn)(단 셔츠는 크기별로 정렬이 되어있음) // 선형탐색x

 

3. 필요한 물건사기 = 스택이용 // ???

 

4. 미로 탈출하기 = 백트래킹(backtracking) 이용 , 트레마의 알고리즘, 네트워크와 그래프같은 특정 지점 특정 지점 이동

(오른손 법으로 탈출할 수 있지만 그럴경우 고립된 섬은 탐지 못한다... 로봇 청소기가 단순 오른손 법으로 섬 위치의 청소가 불가능하다...)

 

5. 쏟아진 우편물 주소에 따라 정리

= 분할정복 = 선형로그(nlogn) = n개를 logn 탐색으로 정리 = 이차미만시간에 정복(subquadratic)

= 병합정렬, 빠른정렬(quick sort)

 

//하나씩 정리하는 것은 이차시간 알고리즘(n^2)(quadratic time) = 삽입정렬, 버블정렬, 선택정렬

 

6. 위대한 음악듣기 = 링크분석 = 정도(degree)와 유사성(similar) 통해 링크로 네트워크 형성

즉, 인기많은 곡의 정도와 유사성에 가까울수록 계속 인기많은 음악을 들을 확률이 크다.

즉, 위대한 음악에서만 곡을 고르면 되므로 상수시간

//랜덤 선택하면 늦게 고를 수 있으믈 최악은 선형시간

 

7. SNS 관심받을 만한 상태메세지를 업로드 = 얼마나 많은 메모리나 디스크 공간이 요구되는지 공간복잡도 확인

= 허프만 코드방식 = 트리 다이어그램으로 최대 알파벳빈도 확인

 

8. 연말 송년회 전에 모든 잔업을 끝마쳐라

= 문맥전환(context switch) = 파이프라이닝(pipelining) = 인터럽트(interrupt)

= 그리디 알고리즘(greedy):현상태최소비용 = 다익스트라 알고리즘(dijkstra):최종적최소비용

= 우선순위대기열(priority queue)

 

9. 수제 이니셜 목걸이 고치기

= 링크드리스트(linked list):한쪽방향 이동가능 = 더블 링크드리스트(doubly linked list):양쪽방향 이동가능 = 상수시간

 

// 배열x (최악은 선형탐색)

 

10. 분리수거장에서 택배용 빈 상자를 찾아라

 

빅세타 = 상한계, 하한계 일정한 비율로 같이 증가

빅오 = 최악의 성능(그 함수는 상한계보다 더 빠르게 증가 못한다.)

빅오메가 = 최상의 성능(그 함수는 하한계보다 더 느리게 증가 못한다.)

보통 실무에서 빅오를 사용해 최악을 대비한다.

증가한다 = 성능이 안좋아진다.

 

11. 저자의 이름 순으로 책장을 정리하자

= 간격삽입정렬(gapped-insertion sort) = 미리 책 사이에 간격을 두어 몇권만 옮기면 사이에 속속 낄 수 있는 선형로그시간이 가능하다(삽입정렬의 수정)

= 빠른정렬(quick sort) (기준점이 최저값이나 최고값이 아닌상태이도록 주의!)

// 삽입정렬(n^2)

 

12. 마트에서 최대한 빠르게 필요한 물건만 쓸어담기

해쉬가 상수시간 검색이 보장된다. 하지만 충돌문제주의!

 

테이블 수 < 레코드 수

연쇄화 - 해당 해쉬값에 대응하는 곳에 그룹을 만듬

 

테이블 수 > 레코드 수

선형탐색법(해당 위치 다음에 계속 해쉬 추가하기)

이중해싱(해쉬값 2개로 계산해서 해쉬 추가하기)

 

이진탐색트리 - 삽입/삭제/탐색 모두 O(logn)

 

==========================================================================

간단한 예시를 통해 어느순간 사용해야 하는지 머리에 그려진다.

이것은 결국 알고리즘 개념과 문제풀이 뿐 만 아니라 최적화에 대한 개념을 심어주는 기초이다.

아직 실무와 연관되지는 않았지만 이 알고리즘이 아니더라도 코드를 깔끔하고 최적화 해야하는 중요성을 느낀다.