마음대로 개발 LIFE

문제 링크

https://www.acmicpc.net/problem/1874

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1

8
4
3
6
8
7
5
2
1

예제 출력 1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2

5
1
2
5
3
4

예제 출력 2

NO

틀린 풀이

import sys

n = int(input())
numbers = sorted(list(range(1, n + 1)), reverse=True)
example = []
for i in range(n):
    example.append(int(sys.stdin.readline().rstrip()))

stack = []
result = []
plus_minus = []

# example에 입력 배열을 저장한다
# numbers에 숫자를 차례로 저장해 pop하고 stack에 추가한다
# stack에서 pop하여 result에 저장한다.

# example을 차례로 순회하며, 해당 차례 값이 numbers에 있는 경우
# 그 값까지 pop하며 stack에 저장한다

# 해당 차례 값이 stack에 있는 경우 pop하여 result에 저장하고,
# pop한 값이 해당 차례 값과 다른 경우, "NO"를 출력하고 프로그램을 종료한다.

for a in example:
    if numbers.count(a) == 1:
        index_numbers = numbers.index(a)
        temp = numbers[index_numbers:]
        temp.reverse()
        stack += temp
        del numbers[index_numbers:]
        plus_minus += ['+'] * len(temp)
        result.append(stack.pop())
        plus_minus.append('-')
        
    elif stack.count(a) == 1:
        index_stack = stack.index(a)
        if index_stack != len(stack) - 1:
            print("NO")
            plus_minus = []
            break
        result.append(stack.pop())
        plus_minus.append('-')
 
if len(plus_minus) != 0:
    for a in plus_minus:
        print(a)

이유

• 시간 초과
  • stack, result를 직접 연산할 필요가 없었다.

맞은 풀이1

import sys

n = int(input())
num_list = [int(sys.stdin.readline()) for _ in range(n)]

stack = [] # 스택
result = [] # 결과값 저장
result_no = True # 불가능한 경우 False
cnt = 0

for num in num_list:
    
    while cnt < num:
        cnt += 1
        stack.append(cnt)
        result.append('+')
        
    # 스택의 가장 위의 수와 num과 같으면 pop하고 result에 '-' 저장
    if stack[-1] == num:
        stack.pop()
        result.append('-')
    # 스택의 가장 위의 수가 num과 다르다면 스택 불가능
    else:
        result_no = False
        break
    
if result_no == False:
    print('NO')
else:
    print('\\n'.join(result))

접근 방식

• numbers에서 pop하여 stack에 저장하는 대신, 그만큼 cnt를 증가시켜 저장했다.
• example(num_list)을 순회하는 방식은 동일했다.
• cnt가 해당 차례 num에 도달할 때까지 증가시키며
  • stack에 cnt를 append하고
  • result에 ‘+’를 append 했다.
• cnt ≥ num인 경우 즉, 해당 num이 이미 stack으로 옮겨진 경우,
  • stack.pop()한 값이 num과 같아야만 한다.
  • 그렇지 않으면 “NO”를 출력하고 프로그램을 종료한다.

종합하면,

위에서 numbers, stack, result, plus_minus로 연산하던 것을

cnt, stack, result(plus_minus와 동일)로 연산하여 reslut를 제외했고,

해당 차례의 수(num)가 stack에 있는지 찾는 연산 대신,

cnt 값을 활용하여 연산 없이 확인하여 시간을 줄였다.

정리

• 스택 자료구조를 활용한 문제이다.
• 불필요한 연산을 줄인다.
• 숫자가 stack에 순차적으로 쌓이고, 스택 최상단의 값만 pop할 수 있다는 사실을 활용한다.
  • 스택 최상단의 값과 원하는 값이 다른 경우, 프로그램을 종료한다.

문제 링크

https://www.acmicpc.net/problem/1654

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입력 1

4 11
802
743
457
539

예제 출력 1

200

틀린 풀이

import sys

k, n = map(int, input().split())
sticks = []
for i in range(k):
    sticks.append(int(sys.stdin.readline().rstrip()))

