여러가지 조건에서 최단거리를 구하는 알고리즘 문제가 나오기 때문에 관련 공부는 필수인 듯 하다.

기존에는 다익스트라 알고리즘만 활용가능한 수준이었는데 이번에 11403번 문제를 보면서 플로이드 워셜 알고리즘을 처음 사용해 보았다.

처음 풀이에서는 플로이드 워셜 알고리즘을 사용하지 않고, deque를 활용하여 문제를 풀었는데 백준 문제 기준으로 deque를 사용한 풀이의 시간이 덜 소요되는것으로 보였다.

두가지 풀이에서 어떤 점이 소요시간의 차이를 일으켰는지 알아보고자 한다.

1. deque 활용

deque를 활용한 풀이는 다음과 같다.

import sys
import time

sys.stdin = open("input.txt")
from collections import deque
n = int(input())
city = [list(map(int, input().split())) for _ in range(n)]

# deque 버전
def solution_deque():
    visit = [[0]*n for _ in range(n)]
    dq = deque()
    for from_first, m in enumerate(city):
        for to_city, moving in enumerate(m):
            if moving == 1 and visit[from_first][to_city] == 0:
                visit[from_first][to_city] = 1
                dq.append(to_city)
                while dq:
                    to_city = dq.popleft()
                    for next_to, next_move in enumerate(city[to_city]):
                        if next_move == 1 and visit[from_first][next_to] == 0:
                            visit[from_first][next_to] = 1
                            dq.append(next_to)

    for i in visit:
        print(*i)

여기서 visit은 방문여부를 체크하기도 하지만, 최종 답을 적기 위해 그 초기값을 0으로 하였다.

city 이중배역에 문제로 주어진 간선 정보를 담았다.

이후 첫번째 for loop 에서 현재 확인하고자 하는 노드를 "from_fist" 값으로 하고, from_first와 연결된 노드를 "to_city" 라고 하였다.

from_first 에서 to_city 로 가는 간선이 존재한다면 visit정보를 1로 업데이트 하고, 간선 정보를 deque에 담는다.

이후 deque값이 존재할 동안 (while 조건) 이어지는 간선 정보를 확인한다.

to_city 를 기준으로 for loop로 찾는 도시 "next_to" 의 1인 경우 (next_move가 1) 방문여부를 확인하고 from_first에서 next_to가 연결되었음을 체크한다.

또한, to_city 에서 next_to의 연결정보를 다시 deque에 담아 next_to의 도시에서 시작하는 연결정보를 계속해서 탐색한다.

from collections import deque
# from_first = 0
# to_city = 1
city = [[0, 1, 0], [0, 0, 1], [1, 0, 0]]
"""
from_first에서 to_city의 연결정보가 1이므로 방문여부 확인 후 체크한다.
그리고 이어서 탐색하기 위해 해당 연결 정보를 deque에 담는다
"""
dq = deque()
if city[from_first][to_city] == 1 and visit[from_first][to_city] == 0:
	visit[from_first][to_city] = 1
    dq.append(to_city)
    # dq에 담긴 정보에서 이어서 탐색 한다. (from_first에서 시작한 연결정보가 끝날때까지)
    while dq:
    	from_city, to_city = dq.popleft()
        for next_to, next_move in enumerate(city[to_city]):
        	if next_move == 1 and visit[first_from][next_to] == 0:
            	visit[first_from][next_to] = 1
                """
                to_city에서 next_to가 연결되어있다면 from_first에서 next_to도 연결된 것이다.
                방문여부를 체크하고, 이어서 연결정보를 탐색하게 한다.
                """
                dq.append(next_to)

한가지 상황을 예로 들어 과정을 풀이하면 위와 같다. 총 시간복잡도는 N^3으로 확인된다. 단, 자기자신의 노드로 가는 경우는 0이기 때문에 해당 경우의 수는 확인하지 않는다.

2. 플로이드-워셜 활용

플로이드-워셜 알고리즘이란 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

위 알고리즘을 더욱 잘 활용할수 있는 예제는 "가중치가 있는 간선" 이 주어졌을때 인데, 위 문제의 경우 가중치가 없어 오로지 "연결 가능한 노드인지" 를 확인만 하면 된다.

플로이드-워셜 알고리즘으로 i 에서 j 노드로 갈때 k 노드를 거쳐서 갈수있는지 확인하여 i 에서 j 노드의 연결을 확인한다. i에서 j 노드의 모든 수를 확인하는 N^2 시간복잡도에서 k 노드 확인 경우를 추가하여 최종적으로 N^3의 시간복잡도를 보이고, 모든 노드를 확인하여 제외되는 경우는 없다.

def solution_floid():
    """
    i에서 j의 경로를 탐색하면서 거쳐가는 k 노드의 값을 확인, k 값으로 연결된 i, j는 연결가능하다
    """
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if city[i][k] == 1 and city[k][j] == 1:
                    city[i][j] = 1
    for row in city:
        print(*row)

3. 두 풀이의 풀이시간 차이

2) 동일한 노드수에서 간선 비율의 차이에 따른 시간차이

i. 노드의 수가 14개

당연히 알고리즘으로 풀면 더 빠르겠지! 싶었던 생각이 예제로 소요시간을 확인하며 깨졌다.

노드의 수가 14개이면서, 간선의 비율이 약 25%, 약 52% 약 92% 일때 시간을 측정해 보았다.

# 노드의 수 14 / 간선비율 약 25%
# deque 소요시간 : 0.0006220340728759766
# floyd 소요시간 : 0.0008339881896972656

14
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 1 0 1 0 1 0 1 0 1 0 0 0
0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0 0 0 1 0 0 0

# 간선 비율 약 52%
# deque 소요시간 : 0.0006856918334960938
# floyd 소요시간 : 0.0009648799896240234

