Tarel_base

깊이우선탐색 - DFS

요약

그래프의 완전 탐색 기법 중 하나이며 시작노드에서 출발 -> 탐색할 분기를 정해서 최대 깊이까지 탐색을 마친 후, 다른 쪽 분기로 넘어가 다시 탐색하는 알고리즘으로 재귀함수로 구현한다.

분석

DFS는 한 번 방문한 노드를 재방문해선 안 되기 때문에 방문 여부를 따로 체크할 리스트가 필요하다.

DFS 탐색방식은 후입 선출 특성을 가지므로 스택을 사용한다.

1. 방향 없는 그래프

방향없는 그래프에서 연결요소를 구해보자

예시

아래는 입출력의 예시다.

입력 예시
=================
6 5
1 2
2 5
5 1
3 4
4 6

이 숫자의 나열은 첫 번째 줄은 노드의 숫자와 엣지의 개수를 말하며

그 아래로는 어느 노드와 어느 노드가 연결되어 있는지를 나타낸다.

즉, 노드는 총 6개, 노드간의 연결은 총 5개이며

1번과 2번이 연결, 2번과 5번이 연결, 5번과 1번이 연결......이라고 할 수 있으며

이를 그림으로 표현하면 아래와 같다.

이 그래프는 보시다시피 두 개가 서로 분리되어 있다.

고로 출력 결과는 아래와 같다.

출력 예시
============
2

이번엔 다른 입력 예시를 만들어보자

입력 예시
==============
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

노드는 6개 연결은 총 8개며 그림으로 표현하면 다음과 같다.

보시다시피 따로 분리되어 있지 않다 고로 출력결과는 1이 나온다.

출력 예시
================
1

코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

n, m = map(int, input().split())
A = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)

def DFS(v):
    visited[v] = True
    for i in A[v]:
    	if not visited[i]:
        	DFS(i)
            
for _ in range(m):
    s, e = map(int, input().split())
    A[s].append(e)
    A[e].append(s)
    
count = 0

for i in range(1, n + 1):
    if not visited[i]:
        count += 1
        DFS(i)
        
print(count)

우선 노드와 엣지수를 입력을 받으면

A리스트를 생성하는데, 이 리스트는 각 노드가 어디와 연결되어 있는지를 나타내는 리스트다

예를 들어, 이 사진어서, 1번 노드는 2번과 5번과 연결되어 있으므로 A[1] 의 값은 [2, 5]가 된다.

visited는 각 노드별로 방문을 했는지 안했는지를 나타내는 리스트로 일단은 전부 False로 입력된다.

첫 번째 for문에서, 각 이을 노드 번호를 s와 e로 입력 받고

이것을 A리스트에 추가한다.

이것을 엣지 수만큼 반복하면 각 노드가 어느 노드와 연결되어 있는지 나타내는 리스트 A가 완성된다.

위 예시 기준, A값은 다음과 같이 나온다.

A[[], [2, 5], [1, 5, 4, 3], [4, 2], [3, 6, 5, 2], [2, 1, 4], [4]]

두 번째 for문에서 DFS 함수를 실행한다.

DFS 함수를 실행했다는건 해당노드를 방문했다는 뜻이므로 해당 visited의 값은 True가 된다.

이 for문은 1부터 시작한다. 즉 DFS 함수의 파라미터에 1을 넣고

안의 for문에서 visited의 값을 체크한다.

이걸 계속 돌면서, visited 값을 True로 바꿔나가다보면 연결된 모든 노드들이 방문하면서, visited 변수의 값이 True로 바뀐다.

이걸 몇 번했느냐가 곧 count 변수의 값이다.

예시에선 2 번째 for문에서 DFS를 한 번 호출 했으므로 count값은 1이 된다.

그리고 이 count 값이 연결 요소의 개수이다.

1. 재귀 호출

자신이 자신을 다시 호출하는 것을 재귀호출이라고 한다.

간단한 재귀호출을 코드로 작성해보면 다음과 같이 나온다.

def openBox():
    print('종이상자를 엽니다. ')
    openBox() # 자신을 다시 호출
openBox()

# 실행결과
'''
종이상자를 엽니다. 
종이상자를 엽니다.  
종이상자를 엽니다. 
종이상자를 엽니다. 
종이상자를 엽니다. 
종이상자를 엽니다. 
.........
'''

쉽게말해 자기 함수 안에 자기 자신을 호출하는 코드를 입력함으로써 재귀호출이 완성된다.

그런데 이렇게 무한히 반복되면 당연히 문제가 발생되기 때문에 보통은 아래처럼 반복 조건에 제한을 둔다.

count = 5

