[TIL]230306 - 알고리즘 1주차: The Role of Algorithms in Computing

알고리즘이란

• 문제 해결을 위한 잘 정의된 절차

Problem(문제)는 무엇인가

• 잘 지정된 입력 및 출력
• 예) 정렬문제

정렬, Binary Search 모두 같은 값이 존재할 수 있음
만약 같은 값이 있다면 잘 동작할까?
Binary Search는 Worst Case = O(lg N)
Search Key가 중요함
Priority Queue도 같은 값이 들어있을 수 있음

---

알고리즘

• 입력을 받아 출력을 생성하는 잘 정의된 계산 절차
• 입력을 출력으로 변환하는 일련의 계산 단꼐
• 잘 지정된 계산 문제를 해결하기 위한 도구
• 알고리즘은 입출력 관계를 달성하기 위한 특정 계산 절차를 설명함
• 문제의 인스턴스(입력) vs 문제에 대한 해결책(출력)

컴퓨터 알고리즘

• 계산 문제를 해결하기 위한 잘 정의된 계산 절차 문제

알고리즘의 정확성

• 알고리즘은 모든 입력 인스턴스에 대해 올바른 출력으로 중지되면 올바른 것이라고 함
• 올바른 알고리즘은 주어진 문제를 해결함
• 잘못된 알고리즘은 전혀 중지되지 않거나 원하는 알고리즘이 아닌 다른 대답으로 중지 될 수 있음

---

문제를 어떻게 해결할까?

• 데이터 구조

  • 데이터 구조는 데이터를 저장하고 조직하는 방법
  • 액세스 및 수정을 용이하게 함

• 효율적인 알고리즘

  1. P-problems: 다항 시간 내에 효율적으로 풀 수 있는 문제
  2. NP-complete problems:
     • 효율적인 알고리즘이 존재하는지 여부는 알려져 있지 않음
  • 만약 효율적인 할고리즘이 그들 중 하나에 존재한다면, 효율적인 알고리즘은 그들 모두에 존재함
  • 몇몇 문제는 우리가 효율적인 알고리즘을 알고 있는 문제와 유사함

알고리즘 성능

• 실행시간(시간 복잡도)
• 공간소비(공간 복잡도)

정렬에 대한 두 가지 알고리즘

• 삽입 정렬: n^2
• 병합 정렬: nlgn
  

---

추가 예제(1) - 탐색

• 문제: n개 수로 된 리스트 S 에 x 라는 수가 있는지 알아내시오.
  x가 S 에 있으면 “예”, 없으면 “아니오”로 답하시오.
• 파라미터: S, n, x
• 입력의 예: S = [10,7,11,5,3,8], n = 6, x =5
• 출력의 예: “예”

• 알고리즘 : 순차탐색 알고리즘 v.s. 이진탐색 알고리즘

---

순차탐색 알고리즘

• 최악의 경우 N번 비교

---

이진탐색 알고리즘

• 최악의 경우 log2N+1번 비교

---

순차탐색 vs 이진탐색

순차탐색 시간복잡도 분석

• 단위연산: 배역의 아이템과 키 x와 비교 연산

• 입력크기: 배열 안에 있는 아이템의 수 n

• 최악의 경우 분석

  • x가 배열의 마지막 아이템이거나, x가 배열에 없는 경우
  • 단위연산이 n번 수행
  • 따라서, WorstCaseTime(n) = n

  

• 최선의 경우 분석

  • x가 S[1]일 때, 입력의 크기에 상관없이 단위연산이 1번만 수행됨
  • 따라서, BestCseTime(n) = 1

최악, 평균, 최선의 경우 분석 방법 중에서 어떤 분석이 가장 정확한지, 어떤 분석을 사용할 것인지 생각해볼 것!