14
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0

# 간선비율 약 92%
# deque 소요시간 : 0.0006418228149414062
# floyd 소요시간 : 0.0008568763732910156

14
0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0

노드수가 14개일 경우 간선의 비율차로는 플로이드-워셜의 소요시간이 항상 더 길게 나온다.

ii) 노드 수가 5개

# 간선비율 약 80%
# deque 소요시간 : 9.012222290039062e-05
# floyd 소요시간 : 8.797645568847656e-05

5
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0

# 간선비율 약 20%
# deque 소요시간 : 9.918212890625e-05
# floyd 소요시간 : 9.894371032714844e-05

5
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0

노드의 수가 5개이거나, 이의 약 3배인 14개이거나 플로이드-워셜 풀이로 풀었을 경우 소요시간이 더 크게 나오는것을 확인 할 수 있다.

극단적으로 노드의 수가 3개일 경우에는 플로이드-워셜의 소요시간이 더 적게 나오긴 하다

# 간선비율 : 약 33%
# deque 소요시간 : 3.910064697265625e-05
# floyd 소요시간 : 2.9087066650390625e-05

3
0 1 0
0 0 1
1 0 0

하지만 보통의 문제에서는 n의 범위가 3까지일리가 없으니... 시간복잡도를 생각한다면 플로이드-워셜이 아닌 deque를 사용한 풀이를 선택해도 될것같다.

문제

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

분할정복 알고리즘 ?
기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나  병합정렬이 있다.
출처 : 나무위키 - 분할 정복 알고리즘

사실 처음엔 큰 문제를 작게 쪼개서 계산?? 이 문제에 적용이 된다고? 싶었지만 처음 접해보는 분할정복 문제였어서 감이 안왔던듯 하다.

직접 문제를 손으로 써내려가면서 이해해 보았다.

문제에서 주어진 조건은 크게 두가지가 있다.

1. 주어진 영역 내 서로 다른 색이 존재 할 경우 해당 영역을 4분할 한다.

2. 정사각형 내 동일 색상 단위로 총 몇개 정사각형이 존재하는지 출력한다.

따라서 1번 조건에 맞을 경우 문제를 쪼개면 되는것이고, 쪼갠 상황에서 2번 조건에 맞는다면 답으로 기록하면 된다.

시작점은 [0, 0] 으로 한다. 시작점의 색상을 기억해 두고, 일정한 인접 행렬을 탐색하다가 다른 값이 나온다면 1번 조건에 부합하므로 즉시 4분할을 해준다.

분할된 영역의 구간은 규칙적으로 변경된다.

python의 // 는 값을 나눈 몫을 반환하므로 n값이 8일때 n//2를 하면 그 값은 4가 된다. 또한 python의 for loop에서 range의 end parameter는 해당 값 "미만"으로 동작하기 때문에 n//2 값을 넣어주면 된다.

처음에 탐색의 시작을 [0,0] 에서 한다고 하였으므로 첫번째 이중 for loop의 탐색 범위는 탐색x는 (이하 xx) x ~ x+n(미만) 이고, 탐색y는 (이하 yy) y ~ y+n 이 된다.

첫번째 cut 에서 또다시 서로다른 색이 발견되어 4분할을 진행해 줄때, x값과 y값의 범위 변화는 규칙적으로 변경된다.

위 규칙을 토대로 풀이를 작성하면 아래와 같다.

import sys
sys.stdin = open("input.txt")
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