def openBox():
    global count
    print('종이상자를 엽니다. ')
    count -= 1
    if count == 0:
        print('상자에 반지를 넣는다.')
        return
    openBox() # 자신을 다시 호출
    print('종이상자를 닫습니다.')
    
openBox()

# 실행결과
'''
종이상자를 엽니다. 
종이상자를 엽니다. 
종이상자를 엽니다. 
종이상자를 엽니다. 
종이상자를 엽니다. 
상자에 반지를 넣는다.
종이상자를 닫습니다.
종이상자를 닫습니다.
종이상자를 닫습니다.
종이상자를 닫습니다.
'''

이는 마치 러시아의 인형마냥 상자를 열면 또 상자가 나오고 다시 열면 또 나오는 식으로 반복되다가

반복 조건이 끝나면 조건을 수행하고 다시 닫고 또 닫는 형태로 반복된다.

자세히보면 여는건 5번 하는 반면 닫는건 4번밖에 안하는데

이는 '상자에 반지를 넣는다.'를 출력할 때 바로 리턴해버려서 '종이상자를 닫습니다' 구문을 패스해버리기 때문이다.

2. 사용

구현하는 개념 자체는 생각보다 간단하다.

이제 이걸 사용해보자

2-1. 팩토리얼

재귀함수하면 가장 먼저 생각나는 수학으로 재귀함수를 사용하면 짧고 간단하게 구현할 수 있다.

def factorial(num):
    if num <= 1:
        return 1
    else:
        return num * factorial(num -1)

print('10! =', factorial(10))

# 실행결과
# 10! = 3628800

factorial 함수의 파라미터에 숫자로 몇을 넣어주냐에 따라 몇 팩토리얼이 출력될 지가 결정된다.

2-2. 구구단

def gugudan(dan, num):
    print(f'{dan} X {num} = {dan * num: 2d}', end = ' ')
    if num < 9:
        gugudan(dan, num + 1)

for dan in range(2,10):
    print(f'{dan}단 시작! ------')
    gugudan(dan, 1)

출력시, 2단부터 9단까지 출력된다.

함수는 단번호와 최대 수를 받아 한 단을 출력하고

for문을 통해서, 2단부터 9단까지 출력한다.

2-3. N제곱

tab = ''
def pow(x, n):
    global tab
    tab += ' '
    if n == 0:
        return 1
    print(tab, f'{x} X {x}^{n} - {1}')
    return x * pow(x, n-1)

print('2^10')
print('답 -->', pow(2,10))

# 실행결과
# 2^10
#   2 X 2^10
#    2 X 2^9
#     2 X 2^8
#      2 X 2^7
#       2 X 2^6
#        2 X 2^5
#         2 X 2^4
#          2 X 2^3
#           2 X 2^2
#            2 X 2^1
# 답 --> 1024

pow 함수에 x에 N제곱 대상을, n에 몇제곱인지를 넣는다.

위 코드에선 pow함수에 2와 10을 넣었으므로 2의 10제곱, 즉 1024가 출력된다.

2-4. 피보나치 수열

피보나치 수열은 앞의 두 수를 더한 값을 다음 값으로 하는 수열이다.

0과 1로 시작을 하며 0과 1을 더한값은 1이므로 3번째 값은1, 1과 1을 더한 값은 2이므로 4번째 값은 2....

이런식이다.

이걸 구현해보자

def fibonaci(n):
    if n == 0: return 0
    elif n == 1: return 1
    else:
        return fibonaci(n-1) + fibonaci(n-2)

print('피보나치 수 --> 0 1', end = ' ')
for i in range(2, 11):
    print(fibonaci(i), end = ' ')
    
# 실행결과
# 피보나치 수 --> 0 1 1 2 3 5 8 13 21 34 55

피보나치 함수에 입력받은 값을 넣어서 실행한다.

여기서 for문의 범위값을 통해서, 얼마나 출력할지를 정해줄 수 있다.

1차원 구간합과 2차원 구간합에 대한 정리

1. 구간합 1차원

요약

배열(리스트)에서 일정 구간에 있는 값을 더하는 것으로

합배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

분석

구간합은 마치 주어진 리스트에서 어디서부터 어디까지 전부 더하기만 하면 되는 간단한 알고리즘 처럼 보인다.

그러나 매번 합을 계산한다면 계산해야할 대상이 많아질 수록 시간을 많이 소비하게 된다.

예를 들어, 반복문을 사용해서 a 부터 b 까지의 값을 모두 더할 경우, a 부터 b 까지의 거리가 멀 수록 소요시간이 너무 길어진다.

그러나 구간 합 알고리즘을 사용할 경우 그 시간이 크게 감소한다.