start = 0
end = sum(sticks) // n + 1  # 가장 이상적인 경우의 랜선 길이를 end로 정한다
mid = 0

# 길이에 따른 랜선 개수를 구하는 함수
def count_sticks(sticks, length):
    count = 0
    for stick in sticks:
        count += stick // length
    return count

while True:
    mid = (start + end) // 2
    count = count_sticks(sticks, mid)
    count2 = count_sticks(sticks, mid + 1)
		# 랜선 개수가 n이면서 길이가 1 늘어났을 때 랜선 개수가 n - 1이 되는,
		# 즉, 랜선 개수가 n일 때의 최대 길이를 mid에 저장한 채로 break 한다
    if count == n and count2 == n - 1:
        break
    if n > count:
        end =  mid - 1
    elif n < count or count2 == n:
        start = mid + 1

print(mid)

이유

• 시간초과
• 정확하게 왜 시간초과인지는 모르겠으나, 로직이 복잡함.

맞은 풀이1

import sys

k, n = map(int, input().split())
sticks = []
for i in range(k):
    sticks.append(int(sys.stdin.readline().rstrip()))

def count_sticks(sticks, length):
    count = 0
    for stick in sticks:
        count += stick // length
    return count

start = 0
end = sum(sticks) // n + 1

result = 0
while start <= end:
    mid = (start + end) // 2
    count = count_sticks(sticks, mid)
    if count < n:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

접근 방식

• 이분탐색
  • 입력의 범위가 매우 큼(K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수)
  • 최적의 해 하나를 찾아들어가는 형식
• 탐색 범위를 줄인다
  • 최대의 end는, 이상적인 경우에 위와 같이 나타남을 이용해 범위를 축소시킨다

정리

• 탐색 문제가 입력의 범위가 매우 크면 → 이분 탐색 떠올리기
• 위의 반복문 형식 기억하기

관련 학습 자료

https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5

12분 30초 - 떡볶이 떡 만들기 문제

난이도: 골드5

https://www.acmicpc.net/problem/2470

n = int(input())
array = sorted(list(map(int, input().split())))

# 포인터 두 개(left, right)와 최소일 때의 값, 위치를 기억하는 변수들(min, min_left, min_right)을 선언
left = 0
right = n - 1
min = abs(array[left] + array[right])
min_left = left
min_right = right


while left < right:
	# 용액의 합이 0이면 기록 후 즉시 종료
    if abs(array[left] + array[right]) == 0:
        min = abs(array[left] + array[right])
        min_left = left
        min_right = right
        break
	# left, right의 차이가 2 이상일 때(이동 시 겹치지 않을 때)
    # left 또는 right가 이동한 경우, 각각의 값을 비교하여 어느 포인터를 이동할지 결정
    if abs(array[left] + array[right - 1]) < abs(array[left + 1] + array[right]) and (right - left) >= 2:
		# 이동한 것이 최소라면, 해당 정보 기록
		if abs(array[left] + array[right - 1]) < min:
            min = abs(array[left] + array[right - 1])
            min_left = left
            min_right = right - 1
        right -= 1
    # 위와 로직 동일
    elif abs(array[left] + array[right - 1]) >= abs(array[left + 1] + array[right]) and (right - left) >= 2:
        if abs(array[left + 1] + array[right]) < min:
            min = abs(array[left + 1] + array[right])
            min_left = left + 1
            min_right = right
        left += 1
    # left, right 차이가 1이라면, 같게 만들어 다음 반복문이 실행되지 않게 함
    else:
        right -= 1
    

print(array[min_left], array[min_right])

# input 입력 받기
n = int(input())
solution = list(map(int, input().split(' ')))

# 정렬하기
solution.sort()

# 이중포인터 설정
left = 0
right = n-1

answer = 2e+9+1 # 기준값
final = [] # 정답

