Sapphire9 개발 일지

'Do it! 자료구조와 함께 배우는 알고리즘 입문(파이썬)' 책을 기반으로 정리한 내용입니다.

 

배열(array)이란?

  • 배열(array)은 같은 타입의 변수들로 이루어진 유한 집합
  • 파이썬에서는 서로 다른 자료형을 같이 저장할 수 있음
  • 배열을 구성하는 각각의 값을 배열 요소(element)
  • 배열에서의 위치를 가리키는 숫자는 인덱스(index)
  • 배열은 같은 종류의 데이터를 많이 다뤄야 하는 경우에 사용할 수 있는 가장 기본적인 자료구조

 

파이썬에서 배열은 리스트(list)와 튜플(tuple)로 구현할 수 있다.

 

검색 알고리즘

검색과 키

  • 검색 조건에서 주목하는 항목을 키
  • 대부분 키는 데이터의 일부
  • 데이터가 간단한 정숫값이나 문자열이면 데이터값이 그대로 키값이 될 수 있음

 

배열 검색

선형 검색

  • 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘

 

이진 검색

  • 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘

 

해시법

'데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것

  • 원소의 검색뿐 아니라 추가, 삭제도 효율적으로 수행할 수 있음
  • 해시 테이블 : 해시값을 인덱스로 하여 원소를 새로 저장한 배열
  • 해시 함수 : 키를 해시값으로 변환하는 과정
  • 버킷 : 해시 테이블에서 만들어진 원소

 

해시 충돌

저장할 버킷이 중복되는 현상을 충돌(collision)이라고 한다.

 

체인법

  • 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법(열린 해시법)

 

오픈 주소법

  • 충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법(닫힌 해시법)
  • 버킷에 속성(저장, 비어있음, 삭제 완료)을 부여하여 검색 실패 방지

 

복잡도

알고리즘의 성능을 객관적으로 평가하는 기준

  • 시간 복잡도 : 실행하는 데 필요한 시간을 평가
  • 공간 복잡도 : 메모리와 파일 공간이 얼마나 필요한지를 평가

 

O(f(n))과 O(g(n))의 동작을 연속적으로 하는 경우 복잡도는 일반적으로 다음과 같이 나타냄

O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
  • 선형 검색의 시간 복잡도 : O(n)
  • 이진 검색의 시간 복잡도 : O(log n)

 

리스트

데이터에 순서를 매겨 늘어놓은 자료구조

  • 구조가 단순한 리스트로 선형 리스트, 연결 리스트가 있음
  • 스택과 큐도 리스트 자료구조에 속함

 

연결 리스트

  • 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결되어 있음
  • 연결 리스트에서 각각의 원소를 노드
  • 노드는 데이터와 뒤쪽 노드를 참조하는 포인터를 갖고 있음

 

배열로 연결 리스트 만들기

배열의 각 원소에는 순서대로 데이터가 저장되어 있다. 따라서 '뒤쪽 노드 꺼내기'는 인덱스값이 1만큼 큰 원소에 접근하여 얻을 수 있다.

단순한 배열로 구현한 연결 리스트는 다음과 같은 문제가 있음

데이터를 삽입, 삭제함에 따라 데이터를 옮겨야 하므로 효율적이지 않다.

'CS > 자료구조' 카테고리의 다른 글

우선순위 큐  (0) 2023.02.10
profile

Sapphire9 개발 일지

@Sapphire9

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

검색 태그