구간 합 알고리즘은 먼저 어디서부터 어디까지 더해 준 값을 for문을 사용해서 미리 만든다

물론 이 과정에서, 더해야할 숫자가 많다면 시간이 오래 걸릴 것이다.

그러나 이렇게 만들어진 '구간합 배열'은 

예시

아래 예시는 구간합 알고리즘으로써

배열의 길이, 구간합을 수행할 횟수, 배열안의 요소와 구간을 입력하여 동작한다.

입력 예시
======================
5 3
5 4 3 2 1
1 3
2 4
5 5

배열의 길이는 5며 구간합은 3번 수행한다.

배열안의 요소는 [5, 4, 3, 2, 1]이며

1번 값부터 3번까지의 값을 더하고

2번 값부터 4번까지의 값을 더하고

5번 값부터 5번까지의 값을 더한다는 의미이다.

그렇다면 출력은 다음과 같이 나올 것이다.

출력 예시
======================
12
9
1

코드

import sys
input = sys.stdin.readline
suNo, quizNo = map(int, input().split())
numbers = map(int, input().split())

prefix_sum = [0]
temp = 0

for i in numbers:
    temp = temp + i
    prefix_sum.append(temp)
    
for i in range(quizNo):
    s, e = map(int, input().split())
    print(prefix_sum[e] - prefix_sum[s-1])

코드에서, suNo와 quizNo는 각각 배열의 길이와 구간합을 실시할 횟수를 입력하는 것을 말한다.

numbers는 입력받은 배열을 말하며 입출력 예시의 [5, 4, 3, 2, 1]에 해당하는 배열이다.

첫 번째 for문에서, prefix_sum에는 0번 인덱스에 0에서부터 시작해 각각의 더한 값이 들어간다.

예를들어 numbers가 [5, 4, 3, 2, 1]이라면

첫번째 for문에서, prefix_sum의 값은 [0, 5, 9, 12, 14, 15]가 된다.

그리고 찾고자 하는 범위를 입력 받으면, 서로의 범위에 해당하는 값을 빼주면 된다.

예를 들어, [5, 4, 3, 2, 1]에서 3번째 값인  3과 5번째 값인 1 까지의 구간합을 구한다면

prefix_sum의 값에서 5번째 값인 15에서 3-1번째 값인 9를 빼주면 된다.

이 코드의 핵심은 비록 prefix_sum 배열을 만드는데 시간이 걸리겠지만

한 번 완성되면, 그 이후로는 어떤 구간합을 해도 시간이 거의 걸리지 않는다는 장점이다.

2. 구간합 2차원

위에서 1차원 구간합을 구했다면 이번엔 2차원 구간합이다.

요약

위의 행렬에서, (2,2)의 값은 3이고 바로 옆인 (2,3)의 값은 4다.

만약 (2,2)에서 (3,4)까지 합을 구한다면 3 + 4 + 5 + 6 = 27이다.

(2,2) 에서 (3,4)까지 표시한 모습

분석

2차원 배열 또한 먼저 합배열을 만들고 질의를 수행하는 형태로 실행된다.

그저 맨 앞의 요소부터 순차적으로 넣은 값을 배열로 만들었던 1차원 배열 구간합처럼

이번에도 비슷하게 계산하지만 차원이 하나 늘면서 계산식이 복잡해진다.

기존 배열을 A, 합배열을 B 라고 한다면

B[ i ][ j ] 의 값을 구하는 공식은 B[ i ][ j - 1] + B[ i - 1 ][ j] - B[ i - 1 ][ j - 1] + A[ i ][ j ] 이렇게 된다.

참고로 B [ i , 0 ] 의 값은 i, B [ 0 , j ] 의 값은 j다.

이 계산식으로 위에서 제시한 예시를 A, A를 기반으로 만드는 합배열을 B라고 한다면 아래와 같다.

계산 과정은 아래와 같다.

선술한 계산식에 따라 계사능 하며

B[2][2]의 값을 구하는 계산식은 B[2][1] + B[1][2] - B[1][1] + A[2][2] = 3 + 3 - 1 + 3 = 8 이다

즉 (1, 1)은 1+1+0-1 = 1, 그 옆은 1 + 2 - 1 + 1  = 3, 그 옆은 3 + 3 - 2 + 2 = 6.... 이런식으로 더해 간다.

마지막 행인 (4, 4)는 42 + 42 - 27 + 7 = 64 가 된다.

자, 그렇다면 구간 합은 어떻게 계산될까?

요약에서 다루었듯 (2,2)에서 (3, 4)까지 더한 다면

3 + 4 + 5 + 4 + 5 + 6 = 27이 된다.