# 투포인터 진행
while left < right:
    s_left = solution[left]
    s_right = solution[right]

    tot = s_left + s_right
    # 두 용액의 합이 0과 가장 가까운 용액을 정답에 담아주기
    if abs(tot) < answer:
        answer = abs(tot)
        final = [s_left, s_right]
	
    # 두 용액의합이 0보다 작다면 왼쪽의 값을 늘려 조금 더 0에 가깝게 만들어준다
    if tot < 0:
        left += 1
    # 반대로, 두 용액의 합이 0보다 크다면 오른쪽의 값을 줄여서 조금 더 0에 가깝게 만들어준다
    else:
        right -= 1

print(final[0], final[1])

전체적인 논리는 비슷하지만,

이동 시 값을 비교한 것이 아니라, 논리를 통해 접근했다.

두 용액의 합이 0보다 작다면, left를 +=1 하고

0보다 크다면, right를 -=1 했다.

굳이 left +=1, right -=1 한 경우를 비교한 후 움직일 필요가 없었던 것이다.

남의 풀이2 (이분 탐색 사용)

출처 : https://latte-is-horse.tistory.com/316

n = int(input())
arr = sorted(map(int, input().split()))  # 정렬된 용액들


def binary_search(s, target):
    global arr
    res = n
    start, end = s, n - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= target:
            res = mid
            end = mid - 1
        else:
            start = mid + 1
    return res


def solution():
    global arr
    v1, v2 = 0, 0
    best_sum = 10 ** 10
    for i in range(n):
        # 이분 탐색 수행: 현재 위치(i) 이후의 용액에서 탐색, 찾는 값은 (현재 용액 * -1)
        res = binary_search(i + 1, -arr[i])
        
        # 찾은 용액의 왼쪽 용액 확인
        if i + 1 <= res - 1 < n and abs(arr[i] + arr[res - 1]) < best_sum:
            best_sum = abs(arr[i] + arr[res - 1])
            v1, v2 = arr[i], arr[res - 1]

        # 찾은 용액 확인
        if i + 1 <= res < n and abs(arr[i] + arr[res]) < best_sum:
            best_sum = abs(arr[i] + arr[res])
            v1, v2 = arr[i], arr[res]
    
    print(v1, v2) # i 번째 용액을 확인할 때 i + 1번 용액부터 확인하기 때문에 항상 v1 <= v2 이다.


solution()

이분 탐색으로 풀었다는 것이, 직관적인 논리로 다가오지는 않는다.

하지만, 아래와 같은 사고 흐름이라면 직관적이다.

1. 브루트포스(전체 경우의 수에 대해 탐색)를 생각

2. 시간 복잡도를 고려하면 시간 초과가 우려됨.

3. 모든 경우의 수를 탐색하되, 이분 탐색을 사용하여 시간 복잡도를 줄인다.

위와 같이 생각했다면,

이분 탐색 함수를 우선 구현하고,

전체 용액에 대해 이분 탐색을 실행하는 알고리즘을 생각할 수 있었을 것이다.

세상은 넓고 똑똑쓰들은 많다..

나도 한 자리 주쇼..

난이도: 실버3

https://www.acmicpc.net/problem/3273

import sys

n = int(input())
array = sorted(list(map(int, sys.stdin.readline().split())))	# 리스트 입력 시 정렬하여 저장
x = int(input())

count = 0

