정글 6일차 TIL (알고리즘의 정의,설계,분석)

• 책읽기: Introduction to Algorithms 40페이지까지 읽어보았다.
• 문제풀기: 18번문제까지 풀었다. 외판원 순회 2 에러 푸느라 애먹었다. 베이스 케이스를 잘못 잡아서 고생했다.

2023.10.17 - [정리] - 알고리즘과 자료구조의 정의

타당하지 않은 알고리즘도 유용할 수 있다는 것을 다시 한번 상기됐다.

알고리즘과 자료구조의 정의

2023.10.17 - [정리] - 알고리즘의 분석

어렴풋했던 내용을 정리하고 넘어갈 수 있었다.

알고리즘의 분석

2023.10.17 - [TIL] - 알고리즘의 설계

루프 타당성, 분할 정복의 3단계의 개념을 알고 나니 좀 더 알고리즘을 짤 때 명확해졌다.

특히 분할 정복의 3단계는 복잡한 문제(하노이 문제, N퀸 문제, 외판원 순환문제2) 에서 많은 도움이 되었다.

알고리즘의 설계

NP-완비 문제(Nondeterministic Polynomial)

• 최적해가 알려지지 않은 문제 중 하나
• 특징
  1. 효율적인 알고리즘이 발견되지 않았지만, 그런 알고리즘이 없다는 것도 증명되지 않았다.
  2. NP-완비 문제 중 단 한 문제에 대한 효율적 알고리즘이 존재하면 다른 모든 문제에 대한 효율적 알고리즘도 존재한다.
  3. NP-완비 문제 중 일부가 효율적 알고리즘이 알려진 다른 문제와 일치하지는 않지만, 상당히 유사하다.
     • 문제 정의를 조금만 바꿔도 알려진 효율적 알고리즘의 성능에 엄청난 변화가 생길 수 있다.
• NP-완비 문제에 대한 효율적 알고리즘을 만들려고 한다면 상당한 시간이 걸릴 수 있다.
• 대신, NP-완비임을 보일 수 있으면, 최적해는 아니더라도 상당히 좋은 해는 찾을 쓸만한 알고리즘을 개발하는 것이 낫다.
• 즉, 빨리 포기하고 workaround 찾는게 낫다.

---

시간상 모든 정리를 나만의 언어로 바꿔서 쓰지는 못했다. 그래도 적어두고 다시 찾아볼 수 있는 것에 일단 만족.