white = 0
blue = 0
def cut(x, y, n):
    global white
    global blue
    check_color = board[x][y]
    for xx in range(x, x+n):
        for yy in range(y, y+n):
            if board[xx][yy] != check_color: # 조건 1 부합 : 4분할 진행
                cut(x=x, y=y, n=n//2) # 1영역 : x = x ~ x+(n//2) | y = y ~ y+(n//2) | n = n//2
                cut(x=x, y=y+n//2, n=n//2) # 2영역 : x = x ~ x+(n//2) | y = y+n//2 ~ y+n//2+n | n = n//2
                cut(x=x+n//2, y=y, n=n//2) # 3영역 : x = x+n//2 ~ x+n//2+n | y = y ~ y+(n//2) | n = n//2
                cut(x=x+n//2, y=y+n//2, n=n//2) # 4영역 : x = x+n//2 ~ x+n//2+n | y = y+n//2 ~ y+n//2+n | n = n//2
                return # 분할은 분할대로 호출해놓고, 값에 적용되는걸 막기 위해 분할 뒤 return 한다.
    # 조건 2 부합 : 분할되지 않으면 모두 색이 같다는 것으로 정답으로 기록한다.
    if check_color == 1:
        blue += 1
    else:
        white += 1

cut(0, 0, n)  # 시작 조건 [0,0]
print(f"{white}\n{blue}")

큰 문제를 쪼갠다는 것과, 4분할 처리 하는 것에 대해 알 수 있었다.!

이분탐색법을 이용해 최소/최대 값으로 답이 결정되는 알고리즘을 풀어보자

[입력]     [출력]
5 2       3
7
4

[입력]    [출력]
7 5       4
7
1
7
4
4

이분탐색법은 주어진 정답 구간의 최소값과 최대값을 각각 left point, right point로 잡고, 그의 중간값을 확인하여 답에 맞는지 확인하며 찾아가는 방법이다. 기준이 되는 lt, rt의 중간값으로 왼쪽구간, 오른쪽 구간을 나누기 때문이 이분탐색이라고 한다.

위 문제에서 정답으로 요구하는것은 "질투수치" 이다. 질투수치는 보석을 나눠받은 학생들 중 최고로 많은 보석을 가져간 학생의 보석갯수를 의미한다. 이 값의 최소치를 구한다는 것은 곧, 학생들에게 보석을 최대한 적게 골고루 나누준다는 뜻이다.

위 문제에서 주어진 조건은

1. 학생은 한가지 색의 보석만 받을 수 있다.

2. 보석은 모두 나눠주어야 한다. (보석이 남으면 안됨) 그러나 보석을 아예 못받는 학생이 있을 수 있다. (5명중 3명만 보석받아도 괜찮음)

위 두가지 조건에 유의하며 코드를 작성해 보았다.

import sys
sys.stdin = open("input.txt")

students, color = map(int, input().split())
jewels = [int(input()) for _ in range(color)]

lt = 1  # 보석을 나눠받는 가장 작은 수 1
rt = max(jewels) # 보석을 나눠받는 가장 큰 수
while lt <= rt:
    mid = (lt + rt) // 2  # 중간값 탐색
    get_s = 0  # mid 갯수로 보석을 나눠받은 총 학생 수
    for j in jewels:
        if j % mid == 0:
            get_s += (j//mid) # 똑 나눠 떨어지면 몫이 곧 그 수만큼 나눠받은 학생 수
        else:
            get_s += (j//mid) + 1 # 안나눠떨어지면 몫에다가 나머지만큼 가져간 학생 수
            
    if get_s > students:
    	# 나눠받은 학생 수 가 주어진 학생수보다 많다면 더 많이씩 나눠줘야 한다.
        lt = mid + 1
    else:
        # 나눠받은 학생 수가 주어진 학생수보다 같거나 적다면 더 적게 나눠줘도 된다.
        rt = mid - 1
print(lt)  #

[변수] mid, get_s

- 이분탐색을 진행하면서 몇개의 보석으로 학생들이 나눠받을 것인지 mid 값을 정한다. 이 값은 항상 구간의 최소값과 최대값의 중간값이다. (2로 나눈 몫)

- mid 갯수만큼 보석을 나눠받을때, 한개 색상의 보석이 mid의 배수이면 그 몫 만큼의 학생수가 보석을 나눠갖는다.

- mid 갯수만큼 보석을 나눠받을때, 한개 색상 보석의 수가 mid로 나누었을때 나머지가 발생한다면 몫의 수 만큼의 학생이 mid값 만큼의 보석수를 나눠갖고, 한 학생은 나머지 수 만큼 보석을 나눠받게 되므로 몫 + 1 만큼의 학생들이 나눠받게 된다.

[계산하기] lt, rt

> lt = mid + 1

mid 갯수만큼 학생들이 보석을 나눠가질때, 나눠갖게된 학생의 수가 문제로 주어진 students의 수보다 크다면 이는 보석을 좀더 많이씩 나눠가져서 나눠받는 학생의 수를 줄여하 한다는 것을 의미한다.

따라서 mid 갯수만큼은 정답이 되지 않는것을 인지하고, 탐색 범위를 높이기 위해 최소값이었던 lt를 mid+1만큼으로 변경한다.

> rt = mid - 1

mid 갯수만큼 학생들이 보석을 나눠가질때, 나눠받은 학생의 수가 주어진 students의 수보다 같거나 적다면 일단 mid값은 정답이 된다는 것이다. 하지만 답에서 구하는것은 그 값의 최소값이기 때문에 더 작은 값도 정답이 될수 있는지 탐색해야 한다.

따라서 mid 값보다 1 작은수로 rt값을 변경하고 그 사이값들을 비교한다.

[정답 도출하기] lt

while 문을 빠져나오는 조건은 두가지가 있다.

1. lt와 rt의 값이 동일할때, lt 값이 mid+1 된 경우

2. lt와 rt의 값이 동일할때, rt 값이 mid-1 된 경우

먼저 1번의 경우 새로운 lt값이 된 mid+1값은 언젠가 그 값이 정답이었던 mid 값이다. 따라서 while 조건에서 벗어나게 되어 더이상 탐색이 불가능하게 되더라도 lt값은 이전에 정답으로 체크되었던 mid 값이었으므로 정답이 된다.

2번의 경우 이미 2번의 조건이 정답에 부합하는 조건이므로 그 당시의 lt값 (이때는 lt와 rt가 같지만 한번 더 탐색을 위해 rt값이 줄어들어버린것) 을 정답으로 확정한다.

주어진 예제 1번을 확인해보면 [정답 도출하기]의 2번 상태에서 while 문이 종료된다. 예제2번의 경우 1번 상태에서 while 문이 종료되는데 풀이를 확인해보면 아래와 같다.

15810번

위와 동일한 개념으로 문제를 풀면 된다.

import sys
sys.stdin = open("input.txt")

staff, ba = map(int, input().split())
times = list(map(int, input().split()))

lt = 1
rt = max(times) * ba

while lt <= rt:
    mid = (lt + rt) // 2
    # 총 소요시간이 mid일때 몇개까지 풍선을 불 수 있는가
    total_balloon = 0
    for one in times:
        # 불고나서 몇분 남았다 해도 그 시간안에 부는것 완성 못하므로 나머지는 버린다.
        total_balloon += mid//one
    if total_balloon >= ba:
        # 목표갯수와 같거나 보다 많다면 총 소요시간을 줄여본다
        rt = mid - 1
    else:
        # 목표갯수보다 모자르다면 총 소요시간을 늘려준다
        lt = mid + 1
print(lt)

최소 / 최대 값이 답으로 결정되는 알고리즘 풀이법에는 이렇게 이분탐색법을 활용할수 있으므로 이 개념을 꼭 익혀두면 좋다!

알고리즘 문제를 풀다보면 2중배열을 조작하여 풀어야 하는 유형이 종종 보인다.

자주 나오는 유형은 그 풀이공식을 어느정도 외워두는것이 좋은 듯 하다.

문제

A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5]
   ↓                                       ↑
A[2][1]   A[2][2] ← A[2][3] ← A[2][4]   A[2][5]
   ↓         ↓                   ↑         ↑
A[3][1]   A[3][2] → A[3][3] → A[3][4]   A[3][5]
   ↓                                       ↑
A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5]

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000 (16926번) / 1 ≤ R ≤ 10**9 (16927번)
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

---

 먼저 "반시계 방향" 으로 회전을 어떻게 할 것인가? 를 두고 한참 고민했다. 모두가 같은 방향으로 회전하는 것이 아니라 총 4가지 방향으로 회전해야 하기 때문에

1. 어느 포인트에서 회전방향을 바꾸어야 하는지
2. 얼마만큼 길이를 해당 방향으로 회전해야 하는지

를 구하는게 관건이었다.

 

이 문제를 풀기 위해서는 "이중배열을 1차원 배열로 풀기" 가 포인트이다.

1. 이중배열을 1차원 배열로 풀기

1차원 배열로 풀기 위해서는 회전하는 기준이 되는 묶음 (이하 루프) 의 갯수를 파악해야 한다. 제한조건에서 n과 m중 최솟값은 2의 배수임을 명시했기 때문에 루프가 생기지 않는 가운데 부분은 고려하지 않는다.

 

가로, 세로의 최솟값을 2로 나눈 몫 만큼 루프가 형성된다.

# 1. 가로 4, 세로 5
standard = min(4, 5) // 2 # => 2

# 2. 가로 5, 세로 4
standard = min(5, 4) // 2 # => 2

# 3. 가로 2, 세로 4
standard = min(2, 4) // 2 # => 1

# 4. 가로 6, 세로 2
standard = min(6, 2) // 2 # => 1

따라서 새로 만들어질 1차원 배열도 루프의 갯수만큼 생성될 것이다.

위, 오른쪽, 아래, 왼쪽 순서대로 배열을 새로 정의하는데 이때 "모서리에 있는 숫자" 의 중복 처리를 주의해야 한다.

위와 아래에는 모든 모서리를 포함하도록 하고, 오른쪽과 왼쪽은 모서리를 제외한 변의 숫자만을 처리하도록 한다.

n, m, r = map(int, input().split()) # n = 세로 / m = 가로 / r = 회전 수
board = [list(map(int, input().split())) for _ in range(n)]
new_board = [[0]*m for _ in range(n)]
q = deque()
# 2차원 배열을 1차원 배열로 펼치기
loop_count = min(n, m) // 2

for i in range(loop_count):
    q.clear()
    # 위쪽
    q.extend(board[i][i:m-i])
    # 오른쪽 (모서리 제외)
    q.extend([row[m-i-1] for row in board[i+1:n-i-1]])
    # 아래쪽
    q.extend(board[n-i-1][i:m-i][::-1])
    # 왼쪽 (모서리 제외)
    q.extend([row[i] for row in board[i+1:n-i-1][::-1]])
    q.rotate(-r)

또한 위와 아래는 숫자 처리 방향이 반대이고, 오른쪽과 왼쪽도 서로 반대방향이므로 아래쪽과 왼쪽의 수를 배열로 생성할때에는 [::-1] 을 하여 순서를 반대로 되게 해준다.

2. r만큼 회전시키기

루프를 1차원 배열로 만든 뒤 r의 횟수만큼 회전을 시켜줌에 따라 pop, popleft, append, appendleft 가 발생한다.

문제는 "반시계 방향" 이므로 popleft와 append가 일어나게 된다.

하지만 python의 deque 에서는 회전을 동작하는 rotate 함수가 있으므로 이를 사용해 준다.

왼쪽으로 회전할때는 음의값을, 오른쪽으로 회전할때는 양의 값을 인자로 받는다.

from collections import deque

dq = deque()
dq.extend([1, 2, 3, 4])

# 좌로 회전
dq.rotate(-2) # => [3, 4, 1, 2]

# 우로 회전
dq.rotate(2) # => [3, 4, 1, 2]

# r 만큼 좌로 회전 (반시계 방향)
q.rotate(-r)

3. 1차원 배열을 2차원 형태로 가공하기

회전이 완료된 1차원 배열을 다시 원래 자리의 2차원 배열 형태로 만들어 주어야 한다.

별다른 공식은 없고 위치를 주의하여 넣어주면 된다.

    # 위
    for j in range(i, m-i):
        new_board[i][j] = q.popleft()

    # 오른쪽
    for j in range(i+1, n-i-1):
        new_board[j][m-i-1] = q.popleft()
    # 아래쪽
    for j in range(m-i-1, i-1, -1):
        new_board[n-i-1][j] = q.popleft()

    for j in range(n-i-2, i, -1):  # 왼쪽
        new_board[j][i] = q.popleft()

q 에는 회전이 완료된 수들이 순서대로 들어있다. 1차원 배열에 담았던 순서대로 위 -> 오른쪽 -> 아래쪽 -> 왼쪽 으로 처리해 준다.

이때 for-loop 에서 range(a, b, c) 형태는 a 부터 b 까지 c의 값만큼 더하여 처리한다는 뜻이다.

전체 풀이

import sys
from collections import deque
sys.stdin = open("input.txt", "r")
n, m, r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
new_board = [[0]*m for _ in range(n)]
q = deque()
# 2차원 배열을 1차원 배열로 펼치기
loop_count = min(n, m) // 2

for i in range(loop_count):
    q.clear()
    # 위쪽
    q.extend(board[i][i:m-i])
    # 오른쪽 (모서리 제외)
    q.extend([row[m-i-1] for row in board[i+1:n-i-1]])
    # 아래쪽
    q.extend(board[n-i-1][i:m-i][::-1])
    # 왼쪽 (모서리 제외)
    q.extend([row[i] for row in board[i+1:n-i-1][::-1]])
    q.rotate(-r)

    # 다시 board 정렬하기
    # 위
    for j in range(i, m-i):
        new_board[i][j] = q.popleft()

    # 오른쪽
    for j in range(i+1, n-i-1):
        new_board[j][m-i-1] = q.popleft()
    # 아래쪽
    for j in range(m-i-1, i-1, -1):
        new_board[n-i-1][j] = q.popleft()

    for j in range(n-i-2, i, -1):  # 왼쪽
        new_board[j][i] = q.popleft()

for row in new_board:
    print(*row)

"""
[입력]
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
"""

"""
[출력]
3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14
"""

16926번과 16927번의 문제가 동일하여 같은 풀이로 제출하면 되는데

앞의것은 실버레벨이고 뒤의것은 골드레벨인것을 보아, 16926번을 풀때 deque를 활용하지 않고 순수 배열 처리로만 했을때 풀리더라도 같은 풀이로 16927번을 풀었을때 타임아웃이 나지 않을까 싶다.

제한 조건을 보면 16926은 R의 값이 최대 1000 이지만 16927은 최대 10**9 값을 가질수 있다.

위 풀이로는 두 문제 전부 python3으로 체점하여 통과 가능하다.

우리회사에서는 유저의 행동기록을 남기고 있다. 상품에 대한 처리, 주문에 대한 처리, 유저가 활동한 기록들 등..

이런 기록들이 서비스 오픈 이후로 별다른 정리조치 없이 꾸준히 쌓이고 있는데,

아무래도 서비스 운영기간이 늘어날수록 db용량이 늘어나는건 당연한 수순이지만, aws 비용 줄이기를 하고 있는 요즘

mongodb의 ec2 용량마저 줄이기 위해서 데이터 정리를 하게 되었다.

1. 현재 가용중인 mongodb의 ec2 용량 확인하기.

회사 mongodb는 aws의 ec2에 서버를 띄워 사용하고 있다. 그리고 EBS로 EC2의 용량을 지정해 두었다.

amazonEBS는 AWS 클라우드의 EC2 인스턴스에 사용할 영구 블록 스토리지 볼륨을 제공한다.
각 EBS 볼륨은 가용 영역 내에 자동으로 복제되어 구성요소 장애로부터 보호해주고 고가용성 및 내구성을 제공한다.

현재 설정된 mongodb EC2의 EBS 볼륨은 310GiB 이다.

왜 primary랑 secondary가 다르냐면... 바로 얼마전에 300GiB 에서 DB에 OOM이 발생하였기 때문이다 ㅎ

200GiB에서 올린지 1년도 채 되지 않았는데 그 사이에 유저들의 활동량이 폭발적으로 늘어나면서 금방 용량이 꽉 찬듯 하다.

이때 급해서 primary만 먼저 10GiB 정도 올리고 동시에 불필요한 히스토리 데이터를 삭제작업 하면서 최종적으로 가용중인 용량은 310GiB중 267GiB 이다.

+) ec2 mongodb 용량 확인하기 : df -h

[ec2-user@ip-**** ~]$ df -h
Filesystem      Size  Used Avail Use% Mounted on
/dev/nvme0n1p1  310G  267G   44G  87% /

미리 체크하면서 데이터 정리 했으면 안늘려도 됐겠군....ㅎ 그치만 데이터 정리에 대한 정책이 아예 없었었다!!!!!!!!!!!!!

이후 데이터 정리에 대한 여러번의.. 지시가 내려오면서... 다양한 기준으로 데이터 정리를 하기 시작했다.

- 장기 미접속 유저의 데이터 삭제...

- 탈퇴유저의 즉시 데이터 삭제..

그리고 이번에 작업한 "1년지난 히스토리 데이터 삭제" 이다.

2. 데이터 삭제하기

+) index 걸기

데이터 삭제를 위해서 기준값을 갖고 delete를 해주는데, 이때 잡은 기준값 key에 index가 몇개 collection엔 없었다.

일단 해~ 하면서 삭제프로세스를 시작했고 예상되는 소요시간 120시간 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

바로 중단 후 index 작업을 해주었다.

그리고 나서 걸린 시간 2시간! 새로운 collection를 구상할땐 index 꼭좀 걸어주세용... 뒤늦게 걸려니 영...

데이터 삭제 후 다시 가용용량을 확인해 봤는데 용량이 전혀 줄지 않았다! 띠용..

이는 "mongodb에서 삭제된 데이터에 대한 디스크 용량을 즉시 반환하지 않기 때문" 이다.

데이터를 삭제한 이유가 용량확보를 위한 것이므로 즉시 용량을 확보해주면 된다.

3. 용량 확보하기 : compact

+ collection lock 확인

mongodb에서 용량을 확보하는 명령어는 compact 이다.

해당 명령어 사용시 collection에 lock은 걸리지 않지만 가장 안전한 방법으로는

- 현재 사용중인 db와 를 복제..

- 데이터 마이그레이션 ..

이렇게 하는거라고 하는데 몇천만개의 데이터를 마이그레이션 하려면 거진 하루정도는 서비스를 내려야 하지 않나 싶다 ㅎ

아니면 내리지 않고 ... 어.. 음.. 마이그레이션 하는동안 생성된 데이터를 임시보관 해뒀다가 마이그레이션 한 뒤 다시 insert 해주는...? 어우.. 이게 맞나..? 무튼 복잡하다!

당장의 용량확보가 최우선순위였고, 삭제된 데이터는 운영하는데 아무런 지장이 없는 데이터이므로 운영환경에서 compact 해주기로 한다.

먼저 ec2의 mongodb 로 접속한다. 그리고 다시한번 용량 확인

[ec2-user@ip-*** ~]$ ssh 운영환경 ec2
       __|  __|_  )
       _|  (     /   Amazon Linux 2 AMI
      ___|\___|___|
[ec2-user@ip-*** ~]$ ssh mongo
Last login: ~~~

       __|  __|_  )
       _|  (     /   Amazon Linux 2 AMI
      ___|\___|___|
[ec2-user@ip-*** ~]$ df -h
Filesystem      Size  Used Avail Use% Mounted on
/dev/nvme0n1p1  310G  267G   44G  87% /

이후 mongodb shell 을 열어준다.

[ec2-user@ip-*** ~]$ mongo
MongoDB shell version v5.0.13
connecting to: mongodb://127.0.0.1:27017/? ~~~~~~
================
... 안내문 생략 ...
================
replica:PRIMARY>

db가 replica set 설정이 되어있어 primary 로 연결되었다.

+) compact 명령어 실행 권한 에러

compact 명령어는 db의 관리자가 수행할수있는 명령어이다. 관리자 권한이 아닌 상태에서 명령어 실행시 에러가 발생한다.

replica:PRIMARY> db.runCommand( {compact : '{target Collection}', force : true} )
{
	"ok" : 0,
	"errmsg" : "command compact requires authentication",
	"code" : 13,
	"codeName" : "Unauthorized",
	"$clusterTime" : {
		"clusterTime" : Timestamp(~~~, ~~),
		"signature" : {
			"hash" : BinData(0,"~~~"),
			"keyId" : NumberLong("~~")
		}
	},
	"operationTime" : Timestamp(~~~, ~~)
}

때문에 대상 db로 들어가 관리자로 접속후 진행해야 한다.

현재 관리자 user 생성된게 없어서 먼저 생성부터 해준다. shell 에서 생성해주려나 authentication error 가 발생하는데 이부분은 어떻게 생성하는지 방법을 몰라서 mongodb tool 에서 해당 db의 users 항목에서 add 해주었다.

db.createUser(
   {
     user: "dbAdmin", pwd: "password", roles: [{"role":"dbAdmin","db":"targetDB"}]
   }
)

이후 다시 mongo shell 에서 어드민 권한을 사용해 compact를 수행하준다.

replica:PRIMARY> use {작업할 DB명 : 이하 targetDB}
switched to db targetDB
replica:PRIMARY> db.auth('dbAdmin123123', 'password')
Error: Authentication failed.
0  # 접속 실패
replica:PRIMARY> db.auth('dbAdmin', 'password')
1  # 접속 성공

1 이 나오면 관리자 권한으로 연결됐단 뜻이다.

이후 compact 명령어를 실행해준다. 시간이 오래 걸릴 경우 shell 이 멈춘것처럼 보이는데 이때 다른 터미널을 열어서 mongo 용량을 확인해보면 실시간으로 용량이 줄어드는걸 볼 수 있다 ㅎㅎ

replica:PRIMARY> db.runCommand( {compact : '{target Collection}', force : true} )
{
	"bytesFreed" : ******,
	"ok" : 1,
	"$clusterTime" : {
		"clusterTime" : Timestamp(***, *),
		"signature" : {
			"hash" : BinData(0,"******"),
			"keyId" : NumberLong("******")
		}
	},
	"operationTime" : Timestamp(***, *)
}
# 작업 후 db 용량
Filesystem      Size  Used Avail Use% Mounted on
/dev/nvme0n1p1  310G  266G   45G  86% /

 1 기가 줄었군......................

이후로도 계속 작업을 진행해준다. 보다 상세한 비교를 위해 compact 수행 전 collection의 stats를 확인해보고 명령어 실행 이후와 함께 비교해 보았다.

확인 할 부분은 "storageSize" 이다. 데이터를 삭제하기 전과 용량이 동일하게 잡혀있다.

compact 명령어 실행 이후는 아래와 같다.

7.5GiB 로 용량이 줄어들었다!

전체 db 용량도 확인해보니 259GiB로 확인된다.

[ec2-user@ip-*** ~]$ df -h
Filesystem      Size  Used Avail Use% Mounted on
/dev/nvme0n1p1  310G  259G   52G  84% /

임무 완료!

입력값 처리

python에서 sys 가 있다면 java에서는 import java.util.Scanner 가 있다.
이때 Scanncer는 InputStream을 생성자로 입력받는데, 입력하는 곳이 어디냐에 따라 그 값을 넣어주면 된다.

[1] 입력 방식의 차이

1-1) 키보드에서 입력받기 : System.in

