코드잇 알고리즘의 정석

---

알고리즘이란?

• 문제를 해결하기 위한 자세한 방법

좋은 알고리즘이란?

• 단 두가지
  1. 문제해결이 가능한 방법인가?
  2. 더 효율적으로 해결이 가능한 방법인가?

컴퓨터 알고리즘이란?

• 임의의 명령을 컴퓨터가 이해하고 실행할 수 있도록 적혀있는 방법

알고리즘 그게 뭐가 중요해?

• 서비스 사용자들이 원하는 가장 중요한 단 두가지
  • 서비스 사용자들이 원하는 단 두가지 핵심은 틀리지 않은 정확한 정보를 알려주는 서비스와 기다림이 더 적은 신속한 서비스 속도 이 두가지는 좋은 알고리즘의 특성이며 고객 유치와 유입에 큰 영향을 줄 것으로 생각된다. 이것이 개발자의 알고리즘 역량이 중요한 이유다.
• 유능한 개발자들은 알고리즘적 사고력이 높기 때문
  • 더 좋은 알고리즘의 풀이로 제한된 컴퓨터 자원에서 속도가 더 빠르고 더 정확한 정보를 주는 것이 가능하기 때문

효율적인 알고리즘적 사고력 기르는 법?

• 핵심은 포기하지 않을 정도의 인내를 바탕으로 가지는 깊은 고민
  • 이유
    • 고민한 시간이 엄청난 자산이 된다.
• 구체적으로 어떻게?
  • 내장 함수를 최대한 이용하지 않고 조건문과 반복문만으로 작성하기
    • 이유
      • 알고리즘 자체의 상상기회 줄어듬
  • 갈피가 잡힐 정도의 힌트나 다른 사람들의 풀이를 보고 끈기를 가지고 풀어보고 못풀었으면 풀릴때까지 다시 힌트와 풀이를 반복
• 가능하면 게임이라고 생각하고 즐기자

탐색알고리즘이란?

• 특정한 값을 찾는 알고리즘이며 선형탐색(linear search algorithm) 과 (binary search algorithm)이 있다.

이진탐색(binary search algorithm)

• 사용 조건
  • 정렬이 되어 있어야 사용가능
• 구현해보기

  def binary_search(element, some_list):
      # 코드를 작성하세요.
      front = 0
      back = len(some_list) - 1
      while front <= back:📌
          middle = (front + back) // 2
          if some_list[middle] == element:
              return middle
          elif element < some_list[middle]:
              back = middle - 1📌
          elif some_list[middle] < element:
              front = middle + 1📌
      return None
      
      
  
  print(binary_search(2, [2, 3, 5, 7, 11]))
  print(binary_search(0, [2, 3, 5, 7, 11]))
  print(binary_search(5, [2, 3, 5, 7, 11]))
  print(binary_search(3, [2, 3, 5, 7, 11]))
  print(binary_search(11, [2, 3, 5, 7, 11]))

  • 📌📌📌막혔던 부분
    • 미들인덱스의 값이 element와 일치 하지 않을 경우 middle값 에서 +1과 -1을 사용해서 범위조정를 조정을 해 주어야 하는데 middle 값으로 대체를 해버려서 풀이가 꼬여 버렸다.

이진탐색이 더 빠른데 선형 탐색이 왜 필요 할까?

• 정렬이 되어 있지 않은 경우 이진탐색은 사용이 불가하기 때문

각 상황에 따른 정렬 알고리즘 속도 비교 사이트

알고리즘 평가 척도 기준은?

• 시간복잡도와 공간 복잡도

알고리즘 작성시 시간과 공간중 어떤게 더 중요한가?

• 시간 복잡도
• 왜?
  • 공간 복잡도는 메모리 공간으로 한계치가 유한하지만 시간 복잡도는 가지각색의 알고리즘에 따라 프로그램의 실행속도에 영향을 주기 때문
  • 공간복잡도는 개인의 컴퓨터 성능에 따라 한계치가 있지만 시간 복잡도는 어느 컴퓨터에서나 영향을 주기 때문이지 않을까?

점근 표기법(Big-O notation)이란?

• 점근표기법의 핵심
  • 절대적인 시간이 아닌 가장 큰 성장성
• 데이터의 양이 무한에 가까워 질수록 시간 복잡도에 가장 큰 영향을 주는 미지수의 부분을 앞에 있는 숫자를 제외하고 표기한것
• 예시
  • O(n), O(n^2), O(log n) 등등이 있다.
• 점근표기법 원리
  • f(x) = O(g(x)), x ->∞

List Operation 중에 시간 복잡도 이해가 되지 않은 것

Operation	Code	Average Case
중간에 요소 추가	my_list.insert(index, element)	O(n)
삭제	del my_list[index]	O(n)