for i in range(len(array)):
    for j in range(i, len(array)):
        if array[i] >= (x//2 + 1):	# 앞의 수와 더했을 때 x보다 반드시 큰 경우 제외
            break
        if array[i] + array[j] == x:	# 이미 탐색한 경우(i와 i-1 등)를 제외하여 i, j 설정
            count += 1
	
print(count)

import sys

n = int(input())
array = sorted(list(map(int, sys.stdin.readline().split())))	# 리스트를 정렬하여 입력 받기
x = int(input())

count = 0
left, right = 0, n-1	# 두 포인터 설정

while left < right:	# 두 포인터가 교차되는 순간 반복문 종료
    sum = array[left] + array[right]
    if sum == x:	# left, right가 가리키는 값의 합이 x와 같은 경우
        count += 1
        left += 1	# left를 이동시켜 sum > x로 만든다
    elif sum > x:	# 값이 큰 경우 right를 이동시켜 값을 줄인다
        right -= 1
    elif sum < x:	# 값이 작은 경우 left를 이동시켜 값을 키운다
        left += 1
    
print(count)

시간 복잡도가 크게 줄어 시간 초과 없이 문제를 풀 수 있었다.

'나의 풀이' 에서 사용한 알고리즘은, 중첩 반복문이기에 O(N^2)의 시간 복잡도를 가진다.

'남의 풀이' 에서 사용한 알고리즘은, 좌우 포인터가 움직이면서 N번의 탐색을 하기에

O(N)의 시간 복잡도를 가진다.

두 포인터에 대해 알게 된 문제였다.

난이도 : 실버3

https://www.acmicpc.net/problem/1388

나의 풀이 (DFS, 재귀함수 활용)

import sys
n, m = map(int, sys.stdin.readline().split())	# 그래프 크기 입력

# 그래프 입력 받기
graph = []
for i in range(n):
    graph.append(list(input()))

visited = [[0] * m for _ in range(n)]

# 세로 나무 판자에 대한 DFS 재귀 함수
def dfs1(r, c):
    if r >= n or c >= m:
        return False
    if visited[r][c] == 0 and graph[r][c] == '|':
        visited[r][c] = 1
        dfs1(r + 1, c)
        return True
    return False

# 가로 나무 판자에 대한 DFS 재귀 함수
def dfs2(r, c):
    if r >= n or c >= m:
        return False
    if visited[r][c] == 0 and graph[r][c] == '-':
        visited[r][c] = 1
        dfs2(r, c + 1)              
        return True
    return False

result = 0
# 전체 위치에 대해 DFS 함수 반복
for i in range(n):
    for j in range(m):
		# DFS 함수가 True를 반환하면 result += 1
        if dfs1(i, j) == True or dfs2(i, j) == True:
            result += 1
            # 해당 round의 탐색 결과를 비교하기 위해 visited를 출력
            # for k in range(n):
            #     print(visited[k])
            # print('------')

print(result)

BFS 문제를 찾아 들어가서 BFS로 풀려고 했으나,

풀이법 떠올리기도 쉽지 않고, queue를 능숙하게 구현하기도 어려워서

나도 모르게 익숙한 DFS 재귀함수로 풀이해버렸다.

가로 또는 세로 방향으로 이어진 나무 판자를 묶어서 1개를 count하는 것이므로,

재귀함수를 두 개 설정하여

한 개는 가로 나무판자의 같은 방향 여부를 오른쪽으로 가면서 탐색하도록,

다른 한 개는 나무판자의 같은 방향 여부를 아래쪽으로 가면서 탐색하도록 구현하였다.

오른쪽과 아래쪽으로 한정하지 않고, 상하 또는 좌우를 탐색하도록 구현했어도,

어차피 이미 탐색한 결과가 기록되어 왼쪽 또는 위쪽으로 움직이는 일은 없었을 것이다.

(근데 이건 다른 DFS 문제도 마찬가지 아닌가..?)

남의 풀이가 궁금해진다.

남의 풀이1 (BFS 활용)

from collections import deque

n, m = map(int, input().split())	# 그래프 크기 입력
result = 0

graph = [list(input()) for _ in range(n)]	# 나무 판자 그래프 정보 입력
visited = [[0] * m for _ in range(n)]	# 방문 여부 그래프 초기화

# BFS 함수 선언
def bfs(r, c):
    queue = deque([(r, c)])
    
    # queue가 비어있지 않다면 계속 반복
    while queue:
        r, c = queue.popleft()
		# 위치가 오류라면 continue
        if r < 0 or r >= n or c < 0 or c >= m:
            continue
		# 이미 방문한 위치라면 continue
        if visited[r][c] == 1:
            continue
		
        # 가로 판자에 대한 로직
        if graph[r][c] == '-':
            visited[r][c] = 1	# 방문 정보 저장
            # 좌 또는 우에 대하여, 가능한 위치인지 판단하고
            # 같은 방향의 나무 판자라면 queue에 추가
            if c - 1 >= 0:
                if graph[r][c - 1] == '-':
                    queue.append((r, c - 1))
            if c + 1 < m:
                if graph[r][c + 1] == '-':
                    queue.append((r, c + 1))
                    
		# 세로 판자에 대한 로직 - 가로와 동일
        if graph[r][c] == '|':
            visited[r][c] = 1
            if r - 1 >= 0:
                if graph[r - 1][c] == '|':
                    queue.append((r - 1, c))
            if r + 1 < n:
                if graph[r + 1][c] == '|':
                    queue.append((r + 1, c))
            
# 전체 위치에 대해 BFS 함수 적용
for i in range(n):
    for j in range(m):
        if visited[i][j] == 0:
            bfs(i, j)
            result += 1

print(result)

BFS와 큐 자료구조를 이용한 풀이이다.

확실히 DFS, 재귀함수로 푼 것이나 로직은 큰 차이가 없다.

어떤 알고리즘을 사용했을 때 탐색이 일어나는 순서와 로직이 머릿속으로 그려지기만 한다면,

가능한 문제에서는 어느 알고리즘을 사용해도 상관 없는 듯하다.

남의 풀이2 (알고리즘 활용 X)

# 방 바닥의 세로 크기 n, 가로 크기 m
n,m = map(int, input().split())
graph = [] 	# 2차원 리스트의 맵 정보 저장할 공간
for _ in range(n):
    graph.append(list(input()))
 
# '-'모양의 나무 판자 개수 계산
count = 0
for i in range(n):
    a = ''
    for j in range(m):
        if graph[i][j] == '-':
            if graph[i][j] != a:
                count += 1
        a = graph[i][j]
 
# 'ㅣ'모양의 나무 판자 개수 계산
for j in range(m):
    a = ''
    for i in range(n):
        if graph[i][j] == '|':
            if graph[i][j] != a:
                count += 1
        a = graph[i][j]
 
print(count)

와 .. 너무 간단하다.

5 x 7 크기의 그래프를 가정하면

각 행을 오른쪽으로, 각 열을 아래쪽으로 총 12번 이동하면서

연결된 판자는 1개로 세고, 다른 방향의 판자가 나오면 판별자를 초기화하는 식으로 구현한 풀이이다.

간단한 구현 문제가 되었다..

난이도 : 실버2

https://www.acmicpc.net/problem/1012

나의 풀이

import sys
sys.setrecursionlimit(10000)

t = int(input())	# 테스트 케이스 개수
result_list = [0 for i in range(t)]	# 출력을 위한 리스트 선언

# 상하좌우 위치에 대해 재귀함수를 호출하는 dfs 함수 선언
# 특정 위치에 배추가 있을 때(값이 1일 때)만 작동
# 탐색한 곳의 값을 0으로 변경
def dfs(x, y):
    # print('x, y in dfs :', x, y)
    if x < 0 or x >= m or y < 0 or y >=n:
        return False
    if graph[y][x] == 1:
        graph[y][x] = 0
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True
    return False

# 테스트 케이스 개수 만큼 로직 작동
for p in range(t):
    m, n, k = map(int, sys.stdin.readline().split())	# 그래프의 가로, 세로 길이와 배추 개수
    graph = [[0 for x in range(m)] for y in range(n)]

	# 배추 심기
    for _ in range(k):
        x, y = map(int, sys.stdin.readline().split())
        graph[y][x] = 1

    result = 0
    # dfs로 탐색 결과가 True이면(해당 구역의 인접 배추를 모두 탐색했으면) 결과를 + 1
    for i in range(m):
        for j in range(n):
            if dfs(i, j) == True:
                result_list[p] += 1

# 테스트 케이스 개수만큼의 결과를 출력
for i in range(t):
    print(result_list[i])

input() 함수를 사용했더니 함수가 굉장히 많이 호출되어 실행 시간이 많이 걸렸다.

sys.stdin.readline()으로 대체했더니 실행 시간이 340ms 에서 84ms로 감소했다.

DFS를 활용한 해당 풀이에 대해서는 문제 없이 잘 푼 것 같다.

남의 풀이

import sys

def dfs(lst,visited, r, c):
    stack = [(r,c)]
    visited[r][c] = 1
    while(stack):
        r,c =stack.pop()
        dr = [-1,0,1,0]
        dc = [0,-1,0,1]
        for i in range(4):
            nr = r+dr[i]
            nc = c+dc[i]
            if 0<=nr<M and 0<=nc<N and not visited[nr][nc] and lst[nr][nc] ==1:
                stack.append((nr,nc))
                visited[nr][nc] =1

                
T = int(input())
for i in range(T):
    cnt = 0
    M, N, K = map(int,sys.stdin.readline().split())
    lst = [[0]*N for i in range(M)]
    visited = [[0]*N for i in range(M)]
    for i in range(K):
        r,c = map(int,sys.stdin.readline().split())
        lst[r][c] = 1
    for r in range(M):
        for c in range(N):
            if not visited[r][c] and lst[r][c] ==1:
                dfs(lst, visited, r,c)
                cnt += 1
    print(cnt)

아래 부분은 나의 풀이와 거의 똑같다.

다른 점은, lst와 visited로 배추 리스트와 방문 리스트를 분리해서 사용했다는 것이다.

dfs 함수 로직이 다른데,

1. 재귀함수가 아닌 스택 구조를 사용했다.

2. (재귀함수가 아니니 당연히) r, c의 변화량을 리스트로 사용하였다.

+ x, y를 위치 변수로 사용하는 게 수학에서의 좌표계와 혼동이 되는 것 같다.

r, c을 사용하는 버릇을 들여야겠다.

numpy 라이브러리를 사용할 때는 zeros 메서드로 쉽게 만들었던 영행렬을

코딩테스트 문제 풀이에서는 어떻게 사용할지 감이 잡히지 않아 찾아보았다.

# graph1, graph2는 같은 결과
graph1 = [[0 for x in range(m)] for y in range(n)]
graph2 = [[0] * m for _ in range(n)]

위와 같이 graph를 선언하면

n x m 의 영행렬(zero matrix)를 선언할 수 있다.

1 x m(columns) 의 영행렬을 n번(rows) 선언하는 것과 마찬가지이다.

기본적인 자료구조인 스택, 큐를 python으로 구현하는 방법을 정리해보려 한다.

스택(stack) :

- 먼저 들어온 것이 나중에 나가는 자료구조

- 선입후출(FILO: First In Last Out)

- 박스쌓기로 기억 (먼저 쌓은 박스가 가장 아래에 위치)

- 단순한 list method(append, pop) 사용으로 구현!

Python으로 스택(stack) 구현

stack = []

stack.append(5)	# 각 연산 시간복잡도 O(1)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop(5)

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

위에 있는 그림처럼, 오른쪽에서 왼쪽으로 들어가는 기다란 관을 떠올리면 연상이 쉽다.

큐(queue) :

- 먼저 들어온 것이 먼저 나가는 자료구조

- 선입선출(FIFO: First In First Out)

- 입구와 출구가 뚫려있는 터널로 기억 (또는 리그오브레전드 큐(대기열) ㅋㅋ)

- collections 라이브러리의 'deque' 모듈을 사용하여 구현!

Python으로 큐(queue) 구현

from collections import deque

queue = deque()

queue.appned(5)	# 각 연산 시간복잡도 O(1)
queue.appned(2)
queue.appned(3)
queue.appned(7)
queue.popleft()
queue.appned(1)
queue.appned(4)
queue.popleft()

print(queue)	# 먼저 들어온 순서대로 출력, deque([3, 7, 1, 4])
queue.reverse()
print(queue)	# 나중에 들어온 순서대로 나열, deque([4, 1, 7, 3])

(reverse를 하지 않은 기준으로)

오른쪽에서 왼쪽으로 향하는 터널을 생각하면 연상이 쉽다.

단순 리스트로 큐를 구현하게 되면,

pop() 메서드에 index를 입력하고,

해당 인덱스 값을 반환한 후 조정하는 과정에서

O(k)의 시간복잡도가 발생하므로,

큐는 deque 모듈을 사용하는 것이 좋다.

참고 자료 :

https://www.youtube.com/watch?v=7C9RgOcvkvo