데이터 취업 스쿨 스터디 노트 - 자료구조 문제풀이, 알고리즘 (6주차)

[6주차 Study Note]

• 선형검색

  • 앞에서부터 순차적으로 검색 (성공 or 실패)

• 보초법

  • 마지막 인덱스 뒤에 찾으려는 값을 추가해서 찾는 과정을 간략화함
    (마지막 전에 찾으면 검색 성공 / 마지막에 찾으면 검색 실패)

• 이진검색
  (1) 먼저 자료를 정렬
  (2) 중앙값과의 크고 작음을 이용해 데이터를 검색
  (반을 자르고 또 그 반을 자르는 형태)

• 순위(rank)

  • 수의 크고 작음을 이용해 순서를 정함
    (기준 수와 타 수들을 비교하면서 타 수들이 작을 때 해당 숫자 인덱스 + 1 / 작으면 인덱스 그대로)
  • 가장 큰 수 = 인덱스 0 / 가장 작은 수 = 인덱스 맨 끝

• 버블정렬

  • 처음~끝까지 인접하는 인덱스 값을 순차적으로 비교한 뒤
    → 큰 숫자를 가장 끝으로 옮김 (쭉쭉 큰값을 오른쪽으로 밀어감)

• 삽입정렬

  • 정렬된 자료 배열과 비교하여 정렬 위치를 찾음
    (정렬되지 않은 숫자의 위치를 찾아 그 위치로 바꾼뒤 정렬)

• 선택정렬
  (1) 리스트 상에서 최소값을 찾음
  (2) 찾은 최소값을 맨 앞의 값과 교체

• 최빈값 (빈도수가 가장 높은 값)
  (1) 리스트 상 최대값을 확인후 0~최대값 인덱스까지 해당하는 인덱스 리스트를 만듦
  (2) 숫자에 맞는 인덱스 자리에 가서 한개당 +1씩 추가
  (3) 인덱스가 가장 큰 값의 자리 확인 후 기존 리스트의 최빈값으로 반환

• 근삿값 (특정 참값에 가장 가까운 절대값)

  • 하나하나 차이가 얼마나 나는지 찾고 가장 작은 차이를 가진 값을 찾음

• 재귀 알고리즘

  • 나 자신을 다시 호출