그렇다면 합 배열에선 이를 어떻게 계산할까?

공식은 아래와 같다.

 B[x2][y2] - B[x1-1][y2] - B[x2][y1-1] + B[x1-1][y1-1]

여기서 x1, y1은 (2,2) x2, y2가 (3,4)가 된다.

즉(2,2)에서 (3,4)의 값을 구한다면

42 - 10 - 6 + 1 = 27이 된다.

예시

입력예시
====================
4 1			배열크기는 4 * 4, 구간합 횟수는 1번
1 2 3 4			1번째 행의 값은 1 2 3 4
2 3 4 5			2번째 행의 값은 2 3 4 5
3 4 5 6			3번째 행의 값은 3 4 5 6
4 5 6 7			4번째 행의 값은 4 5 6 7
2 2 3 4			구간합의 범위는 (2, 2) 부터 (3, 4)까지

위 코드는 우선 2차원 배열의 크기가 4임을 나타내고 질의는 한 번 한다는 뜻이다.

이후 마지막 줄을 제외한 부분은 배열의 요소로써 요소의 내용은 위에 언급한 예시와 같다.

마지막 줄은 어디서부터 어디까지 더할 것인가를 나타낸다.

2 2 3 4를 입력했으므로 (2, 2)부터 (3, 4)까지 더한다는 것을 나타낸다.

아래는 위 입력 예시대로 입력했을 때 나오는 출력이다.

출력예시
===============
27

코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = [[0] * ( n + 1 )]
D = [[0] * ( n + 1 ) for _ in range(n + 1)]

for i in range(n):
    A_row = [0] + [int(x) for x in input().split()]
    A.append(A_row)

for i in range(1, n + 1):
    for j in range(1, n + 1):
    	D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
        
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
    print(result)

우선 배열의 크기와 구간합 계산을 할 횟수를 입력받는다.

첫 번째 for문에서, 배열의 요소 값을 순차적으로 받는다.

두 번째 for문에서, 구간합 2차원 배열을 만든다.

3 번째 for문에서, 구간합을 할 위치를 입력받는다.

입력을 받으면 바로 print문을 통해 더한 값을 입력 받는다.

결론

구간합 알고리즘은 구간합이 필요할 때마다, 또는 구간의 크기가 너무 클 수록, for문을 돌려서 매번, 또는 일일이 값을 더하는 것이 시간을 크게 잡아먹으니

우선 합배열을 만들고 그 합배열을 바탕으로 구간합을 빠르고 쉽게 구할 수 있게 하는 알고리즘이라 할 수 있다.

1. 트리

트리는 그림으로 보는 것이 이해가 빠르다.

보시다시피 가장 위에서 시작해 마치 뒤집어놓은 나무처럼 뻗어나는 것이 트리 구조다.

가장 위를 루트, 특정 노드의 기준으로 자신과 연결된 위쪽 노드를 부모노드, 아래를 자식노드라고 한다.

아래로 내려갈 수록 레벨이 0에서 시작해 1씩 증가한다.

가장 끝에 위치하여 자식이 없는 노드를 리프노드라고 한다.

2. 이진트리

이진 트리란 자식이 2개 이하만 존재하는 트리를 이진트리라 한다.

이 중 리프를 제외한 모든 노드가 자식이 2개씩 존재할 경우, 포화 이진트리라고 한다.

노드의 번호는 최상단이 1로 시작해 왼쪽부터 순차적으로, 위 사진의 오른쪽 처럼 번호를 부여한다.

일반 이진트리는 위 사진의 6번 처럼 빈 공간이 있을 수도 있다.

3. 트리의 순회

트리내의 정보를 찾을 때는 트리를 순회해야 한다.

트리의 정보를 순회할 때는 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 방법이 있다.

위와 같은 트리가 있다고 가정해보자

전위 순회(preorder)를 하면 루트인 화사부터 시작해 루트기준으로 왼쪽부터 다 훑어보는 방법이다.

순서는 아래와 같다.

화사 -> 솔라 -> 휘인 -> 쯔위 -> 문별 -> 선미

중위 순회(inorder)는 트리를 기준으로 왼쪽부터 시작해서 오른쪽으로 차근차근 순회하는 방법이다.

순서는 아래와 같다.

휘인 -> 솔라 -> 쯔위 -> 화사 -> 선미 -> 문별

후위 순회(postorder)은 왼쪽 자식 끝부분부터 시작해 같은 래밸의 같은 부모를 둔 노드를 순회한 다음 그 부모를 순회하는 방법이다.

순서는 아래와 같다.

휘인 -> 쯔위 -> 솔라 -> 선미 -> 문별 -> 화사

4. 이진탐색