키보드에서의 입력을 받으려면 System.in의 InputStream 을 넘겨주면 된다.

import java.util.Scanner

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
    }
}

1-2) 변수에서 입력받기 : 변수명

키보드에서의 입력을 받으려면 System.in의 InputStream 을 넘겨주면 된다.

import java.util.Scanner

public class Main {
    public static void main(String[] args) {
        String ex = "2 apple";
        Scanner sc = new Scanner(ex);
    }
}

1-3) 외부 파일에서 입력받기 : new File()

import java.util.Scanner

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(new File({파일명}));
    }
}

2) 타입에 따라 입력받기

파이썬 처럼 입력받을때 타입을 지정할 수 있다.

import java.util.Scanner

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // int 형으로 입력받기 : Short(), Long(), Double(), Float() 도 가능하다.
        int input_int = sc.nextInt();

        // 문자로 입력받기
        String input_str = sc.next();
        // 문자를 '줄' 단위로 입력받기
        String input_str = sc.nextLine();
    }
}

이때 next() 와 nextInt() 는 모두 기본적으로 공백을 구분자 로 하여 한개 단어씩만 입력받는다.

public class Main {
    public static void main(String[] args) {
        String ex = "2 apple";
        Scanner sc = new Scanner(ex);

        int input_int = sc.nextInt(); // 2   
        String input_str = sc.next();  // apple

        System.out.println(input_int+input_srt);
    }
}
>>> 2apple

