학습 내용 요약
- 배열과 링크드리스트
- 이진탐색
- 재귀함수
1. 배열과 링크드리스트
1) 배열
(1) 정의
크기가 정해진 데이터의 공간으로, 같은 타입의 데이터들을 순차적으로 저장하는 자료구조
(2) 특징
- 고정된 배열의 크기로 인해 크기 자체는 변경 불가능
- 연속된 메모리 공간에 순차적으로 저장되고, index로 빠른 조회 가능. 즉, O(1) 시간복잡도를 가짐
- 원소 삽입 or 삭제는 저장된 원소들의 연속성을 고려해 다른 원소들을 옮기는 작업이 필요하고, 최악의 경우 O(N)의 시간복잡도를 가짐
- 배열의 크기를 늘리려면, 새 배열 생성 후 기존 배열 데이터 복사해야 하므로 비효율적인 자료구조
2) 링크드리스트
(1) 정의
크기가 정해지지 않은 데이터의 공간으로, 데이터를 순차적으로 저장하는 자료구조
(2) 특징
- 배열과 달리 값이 크기가 정해져 있지 않지만, 빈 원소 허용 X
- 데이터가 연속된 메모리 공간에 저장될 필요 없음. 따라서, index 필요X
- 원소를 노드, 연결고리를 포인터라고 하고, 처음 노드를 head, 마지막 노드를 tail이라 함
- 노드들의 순서를 통해 각 노드들에 접근 가능하기에 순서가 중요함
- 특정 노드에 접근하려면, 포인터를 따라 탐색해야 함. 최악의 경우 모든 노드를 탐색해야 하므로 O(N)의 시간복잡도를 가짐
- 노드 삽입 or 삭제 시, 포인터를 연결하고 끊기만 하면 되기 때문에 O(1)의 시간복잡도를 가짐
head_node = Node(1)
next_node = Node(5)
next_node = head_node.next -> 노드 연결(3) 구성요소
- 노드(Node): 각 원소를 지칭함. 두 가지 정보를 담고 있는데, '각 공간의 데이터'와 '연결된 다음 공간 정보'이다.
- 포인터(Pointer): 노드간의 연결고리
※ 파이썬의 리스트는?
파이썬에서는 기존의 배열과는 다른 '동적 배열'의 개념으로 리스트를 사용한다. 그래서 위에서 본 리스트와 배열과는 조금 다른 특징을 가진다. 이에 대해서는 따로 정리하기로 한다.
2. 이진탐색
1) 정의
주어진 범위에서 특정 값을 추정할 때 반씩 범위를 줄이면서 탐색하는 방식 (ex. 업다운 게임). 연산량이 반씩 나눠지기 때문에 순차탐색보다 시간복잡도 면에서 효율적이다.
2) 사용법
- 1~100 범위 중 57 찾을 때,
- 중간 수 50 시도 -> up이면, 51~100 내에서 76 시도
-> down이면, 51~75 내에서 63 or 64 시도 ... - 이런 식으로 탐색 범위를 반씩 줄여나감
3. 재귀함수
1) 정의
재귀란 어떤 것을 정의할 때 자기 자신을 참조하는 것이다. 이를 적용시키면 재귀함수는 자기 자신을 호출하는 함수라고 부를 수 있다.
2) 사용 이유 및 목적
이 함수를 사용하는 이유는 반복적인 작업의 코드를 간결하고 효율성 있는 코드로 작성할 수 있기 때문이다. 예를 들면, 아래의 코드와 같다.
# 일반 반복문 함수
input = "토마토"
def is_palindrome(string):
n = len(string)
for i in range(n):
if string[i] != string[n-1-i]:
return False
return True
# 재귀함수 사용
def is_palindrome(string):
if len(string) <= 1:
return True
if string[0] != string[-1]:
return False
return is_palindrome(string[1:-1])3) 기억할 것
- 재귀함수 쓸 경우 탈출 조건이 필요함
- 특정 현상이 반복해서 발생한다면 재귀함수로 풀기 시도
어렵거나 완전히 이해 못한 내용
배열과 리스트에 대해 간단히 정리 및 비교해봤지만, 아직 정보가 부족한 부분이 많고, 파이썬의 리스트는 동적 배열이라는 특징이 있다고 하니 배열과 리스트의 특징에 대해 좀 더 찾아볼 필요가 있다.
이진탐색, 재귀함수 이 개념들은 생각보다 간단하지만, 실제로 문제를 풀 때는 어떻게 적용시킬 수 있을지 아직 잘 모르겠다. 알고리즘 문제를 좀 더 연습하자.
참고자료
https://velog.io/@hwi_chance/CS-Data-Structure-part.1-Array-and-List
https://velog.io/@ayoung0073/python-list
스파르타코딩클럽 자료구조,알고리즘 2주차 강의(항해99)