이진탐색은 이진 트리에서 가장 활용도가 높은 것으로 데이터 크기를 기준으로 일정 형태로 구성한다.

이진 탐색은 탐색 시간을 크게 줄일 수 있는 장점이 있다.

예를 들어, 10억개의 데이터가 있고 여기서 하나의 데이터를 찾는다고 가정해보자

그럼 일단 5억번째 데이터를 확인하고 찾고자 하는 데이터와 크기를 비교한다.

5억번째 데이터보다 크기가 작다면 2억5천만번째 데이터를 확인한다.

역시 작다면 1억 2천5백만번째 데이터를 확인한다.

역시 작다면 6천2백5십만번째 데이터를 확인한다.

역시 작다면 3천125만번째 데이터를 확인한다.

이런식으로 계속 반으로 줄여나간다.

때문에 이진 탐색방법을 사용하면 10억개의 데이터 기준 약 30번의 탐색만으로도 찾아낼 수 있다.

참고로 1000경의 데이터가 있을 경우 약 63번의 탐색만으로도 찾아낼 수 있다.

5. 구현

5-1. 트리

위에 예시로 나온 이진트리를 구현해보자

class TreeNode: # 트리노드
    def __init__(self) -> None:
        self.left = None
        self.data = None
        self.right = None

우선 클래스를 만들어준다.

이 클래스는 노드 클래스로, 데이터, 왼쪽, 오른쪽의 데이터를 가진다.

node1 = TreeNode()
node1.data = '화사'

node2 = TreeNode()
node2.data = '솔라'
node1.left = node2

node3 = TreeNode()
node3.data = '문별'
node1.right = node3

node4 = TreeNode()
node4.data = '휘인'
node2.left = node4

node5 = TreeNode()
node5.data = '쯔위'
node2.right = node5

node6 = TreeNode()
node6.data = '선미'
node3.left = node6

이제 각 노드를 정의해주자

node1이 루트이며 그 밑으로는 각각의 노드가 어디의 노드인지를 나타낸다.

print('         ',node1.data)
print('    ┌──────┴──────┐    ')
print('  ',node1.left.data, '        ', node1.right.data)
print('┌───┴───┐     ┌───┴───┐')
print(node1.left.left.data, '', node1.left.right.data, ' ',
      node1.right.left.data, '')

자료구조가 완성되었다면 보기좋게 출력해보자

출력결과는 아래와 같다.

(주석처리하면 모양이 기울어져서 따로 작성)

          화사
    ┌──────┴──────┐    
   솔라          문별
┌───┴───┐     ┌───┴───┐
휘인  쯔위   선미

5-2. 트리 순회

선술한 전위순회, 중위순회, 후위순회를 해보자

트리는 바로 위에서 구현한 것을 사용한다.

def preorder(node):
    if node == None: return    
    print(node.data, end = ' -> ')
    preorder(node.left)
    preorder(node.right)
preorder(node1)

# 실행결과
# 화사 -> 솔라 -> 휘인 -> 쯔위 -> 문별 -> 선미 ->

재귀호출을 사용하면 쉽게 구현할 수 있다.

나머지 중위순회나 후위순회는 위 코드의 순서를 바꿔주는 형태로 구현해 줄 수 있다.

def inorder(node):
    if node == None: return
    inorder(node.left)     # 재귀호출(Recursive Call)
    print(node.data, end = ' -> ')
    inorder(node.right)     # 재귀호출(Recursive Call)
inorder(node1)

# 실행결과
# 휘인 -> 솔라 -> 쯔위 -> 화사 -> 선미 -> 문별 ->

중위 순회 코드

def postorder(node):
    if node == None: return
    postorder(node.left)
    postorder(node.right)
    print(node.data, end =' -> ')
postorder(node1)

# 실행 결과
# 휘인 -> 쯔위 -> 솔라 -> 선미 -> 문별 -> 화사 ->

후위순회 코드다.

5-3. 이진탐색

이번엔 새로운 트리를 만들고 이진탐색을 구현해보자

트리는 이렇게 구성한다.

루트에서 시작하여 주어진 값을 비교하여 왼쪽으로 갈지, 오른쪽으로 갈지를 정한다.

이 과정을 계속 반복하여, 원하는 값을 찾아나간다.

if __name__ == '__main__':
    search = input('찾을 걸그룹을 입력 > ')

    current = root
    while True:
        if search == current.data:
            print(search, '찾음 끝!')
            break
        elif search < current.data: # 왼쪽 노드로
            if current.left == None:
                print(search, '못찹음 끝!')
                break
            else:
                current = current.left
        else: # 오른쪽 노드로
            if current.right == None:
                print(search, '못찹음 끝!')
                break
            else:
                current = current.right

