TIL 2022/06/17

1일1로그 100일완성 IT지식

021 검색을 쉽게 만드는 정렬 : 선택정렬 VS 퀵정렬

• 선택정렬 : 아직 정렬되지 않은 항목 중에서 다음 항목을 선택

Intel Facebook Zillow Yahoo Pinterest Twitter Version Bing
Apple Google Microsoft Sony PayPal Skype IBM Ebay

----------------------------------------------------------
1회차 - 16번 검색
Apple Intel Facebook Zillow Yahoo Pinterest Twitter Version
Bing Google Microsoft Sony PayPal Skype IBM Ebay

----------------------------------------------------------
2회차 - 15번 검색
Apple Bing Intel Facebook Zillow Yahoo Pinterest Twitter 
Version Google Microsoft Sony PayPal Skype IBM Ebay

-------------------------- ... ---------------------------
16회차 - 1번 검색
Apple Bing Ebay Facebook Google IBM Intel Microsoft
PayPal Pinterest Skype Sony Twitter Version Zillow Yahoo

데이터의 양에 대한 시간 증가율 :
N + (N-1) + ... + 2 + 1 = (N^2 + N)/2 = (약)N^2
(데이터의 양이 많아지면 N^2에 증가율에 대해 N은 무시할 수 있다.)

• 퀵정렬 : 분할 정복을 활용한 정렬

Intel Facebook Zillow Yahoo Pinterest Twitter Version Bing
Apple Google Microsoft Sony PayPal Skype IBM Ebay

----------------------------------------------------------
1회차 - 16번 검색
Intel Facebook Bing Apple Google Microsoft IBM Ebay
Zillow Yahoo Pinterest Twitter Version Sony PayPal Skype

----------------------------------------------------------
2회차 - 8 + 8번 검색
Facebook Bing Apple Ebay
Intel Google Microsoft IBM
Pinterest Sony PayPal Skype
Zillow Yahoo Twitter Version

-------------------------- ... ---------------------------
4회차 - 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 번 검색
Apple Bing Ebay Facebook Google IBM Intel Microsoft
PayPal Pinterest Skype Sony Twitter Version Zillow Yahoo

데이터의 양에 대한 시간 증가율 :
회차 데이터의 양 = logN N = NlogN
(각 그룹별 데이터의 양이 매 회차마다 logN개)

022 10개의 도시를 최단거리로 여행하는 법

• 지수알고리즘 : 데이터 양에 대한 시간 증가율이 2^N 비율로 증가 하는 알고리즘
  호율이 매우 떨어지지만 그러한 이유로 암호기법에서 사용된다.

• 다항시간 알고리즘(P) : N^2, N^3과 같이 복잡도가 다항식으로 표현되는 알고리즘

• 비결정적 다항시간(NP) : 다항시간 알고리즘으로 풀 수 없는 알고리즘 ex) 최단거리

• 최단거리 알고리즘 : N개의 지점 중 한 지점에서 출발해서 모든 지점을 중복 없이 방문하고 다시 그 지점으로 돌아오는 최단거리를 찾는 알고리즘 .
  최적의 경로를 찾기 위해서는 모든 경로를 확인하고 결정해야함(NP)
  but 근사치를 구할 수 있는 여러 알고리즘 존재(P) > 근사치만으로도 의미가 있다!

오늘의 한줄
몇가지 간단한 알고리즘을 통해 시간복잡도에 대한 개념에 대해 설명하고 있다.
오래전 배운 알고리즘과 시간복잡도에 대해 다시 기억하게 되었는데 여러 알고리즘들(정렬 등)을
자세하게 정리하고 직접 코드를 작성 해봐야겠다.