[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 05 DFS/BFS - 꼭 필요한 자료구조 기초

꼭 필요한 자료구조 기초

 

1 _ 탐색과 자료구조

1. 탐색
   • 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
   • 대표적인 탐색 알고리: DFS/BFS  

 

1. 자료구조
   • 데이터를 표현하고 관리하기 위한 구조
   • 삽입(Push): 데이터를 삽입한다.
   • 삭제(Pop): 데이터를 삭제한다.

 

---

 

2 _ 스택(Stack)

1. 스택(Stack) 개념

   

   • 박스 쌓기로 비유할 수 있다.
   • 선입후출(First In Last Out) 구조 또는 후입선출(Last In First Out) 구조  

 

2. 스택 예제

stack = []


# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력


## 결과
## [5, 2, 3, 1]
## [1, 3, 2, 5]

 

---

 

3 _ 큐(Queue)

1. 큐(Queue) 개념

   

    
   • 대기 줄로 비유할 수 있다. (EX) 놀이공원 입장 줄)
   • 선입선출(Fisrt In First Out) 구조  

 

2. 큐 예제

from collections import deque


# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()


# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()


print(queue)     # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue)    # 나중에 들어온 원소부터 출력


## 결과
## deque([3, 7, 1, 4])
## deque([4, 1, 7, 3])

 

---

 

3 _ 재귀 함수(Recursive Fuction)

1. 재귀 함수(Recursive Fuction) 개념
   • 자기자신을 다시 호출하는 함수  

 

2. 재귀 함수 예제

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

recursive_fuction()

 

3. 재귀 함수 종료 조건
   • 재귀 함수 초반에 등장하는 if문이 종료 조건 역할 수행  

 

4. 재귀 함수 종료 예제

def recursive_fuction(i):

    if i == 100:
        return false

    print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
    recursive_fuction(i + 1)
    print(i, '번째 재귀 함수를 종료합니다.')

recursive_function(1)

 

5. 2가지 방식으로 구현한 팩토리얼 예제

# 반복적으로 구현한 n!

def factorial_iterative(n):
    result = 1

    for i in range(1, n+1):
        result *= i
    return result



# 재귀적으로 구현한 n!

def factorial_recursive(n):
    if n <= 1:
        return 1
   return n * factorial_recursive(n-1)


print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_iterative(5))


## 결과
## 반복적으로 구현: 120
## 재귀적으로 구현: 120

 

---

 

위 내용은 저자 나동빈의 < 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 을 읽고, 공부한 내용입니다.

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