트리구현을 포함한 전체코드는 아래와 같다.

# 이진 탐색 트리
# 전역변수 선언
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스']

class TreeNode:
    def __init__(self) -> None:
        self.left = None
        self.data = None
        self.right = None

if __name__ == '__main__':
    node = TreeNode()
    node.data = nameAry[0] # 블랙핑크
    root = node
    memory.append(node)

    for name in nameAry[1:]:
        node = TreeNode()
        node.data = name
        
        current = root
        
        while True:
            if name < current.data: # 부모노드 왼쪽으로
                if current.left == None:
                    current.left = node
                    break
                current = current.left
            else: # 부모노드 오른쪽
                if current.right == None:
                    current.right = node
                    break
                current = current.right

        memory.append(current)
    print('이진 탐색 트리 구성 완료')
    print('               ',root.data)
    print('         ┌──────────┴──────────┐    ')
    print('    ',root.left.data, '            ', root.right.data)
    print('   ┌─────┴─────┐         ┌─────┴─────┐')
    print(root.left.left.data, '  ', root.left.right.data, ' ',
        root.right.right.data, '')
    
    #print(root.left.left.left.data)

    search = input('찾을 걸그룹을 입력 > ')

    current = root
    while True:
        if search == current.data:
            print(search, '찾음 끝!')
            break
        elif search < current.data: # 왼쪽 노드로
            if current.left == None:
                print(search, '못찹음 끝!')
                break
            else:
                current = current.left
        else: # 오른쪽 노드로
            if current.right == None:
                print(search, '못찹음 끝!')
                break
            else:
                current = current.right

1. 큐

스택이 데이터의 출입구가 하나라면 큐는 출구와 입구가 따로 있는 자료구조라고 생각할 수 있다.

선입선출 (First In First Out; FIFO)의 자료구조로 Queue라고도 한다.

여기서

데이터를 삽입하는 것을 enQueue

데이터를 추출하는 것을 deQueue

데이터의 첫 번째 부분(출구 앞)을 front

데이터의 마지막 부분(입구 앞)을 rear

라고 한다.

1-1 구현

큐를 구현해 보자

큐는 보통 배열을 통해서 구현하는데 이러면 Enqueue와 Dequeue를 할 때마다 계속 데이터가 앞으로 밀려나는

문제가 생기는 점을 잘 고려해야 한다.

SIZE = 0
queue = []
front = rear = -1

먼저, 전역변수를 만든다.

큐에는 큐가 가득 찬 경우, 완전히 빈 경우, 데이터를 넣는 경우, 데이터를 빼는 경우가 있을 수 있다.

이것들을 전부 함수로 만들어주자

# Queue Full 체크
def isQueueFull():
    global SIZE, queue, front, rear
    if(rear != SIZE -1):
        return False
    elif(rear == SIZE -1)and (front == -1):
        return True
    else:
    	# deQueue를 하고나서 빈자리를 채운다.
        for i in range(front + 1 , SIZE):
            queue[i - 1] = queue[i]
            queue[i] = None
        front -= 1
        rear -= 1 # 1씩 감소시킨다.
        return False

큐가 가득 찼을 때를 위한 코드

# Queue Empty 체크
def isQueueEmpty():
    global SIZE, queue, front, rear
    if(front == rear):
        return True
    else:
        return False

큐가 완전히 비었을 때를 위한 코드

front와 rear의 값이 같다면 빈 것으로 판정한다.

def enQueue(data): # Queue 데이터 추가
    global SIZE, queue, front, rear
    if isQueueFull():
        print('=======================')
        print('!!!ERROR: Queue is Full')
        print('=======================')
    else:
        rear += 1
        queue[rear] = data

큐에 데이터를 추가하는 코드

def deQueue(): # Queue 데이터 추출
    global SIZE, queue, front, rear
    if isQueueEmpty():
        print('========================')
        print('!!!ERROR: Queue is Empty')
        print('========================')
        return None
    else:
        front += 1
        data = queue[front]
        queue[front] = None
        
        # deQueue를 한뒤 빈자리를 채운다.
        for i in range(front + 1, SIZE):
        	queue[i-1] = queue[i]
            queue[i] = None
        front -= 1
        rear -= 1 # 1씩 감소
        
        return data

데이터를 추출하는 deQueue 코드

이전에 작성한 큐가 비었는지에 대한 여부를 확인하는 함수를 먼저 사용한다.

def peek(): # Queue front+1 위치값 확인
    global SIZE, queue, front, rear
    if isQueueEmpty():
        print('========================')
        print('!!!ERROR: Queue is Empty')
        print('========================')
        return None
    else: 
        return queue[front+1]