3) 구분자로 입력받기

3-1) 한줄로 입력

한줄에 구분자를 두고 여러값을 입력받는 경우도 있다.

3
1 6 7

이런식의 입력예제는 알고리즘 문제에서 많이 볼수 있었다. nextLine()을 통해 개행문자로 구분되기 전 한줄의 값을 모두 읽어올 수 있다.

public class Main {
    public static void main(String[] args) {
        String ex = "2 apple";
        Scanner sc = new Scanner(ex);

        String input_line = sc.nextLine();        
        System.out.println(input_line);
    }
}
>>> 2 apple

3-2) 입력받은 문자열을 공백을 기준으로 리스트로 담기

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("공백으로 구분된 문자열을 입력하세요:");
        String input = scanner.nextLine();

        // 입력된 문자열을 공백으로 분리하여 배열로 저장
        String[] tokens = input.split("\\s+");
    }
}

이때 배열상태인 tokens를 바로 출력하면 배열이 저장된 데이터의 주소값 이 출력된다. 이를 문자로 출력하기 위해선 Arrays.toString() 메소드를 이용해 배열을 문자열로 변환한 후에 출력해야 한다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("공백으로 구분된 문자열을 입력하세요:");
        String input = scanner.nextLine();

        // 입력된 문자열을 공백으로 분리하여 배열로 저장
        String[] tokens = input.split("\\s+");

        // 배열을 리스트로 변환
        List<String> list = Arrays.asList(tokens);

        // 리스트 출력 (테스트용)
        System.out.println("리스트: " + list);
    }
}

