💬 SOFTWARE 002

019 선형 알고리즘 [$O(N)$]

---

반에서 가장 키 큰 사람은 누구?

• 처음부터 끝까지 일일이 조사하면서 기억도 해야함 😅

• 자료 구조(Data Structure)

  • 계산 과정에서 필요한 정보를 표현하는 방법

  • 많은 알고리즘에서 중요하게 고려해야 할 사항

• 알고리즘과 컴퓨터는 모든 가능한 상황을 처리해야 함 (시작을 안하거나, 어떤 수를 0으로 나누거나 등의 예외적인 상황 처리 必)

• 알고리즘에서 중요한 특성 하나는 얼마나 효율적으로 작동하느냐임

• 효율성 : '알고리즘이 빠른가, 느린가?', '주어진 양의 데이터를 처리하는 데 시간이 얼마나 걸릴 것으로 예상되는가?'와 같은 질문에 대한 답

• 선형 시간(Linear-Time, 선형(Linear))

  • 계산 시간이 데이터의 양에 정비례하거나 선형적으로 비례할 때

  • 일상생활에서 접하는 많은 알고리즘들이 대부분 선형

  • 많은 선형 알고리즘이 동일한 기본 형태를 가짐

    • 초기화 / 차례로 검사 / 간단한 계산 수행 / 작업을 끝냄(출력 등)

---

020 이진 검색 [$O(logN)$]

---

10억개의 전화번호에서 내 이름 찾기!

• 전화번호부에서 이름을 찾는 방법 (정렬 되어 있음)

  • 중간을 펼치고 앞쪽/뒤쪽인지 파악한 후, 계속해서 그 때의 중간을 펼쳐봄

• 이진 검색(Binary Search)

  • 각 확인 또는 비교 단계를 거치면서 항목들이 두 그룹으로 나뉘고, 그중 한쪽 그룹은 다음 고려 대상에서 제외될 수 있음

  • 분할 정복(Divide and Conquer)이라는 일반적인 전략의 한가지 예

  • 수행해야 하는 일의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가함

  • 스포츠 경기에 자주 사용되는 단계별 토너먼트가 이에 해당

---