queue의 가장 앞부분의 값을 확인하는 코드

여기까지 큐의 기능을 구현했고 이제 메인 엔트리 코드를 작성하자

if __name__ == '__main__':
    SIZE = int(input('큐 사이즈 입력 > '))
    queue = [None for _ in range(SIZE)]

    while True:
        select = input('삽입(I)/추출(E)/확인(V)/종료(X) >> ')
        if select.lower() == 'x':
            break
        elif select.lower() == 'i':
            data = input('입력데이터 >> ')
            enQueue(data)
            print(f'큐 상태 : {queue}')
        elif select.lower() == 'e':
            data = deQueue()
            print(f'추출 데이터 : {data}')
            print(f'큐 상태 : {queue}')
        elif select.lower() == 'v':
            data = peek()
            print(f'확인 데이터 : {data}')
            print(f'큐 상태 : {queue}')
        else:
            continue
    
    print('큐 프로그램 종료')

실행하면 먼저 '삽입(I)/추출(E)/확인(V)/종료(X) >> ' 문자열이 출력되고 어떤 값을 입력받았는냐에 따라 각자 다른 함수를

사용한다.

정해진 값이 아닌 다른 값을 입력받으면 무시하고 다시 입력받도록 구성했다.

1. 스택

스택이란 주로 실행취소 기능을 사용할 때 자주 사용하는 자료구조로

가장 마지막에 입력된 값이 가장 먼저 출력되는 형태의 자료구조다.

여기서 새로운 데이터를 넣는 것을 push

최상단에 어떤 데이터가 있는지 확인하는 것을 peek

데이터를 꺼내는 것을 pop

이라고 한다.

1-1. 구현

스택을 구현해보자

SIZE = 10
stack = [None for _ in range(SIZE)]
top = -1 # 초기값 바닥

stack

# 출력결과
# [None, None, None, None, None, None, None, None, None, None]

10칸 짜리 스택을 만들었다. SIZE 변수 값에 따라 칸이 결정되고 굳이 10개일 필요는 없다.

top += 1
stack[top] = '커피'
top += 1
stack[top] = '녹차'
top += 1
stack[top] = '꿀물'
stack

# 실행결과
# ['커피', '녹차', '꿀물', None, None]

Push를 통해 자료를 넣은 모습, 그러나 단순 배열처럼 보인다.

이해를 위해 for문을 사용하여 출력해보자

print('--스택상태--')
for i in range(len(stack)-1, -1, -1):
    print(stack[i])
print('-----------')

# 실행 결과
# --스택상태--
# None
# None
# 꿀물
# 녹차
# 커피
# -----------

이제 가장 먼저 들어간 커피가 최하단에 위치한 걸 볼 수 있다.

data = stack[top]
stack[top] = None
top -= 1
print(f'pop -> {data}')
print('--스택상태--')
for i in range(len(stack)-1, -1, -1):
    print(stack[i])
    
# pop -> 꿀물
# --스택상태--
# None
# None
# None
# 녹차
# 커피

pop을 구현해본 모습

최상단에 위치한 데이터가 출력된 모습을 확인할 수 있다.

if top == -1:
    print('더 이상 데이터가 없습니다.')
else:
    pass

예외처리로 만약 데이터가 없을 경우를 대비한 부분

전체 코드는 아래와 같다.

# 스택 전체 구현
# global 변수
SIZE = 0
stack = []
top = -1

# 스택이 꽉 찼는지 여부 확인
def isStackFull():
    global SIZE, stack, top # 전역변수를 그대로 함수에서도 쓸래!
    if(top >= SIZE -1):
        return True
    else:
        return False
    
# 스택이 비어있는지 여부 확인
def isStackEmpty():
    global SIZE, stack, top
    if(top == -1):
        return True
    else:
        return False
    
# 스택에 데이터 추가
def push(data):
    global SIZE, stack, top
    if (isStackFull()):
        print('Stack is Full')
        return
    else:
        top +=1
        stack[top] = data

def pop():
    global SIZE, stack, top
    if(isStackEmpty()):
        print('Stack is Empty!')
        return None
    else:
        data = stack[top]
        stack[top] = None
        top -= 1
        return data

# top의 데이터 확인
def peek():
    global SIZE, stack, top
    if isStackEmpty():
        print('Stack is Empty')
        return None
    else:
        return stack[top]