3-3) 입력받은 한줄을 숫자형 리스트로 만들기

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("공백으로 구분된 숫자를 입력하세요:");
        List<Integer> numbers = new ArrayList<>();

        while (scanner.hasNextInt()) {
            numbers.add(scanner.nextInt());
        }

        // 숫자 리스트 출력
        System.out.println("입력된 숫자: " + numbers);
    }
}

이때 nextLine() 처럼 한줄을 한번에 읽고, 그 후에 처리하는 방법은 아래와 같다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("공백으로 구분된 숫자를 한 줄에 입력하세요:");
        String input = scanner.nextLine();

        // 입력된 문자열을 공백으로 분리하여 숫자로 변환하여 리스트에 저장
        List<Integer> numbers = new ArrayList<>();
        String[] tokens = input.split("\\s+");
        for (String token : tokens) {
            numbers.add(Integer.parseInt(token));
        }

        // 숫자 리스트 출력
        System.out.println("입력된 숫자: " + numbers);
    }
}

처음에 해메었던 부분들이 있었다.

이유는 구간의 총 합이 100m 로 고정되어있다는 걸 간과한채 미지의 수가 들어오면.. 하면서 복잡하게 생각하느라 로직이 꼬였던듯 하다.

일반 tc는 통과했지만 히든tc에서 오답처리되어 0점...!!

