알고리즘 - 연결리스트(Linked List)

연결 리스트란

연결 리스트는 데이터를 연속된 메모리 공간에 저장하지 않고 각 데이터가 다음 데이터의 위치를 가리키는 형태로 구성된 선형 자료 구조이다.

  • 각 데이터 단위: 노드
  • 시간 복잡도
    • 데이터 추가와 삭제: 상황에 따라 다름
      • 맨 앞 삽입: O(1)
      • tail을 알 경우에 맨 뒤 삽입: O(1)
      • tail을 알 수 없는 경우에 맨 뒤 삽입: O(N)
    • 특정 위치의 데이터 검색: O(n)
  • 각 노드가 데이터와 포인터를 가지고 데이터를 저장한다

더보기

알고리즘 - 재귀함수(recursive functions)

재귀 알고리즘이란

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 알고리즘

  • 재귀 호출에는 항상 종료 조건이 필요하다
  • 시간복잡도: O(n^2)
  • 재귀 함수의 단점: 메모리 사용량이 증가하고, 재귀 호출이 지나치게 많이 일어날 경우 스택 오버플로우가 발생할 수 있음, 하지만 효율적인 측면에서 재귀함수를 썼을때 더 좋은 경우가 있기 때문에 적절히 사용해줘야 함

더보기

알고리즘 - 이진탐색 (Binary Search)

이진탐색이란

데이터가 오름차순으로 정렬되어 있는 배열 에서 특정한 값을 찾아내는 알고리즘

  • 크기순으로 정렬되어 있는 성질을 이용
  • 탐색할 범위가 너무 많은 경우 (천만건 이상의 데이터 탐색해야 하는 경우)
  • 시간 복잡도: O(log n)

더보기

Pagination