자료구조

이것이 코딩테스트다 with 파이썬 정리

📌 정의

• 탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

• 자료 구조: 데이터를 표현하고 관리하고 처리하기 위한 구조

  		- 삽입(Push): 데이터를 삽입한다.
    		- 삭제(pop): 데이터를 삭제한다.
          - 오버플로: 자료구조가 수용할 수 있는 데이터의 크기를 이미 찬 상태에서
          		   삽입연산을 진행했을때 발생.
          - 언더플로: 자료구조에 자료가 전혀 없음에도 삭제 연산을 수행했을때 발생
          

• 스택: 선입후출 구조, 후입 선출 구조

• 큐: 선입선출 구조

  from collections import deque
  
  queue = deque()
  
  queue.append(5)
  queue.append(2)
  queue.append(3)
  queue.popleft()
  
  print(queue) # deque([2, 3])
  queue.reverse()
  print(queue) # deque([3, 2])
  

• 재귀함수: 자기 자신을 다시 호출하는 함수

  def function():
  	print("재귀함수를 호출합니다.")
    	function()
        
   function()
   # "재귀함수를 호출합니다" 문자열 무한 호출.
   
   
   #팩토리얼 예제
   
   def factorial(n):
   	if n <= 1:
    		return 1
      return n * factorial(n-1)

• DFS: 깊이 우선 탐색이라고도 불리며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 재귀함수로 구현

  	* 그래프 == 노드(정점이라고도 부르며 도시) + 간선( 도로 )
  	
  	* 그래프의 표현 방법
  	
  			- 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식
  			- 인접 리스트: 리스트로 그래프의 연결관계를 표현하는 방식
            
    	* DFS의 구체적인 동작 과정
        		
                1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
                2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 
                	 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접
                   노드가 없으면 스택에서 최상단 노드를 꺼낸다.
                3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
                

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)
# 1 2 7 6 8 3 4 5

• BFS: 너비 우선 탐색 이라는 의미를 가지며, 가까운 노드부터 탐색하는 알고리즘이다.

  		- 선입 선출 방식을 이용하는 것이 정석
   
   		동작 방식
        
        	1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
          2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를
             모두 큐에 삽입하고 방문 처리를 한다.
          3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
          
          

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)