# 메인 엔트리
if __name__ == '__main__':
    top = -1
    SIZE = int(input('스텍사이즈 입력 >> '))
    stack = [None for _ in range(SIZE)]

    while True:
        select = input('삽입(I)/추출(E)/확인(V)/종료(X) >> ')
        if select.lower() == 'x': # 입력값 소문자로 변경, 종료
            break
        elif select.lower() == 'i': # 삽입
            data = input('추가할 데이터 >> ')
            push(data)
            print(f'스택상태 : {stack}')
        elif select.lower() == 'e': # 추출
            data = pop()
            print(f'추출 데이터 : {data}')
            print(f'스택상태 : {stack}')
        elif select.lower() == 'v': # 확인
            data = peek()
            print(f'확인 데이터 : {data}')
            print(f'스택상태 : {stack}')
        else: 
            continue

    print('스택 프로그램 종료')

1. 단순 연결 리스트

연결리스트의 종류로는 3가지가 있으나 원형 연결리스트와 이중 연결리스트는 제외하고

단순 연결 리스트만 다루어보자

연결리스트는 배열과 비슷해보이나 배열과는 다르게 중간에 데이터를 넣고 지우기가 굉장히 간편하다.

배열의 경우, 새로운 값을 넣거나 없앨 때, 인덱스 값이 다 조정이 되지만 연결리스트는 그저 두 데이터 사이에 값을 넣으므로 대상이 되는 두 자료만 바꾸어주면 되기 때문이다.

1-1. 구현

구현을 해보자 우선 클래스부터 만들어보자

class Node:
    def __init__(self) -> None:
        self.data = None # 현재 값
        self.link = None # 다음 노드 포인터

    def __str__(self) -> str:
        return f'{self.data}'

Node라는 클래스를 사용해서 연결 리스트의 기본을 만들었다.

node1 = Node()
node1.data = '다현'

print(node1)

node1을 만들고 새로운 값을 넣는다.

이러한 과정을 여러번 한다.

node2 = Node()
node2.data = '정연'
node1.link = node2
node3 = Node()
node3.data = '쯔위'
node2.link = node3
node4 = Node()
node4.data = '사나'
node3.link = node4
node5 = Node()
node5.data = '지효'
node4.link = node5

데이터를 넣어준 모습

print(node1.data, end = ' -> ')
print(node1.link.data, end = ' -> ')
print(node1.link.link.data, end = ' -> ')
print(node1.link.link.link.data, end = ' -> ')
print(node1.link.link.link.link.data)

# 실행 결과
# 다현 -> 정연 -> 쯔위 -> 사나 -> 지효

넣어준 데이터를 출력해보자

print문이 많이 사용되었지만 입력받는 데이터가 정상적으로 나오는 것을 볼 수 있다.

newNode = Node()
newNode.data = '재남'
newNode.link = node2.link # node3
node2.link = newNode

새로운 데이터를 넣어보자, 2번 노드('재남')에 새로운 노드를 삽입했다.

del(node3)

이번엔 3번노드('쯔위')를 삭제해 보았다.

print(node1.data, end = ' -> ')
print(node1.link.data, end = ' -> ')
print(node1.link.link.data, end = ' -> ')
print(node1.link.link.link.data, end = ' -> ')
print(node1.link.link.link.link.data)

# 실행결과
# 다현 -> 정연 -> 쯔위 -> 사나 -> 지효

이렇게 편집된 자료를 출력한 모습이다.

재남이 중간에 추가되고 쯔위가 삭제된 모습을 볼 수 있다.

1. 선형 리스트

데이터를 일정한 순서로 나열한 자료구조로 입력 순서대로 저장하는 데이터에 적당하다.

만약 위 사진에서 중간에 자바스크립트를 3위와 4위 사이에 넣는다고 가정해보자

그럴 경우, 4위부터 마지막에 해당하는 자료들이 전부 한칸씩 뒤로 움직여야 한다.

반대로 없애는 경우도 마찬가지로 수정하고자 하는 부분부터 끝까지 그 순서를 하나씩 다 바꾸어 주어야하기 때문에

중간에 새로운 값을 넣거나 삭제할 때 매우 비효율적이다.

파이썬에서는 배열과 리스트를 구분하지 않지만 자료구조에서는 다르다.

2. 배열의 특징

- 인덱스를 사용해 값에 바로 접근
- 새로운 값을 삽입하거나 특정 인덱스 값을 삭제하기 어렵다.
    - 삽입 또는 삭제시, 인덱스를 다 뜯어고쳐야한다.
- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
- 구조가 간단하므로 코딩 테스트에서 많이 사용한다.

3. 리스트의 특징

인덱스가 없어서 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 즉 값에 접근하는 속도가 느리다.
포인터로 연결되어 있으므로 중간 데이터 삽입 삭제가 빠르다.
선언할 때 크기를 별도로 지정하지 않아도 된다. 즉 리스트의 크기는 가변이며 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.
포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.