다시 문제를 확인했고 접근방식을 변경했다.

[1] 내 풀이 : 모든 구간의 속도 차이 비교 (단, 과속일때만 기록)

비교해야 할 구간이 100m 까지이고, 단위가 1m 이므로 모든 구간을 비교해도 괜찮겠다 싶었다.

- step1

이것이 가능한 이유는 구간이 100m 로 비교적 짧게 고정되어있기 때문이다. 이 방식은 구간이 미지수에 매우 범위가 크다면 시간제한이슈로 사용하지 못할 듯 하다.

- step2

0부터 100까지 index 를 사용해 stand_all 과 test_all 의 각 값을 비교한다. 이때 test_all-stand_all 값이 0보다 커야 테스트 중에 과속했다는 것을 의미하므로 그 값만 diff_list 에 담아준다.

- step3

만약 diff_list 에 아무갑솓 안담겨있다면 이는 저속 주행 혹은 정속 주행만 했음 을 의미한다. 따라서 조건에 맞게 0 을 반환한다.
이와 달리 diff_list에 유효한 값이 있다면 이중 가장 큰 값을 출력한다. 이것이 가장 큰 차이가 나는 과속 범위를 뜻한다.

내 풀이가 사용 가능했던 이유는 앞서 말했든 비교범위가 작게, 고정되어있기 때문이다. 실제로 이 방식으로 문제를 풀었을때 평균 0.1 초의 풀이시간이 나온걸 확인할 수 있었다.

만약 범위가 아주아주 크다면 모든 구간을 비교하는것은 사용하지 못할 듯 싶다. 최대한 비교횟수를 줄이기 위해 속도 차이가 나는 구간 마다의 기록 방식을 생각했지만 구현이 잘 안되어 다른 사람들의 풀이를 참고하였다.

[2] 추가 풀이 : 속도가 변하는 구간 값만 확인하기 (deque 활용 가능)

- step 1

구간별 속도를 기록한다. 이중배열속 0번 index는 구간을, 1번 index는 해당 구간의 속도를 뜻한다. 모든 0번 index값을 더하면 주어진 구간인 100이 나온다.

- step 2

약간 queue같은.. 모양인데 정말로 Python의 deque 를 사용해도 될것 같다. 배열보다 pop 하는 효율이 더 좋다고 하니...

기준 과 테스트 의 가장 첫 구간을 비교하여 구간길이의 차는 항상 테스트구간을 기준 으로 한다.

두 구간의 속도 차를 비교하여 해당 값이 0 보다 크다면 모든 속도차이를 비교한 배열에 append 한다. 0이면 정속 주행이고, 음수값이면 저속 주행이므로 배열에 담을 필요가 없다.

