[TIL] 항해 22일차

-- 목차 --

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

 

알고리즘의 성능을 측정하는 기준

1. 정확성 : 동일한 입력에 대해 항상 동일한 결과를 반환하는가
2. 작업량 : 얼마나 적은 연산으로 결과를 만들어 내는가 ( 시간복잡도 )
3. 메모리 사용량 : 얼마나 적은 메모리를 사용하여 결과를 만들어 내는가 ( 공간복잡도 )
4. 단순성 : 얼마나 단순한 구현으로 결과를 만들어 내는가
5. 최적성 : 더 이상 개선한 여지가 없을 만큼 최적화 되어 있는가

---

1. 시간 복잡도
   • 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지 의미
   • 알고리즘을 위해 필요한 연산의 횟수
   • 복잡도를 표현하기 위해 빅오 표기법 사용
   • 최악의 경우에 대한 연산 횟수가 가장 중요
   • N의 범위에 따라 시간 복잡도를 계산하고 사용할 수 있는 알고리즘을 선택하는 방법도 있다.
2. 공간 복잡도
   • 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지 의미
   • 알고리즘을 위해 필요한 메모리의 양

빅오 표기법(O, big-O)
 - 입력값이 무한대로 향할 때, 함수의 상한을 설명하는 수학적 표기 방법

• 점근적 실행시간을 표기할 때 가장 널리 쓰이는 수학적 표기 방법
• 점근적 실행시간이란 N이라는 입력값이 무한대로 커질때의 실행 시간의 추이
• 따라서 충분히 큰 입력값에서의 알고리즘의 효율성에 따라 수행 시간이 크게 차이날 수 있다.

---

다항 시간(P) vs 비결정적 다항 시간(NP)

다항 시간 알고리즘(Polynomial-Time Algorithms)

클래스 P

결정론적 알고리즘으로 다항 시간 내에 해결되는 문제들의 집합

항상 올바른 답을 계산하는 방법

쉬운 문제는 복잡도 면에서 다항이다

 

클래스 NP

비결정론적 알고리즘으로 다항 시간 내에 해결되는 문제들의 집합

실제로 발생하는 문제나 근본이 되는 문제는 지수 알고리즘이 필요하다.

즉, 다항 알고리즘으로 풀 수 없다. (NP문제)

해결책을 빨리 찾을 수는 없지만, 어떤 해결책을 알고 있다면 그것이 맞는지는 빨리 입증할 수 있다.

= 결정을 내려야 할 때 항상 옳게 추측하는 알고리즘이 있다면 NP문제가 그 알고리즘에 의해 다항 시간 내에 해결될 수 있다

---

여행하는 외판원 문제(Traveling salesman problem)

• 외판원은 자신이 사는 도시에서 출발해서 어떤 순서로든 다른 도시를 모두 방문하고 나서 다시 출발점으로 돌아와야 한다.
• 이때, 각 도시를 한번씩만 방문하고, 전체 여행한 거리를 최소로 만들어야 한다.
• 즉, 가능한 모든 해법을 완전 탐색하는 것보다 더 효율적으로 풀 방법이 없다. (우리가 덜 똑똑해서 그런게 아니라 문제가 본질적으로 난해하기 때문이다.!)
• 그래프 이론 용어로 "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순회를 구하라" 라고 표현할 수 있다.
• 도시를 나열하는 방법은 (n-1)! 가지 이다. (비효율)
• 효율적으로 구하는 방법 : DP 메모제이션(중복 제거), 비트마스킹(공간복잡도를 줄이기 위해 2^N 의 경우의 수를 Nbit로 표현) 알고리즘

복잡도를 다룰 때 명심해야 할 점!

최악의 경우 까지 가지 않는다.

= 어떤 문제는 답을 계산하는 데 극한의 시간이 필요하겠지만 모든 문제를 그렇게 난해하게 접근할 필요는 없다.

 

얼마나 빨리 계산할 수 있는가?

• 알고리즘과 복잡도 연구는 컴퓨터 과학의 주요 영역으로 이론과 실제 적용 모두 중요한 연구 대상이다.
  • 어떻게 하면 더 빨리 계산할수 있는지, 메모리를 필요 이상으로 사용하지 않을 수 있는지, 처리 속도와 메모리 소비 간 균형을 유지하면서 계산할수 있는지 등...

앞으로 만날 주요 알고리즘..

통신네트워크와 관련 (3장)	압축 알고리즘	텍스트, 음악, 이미지, 동영상 등을 기억장치에서 차지하는 용량을 줄이려고 시도
	오류 검출 알고리즘	데이터에 세심히 관리된 여분의 정보를 추가하는 알고리즘으로 오류 검출
	수정 알고리즘	검출된 오류를 수정하는 알고리즘
보안 통신(4장)	암호화 알고리즘	메시지를 암호화하는 알고리즘 비공개 정보를 안전한 방식으로 주고받는 것
검색엔진(4장)	검색 엔진 알고리즘	웹페이지를 수집하고, 검색하기 쉽게 정보를 조직화하고, 효율적으로 정보를 검색하는 것 데이터의 규모와 작업의 규모가 매우 크다.

• 알고리즘은 음성이해, 얼굴과 영상 인식, 언어의 기계번역 같은 서비스에서 핵심을 차지하기도 한다.
• 이런 서비스에서는 관련된 특징을 발굴 할 수 있는 데이터를 최대한 많이 보유하는 것이 중요하다. (AI 와 빅데이터)
• 이때, 선형 알고리즘 이상의 성능을 지녀야 하고 개별 처리 작업이 다수 프로세서에서 동시에 실행될 수 있도록 병렬화가 가능해야 한다(4장)

https://gazelle-and-cs.tistory.com/64

https://d2.naver.com/helloworld/0315536

 

정규식

https://pingfanzhilu.tistory.com/entry/Java-%EC%9E%90%EB%B0%94-%EB%B9%84%EB%B0%80%EB%B2%88%ED%98%B8-%EC%A0%95%EA%B7%9C%EC%8B%9D-%ED%8C%A8%ED%84%B4Pattern-%EB%A9%94%EC%86%8C%EB%93%9C

 

exception

https://samtao.tistory.com/42

Springboot Exception Handling(스프링부트 exception 핸들링)

jwt

https://velog.io/@cada/%ED%86%A0%EA%B7%BC-%EA%B8%B0%EB%B0%98-%EC%9D%B8%EC%A6%9D%EC%97%90%EC%84%9C-bearer%EB%8A%94-%EB%AC%B4%EC%97%87%EC%9D%BC%EA%B9%8C

https://bcp0109.tistory.com/301

https://lemontia.tistory.com/1021