[이코테] 꼭 필요한 자료구조 기초

탐색

탐색이란 ? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.

프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸.

대표적으로 DFS, BFS가 있음.

 

사전 지식: 스택, 큐, 재귀함수

 

자료구조

데이터를 표현하고 관리하고 처리하기 위한 구조. 다음의 두 핵심 함수로 구성

삽입(Push): 데이터를 삽입

삭제(Pop) : 데이터를 삭제

• 오버플로 : 데이터가 이미 가득찬 상태에서 삽입 시 발생
• 언더플로 : 데이터가 없는 상태에서 삭제 시 발생

스택

박스 쌓기에 비유할 수 있음. (아래 -> 위로 쌓음)

아래에 있는 박스를 치우기 위해선 위에 있는 박스 먼저 내려야 함. = 후입선출

 

큐

대기 줄에 비유할 수 있음. (먼저 온 사람이 먼저 들어감) = 선입선출

 

재귀 함수

자기 자신을 다시 호출하는 함수.

def recursive_function():
	print('재귀 함수를 호출합니다')
    recursive_function()
    
recursive_function()

실행 시 '재귀 함수를 호출합니다'라는 문자열을 무한히 출력. 종료 조건을 반드시 명시해야 함.

재귀함수는 점화식과 매우 닮아있는 형태. 반복문을 이용하는 것과 비교했을 때 더욱 간결한 형태임을 이해할 수 있음.