• 2-1 : 구간 차 가 양수" 라면 테스트 구간이 더 길다는 뜻이다. 때문에 남은 구간을 "테스트 list"의 0번째 인덱스에 다시 넣어준다. 속도비교도 하므로 속도값은 검사한 테스트 구간 값 그대로 넣어준다.
• 2-2 : 구간 차 가 "음수"라면 기준 구간이 더 길다는 뜻이다. 때문에 남은 구간을 "기준 list"의 0번째 인덱스에 다시 넣어주어야 하는데 이때 값 diff_len 은 음수이므로 절대값 처리 하여 넣어준다. 속도비교도 하므로 속도값은 검사한 기준 구간 값 그대로 넣어준다.

- step 3

모든 과속 데이터가 담긴 배열을 확인하여 조건에 맞게 답을 출력한다. 데이터가 없다면 0을, 데이터가 있다면 그중 가장 많이 과속한 max값을 출력한다.

1. 자료형 초기 선언 두가지 방식 : 괄호 사용 or 내장 함수 사용

python 언어로 작업을 하면서 변수를 자료형의 초기상태로 선언할때 dictionary 는 중괄호 {} , list 는 대괗로 [] 로 표현했었다. 어느순간 작업하면서 얇은 괄호가 눈에 잘 띄지 않는 듯 하여 내장함수를 사용한 적도 있었다.
또한 python에서는 함수의 리턴 type을 명시할때도

def some_function() -> dict:
    ...

이런식으로 자료형의 "이름" 을 직접 명시하다 보니 자료형의 이름이 보이는것이 통일되게끔 작업한거 같기도 하다.
한개 함수는 항상 같은 자료형을 return 하는것이 좋기 때문에 조건에 맞는 데이터가 없어서 return 할 값이 없다 하더라도 None을 반환하지 않고 초기 자료형을 반환하도록 작업한다. 때문에 return 될 변수는 함수 첫 부분에 초기상태로 선언해둔다.

def some_function(a) -> dict:
    res = {} # 혹은 res = dict()
    if type(a) == int:
        res["type"] = "int"
    return res

만약 return 변수 res 를 초기에 선언하지 않았다면 if 문 안에서 res 변수를 선언하는 동시에 값을 담아 return 하고, if 문 바깥쪽에 예외상황의 return 을 선언해 주면 되긴 하다

def some_function(a) -> dict:
    res = {} # 혹은 res = dict()
    if type(a) == int:
        res = {"type": "int"}  # 혹은 res = dict(type='int')
        return res
    return {} # 혹은 return dict()

하지만 조건문이 여러개가 되고, 코드가 복잡해지면 return 이 빠지는 곳이 있을수 있어 모든 조건을 확인 한 후 마지막에 return 하는 방식으로 작업한다. 이때는, 딕셔너리 타입의 변수 res를 선언할때 res={} 이나 res=dict() 이 어떠한 차이가 있는줄 정확히 이해하지 못하였었다.

# 괄호를 이용하기

dict_var = {}
list_var = []
------------------------------
>>> print(dict_var, type(dict_var))
{} <class 'dict'>
>>> print(list_var, type(list_var))
[] <class 'list'>

# 내장함수 이용하기

dict_var2 = dict()
list_var2 = list()
------------------------------
>>> print(dict_var2, type(dict_var2))
{} <class 'dict'>
>>> print(list_var2, type(list_var2))
[] <class 'list'>

출력 결과를 보나, 타입을 보나 둘다 차이가 없어보인다. 하지만 python 의 timedit를 사용해 두가지의 변수 선언 방식의 시간 효율을 따져보니 차이가 발견되었다.

2. 선언 방식에 따른 실행 속도의 차이 : timeit

timeit 은 python에서 제공해주는 모듈로 timeit 이후의 명령어를 실행하는데 걸리는 시간을 확인해준다.

timeit.timeit(stmt='pass', setup='pass', timer=<default timer>, number=1000000, globals=None)

stmt 은 timeit 으로 측정할 코드 및 함수 주체이며, setup stmt에 선언된 코드 및 함수를 실행하기 위해 필요한 사전 함수이다. 이때 실행속도 측정에 setup의 시간은 포함되지 않는다.
timer 함수로 Timer 인스턴스를 만드는데 default 값이 지정되어 있으며, number 실행으로 timeit() 메서드를 실행한다.
이때 number 인자도 default 값으로 10000000 이 지정된다. 또한 비필수 인자인 globals 는 코드를 실행할 이름 공간을 지정한다.

위 모듈을 통해 변수 초기선언 방식인 dict()와 {}의 속도차이를 확인해 보았다.

~ > python -m timeit "dict()"
10000000 loops, best of 3: 0.0451 usec per loop
~ > python -m timeit "{}"
100000000 loops, best of 3: 0.0115 usec per loop

단순 빈 자료형 선언인데도 속도가 무려 4배 넘게 차이가 났다.
그렇다면 변수를 초기 선언하면서 값을 세팅할때는 얼마나 나는지 1개 key-value 를 담아서 확인해보았다.

~ > python -m timeit "dict(fruit='apple')"
10000000 loops, best of 3: 0.0806 usec per loop
~ > python -m timeit "{'fruit': 'apple'}"
10000000 loops, best of 3: 0.0263 usec per loop

위 상황보다는 덜 나지만 비슷하게 4배정도 차이가 나는걸 확인할 수 있었다.

0.03초 차이가 크지 않아 보이지만 프로그래밍에서는 굉장한 차이를 의미한다.

따라서 변수를 선언할 때에도 이런 유의미한 차이를 이해하고 작성하면 조금더 효율적인 코드를 작성 할 수 있을 것이다.