개발자 아지트

import heapq

n, m = map(int, input().split())
tmp = list(map(int, input().split()))

heapq.heapify(tmp)

for i in range(m):
    # 최소값 두 개 꺼내기
    smallest1 = heapq.heappop(tmp)
    smallest2 = heapq.heappop(tmp)
    
    # 두 값을 합친 후 다시 삽입
    summ = smallest1 + smallest2
    heapq.heappush(tmp, summ)
    heapq.heappush(tmp, summ)
    
print(sum(tmp))

이를 이해하기 최소힙을 이해하기 좋은 백준 문제 

: 15903 카드 합체 놀이(https://www.acmicpc.net/problem/15903)

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

문제 해결 방법

파이썬에서는 힙 자료구조를 heapq 를 통해 제공한다. 이때 최소힙 기능만 사용할 수 있고, 최대힙 기능은 지원하지 않는다. 

최소값일 수록 우선순위를 가지고 맨 앞에 배치되니, 최대 힙을 사용하고 싶으면 값들을 넣을 때 -를 붙여 넣고, 출력할때는 -를 달아서 출력하면 최대힙 처럼 사용할 수 있다. 

코드 구현

정답 코드 

'''
# 최대 힙
'''
import heapq
import sys
input = sys.stdin.readline
n = int(input())

tmp = []
for i in range(n):
    value = int(input())
    if value !=0:
        heapq.heappush(tmp, -value)
    else:
        if not tmp:
            print(0)
        else:
            print(-heapq.heappop(tmp))

시간/공간 복잡도

log(n)

어려웠던 점

알게된 점

• heapq 모듈 사용방법 

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

문제 해결 방법

이 문제는 문제 설명에 올라와있는대로 그대로 풀면 된다. 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

다만 문제는 반시계 방향으로 90도씩 회전을 해야한다는 것이고, 

현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 발견되는 즉시!! 반시계 방향으로 90도 회전해야한다. 

코드 구현

정답 코드 

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
startY, startX, dir = map(int, input().split())
mapp = []
for i in range(n):
    mapp.append(list(map(int, input().split())))

dx=[0, -1, 0, 1] # 북 서 남 동
dy=[-1, 0, 1, 0] # 북쪽을 y, x 기준 1, 0으로 표기해서 틀렸음 ....... 정신차려!! 

def solutions(x, y, dir):
    cnt = 0 # 청소하는 칸의 개수 
    while 1:
        # 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
        if mapp[y][x] == 0:
            mapp[y][x]=9
            cnt+=1

        check = 0 # 주변 4칸이 모두 청소된 칸인지 확인용 1은 청소필요, 1은 청소 불필요 
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
        
            if mapp[ny][nx]==0:
                #청소 필요한 칸 발견
                check =1
                break
            
        if check == 1:
            # 반시계 방향으로 90도 회전
            dir=dir+1
            if dir==4:
                dir = 0
            sx=x+dx[dir]
            sy=y+dy[dir]
            
            if mapp[sy][sx]==0:
                # 전진함 
                x = sx
                y = sy
        
        # 청소가 필요 없는 경우 
        if check ==0:
            nny = y-dy[dir]
            nnx = x-dx[dir]
            
            if mapp[nny][nnx]==1:
                return cnt
            else:
                x=nnx
                y=nny

if dir ==1:
    dir = 3
elif dir ==2:
    dir =2
elif dir == 3:
    dir = 1
print(solutions(startX, startY, dir))

시간/공간 복잡도

시뮬레이션 문제라 고려하지 않았다. 

어려웠던 점

• 반시계 반향으로 회전하려면, 문제에서 제시한 방향 기준으로 델타 x, y의 배열을 미리 선언할 때 조심해야 한다. 
• 우측 상단 방향이 행, 열 값이 증가하는 상황이라면  북쪽 방향으로 가는것이 (1, 0)이겠지만 해당 문제의 경우, 우측 하단으로 가야 행, 열이 값이 증가하는 상황이다. 이런 경우 북쪽으로 가는 것은 (-1, 0)이다.

알게된 점

• 좌표 문제의 경우, 쪽이 행과 열을 증가시키는 쪽인지 잘 확인하고 이를 고려하여 문제를 풀어야한다. 
• 델타 x, y좌표 배열을 선언할 때도, 문제에서 관련 조건이나 방법을 제시하는지 잘 확인하여 선언해야 한다. 

재귀 함수란?

: 재귀 함수는 자기 자신을 호출하여 원래 문제에 속한 더 작은 하위 문제를 해결하는 함수이다.

이를 통해 문제를 반복적으로 분해하다가, 더 이상 분해할 수 없는 기본 조건(base condition)에 도달하면 함수 호출을 종료한다. 

재귀 함수의 장점과 단점은 무엇인가?

 장점

• 코드가 반복적인 구조를 가진 문제(예: 특정 패턴의 탐색)를 간결하게 작성할 수 있습니다.
• 문제를 작게 나누어 해결하는 경우 구현이 상대적으로 단순해집니다.

단점

• 잘못된 구현이나 불필요한 깊이의 호출이 발생하면 성능이 저하될 수 있습니다.
• 깊은 재귀 호출로 인해 프로그램이 강제 종료될 가능성도 있습니다.

 재귀 함수에서 재귀 깊이를 줄이기 위한 방법

재귀 함수는 깊이(호출의 반복 횟수)가 깊어질수록 성능에 악영향을 줄 수 있다.

이때, 재귀 깊이를 줄이기 위한 몇 가지 방법을 사용할 수 있다.

메모제이션(Memoization)
이전에 계산한 값을 저장해 두었다가 재사용하는 기법이다.

이를 통해 동일한 계산을 여러 번 반복하지 않게 되어 재귀 호출 횟수를 줄일 수 있다.

memo = {}
def fibonacci(n):
   if n in memo:
       return memo[n]
   if n <= 1:
       return n
   memo[n] = fibonacci(n-1) + fibonacci(n-2)
   return memo[n]

반복문으로 변환
재귀로 풀 수 있는 문제는 대부분 반복문을 통해 해결할 수도 있다.

반복문으로 변환할 경우, 재귀 함수 호출로 인한 추가적인 메모리 사용을 방지할 수 있다.

 def fibonacci_iterative(n):
       a, b = 0, 1
       for _ in range(n):
           a, b = b, a + b
       return a

최적화된 종료 조건 설정
재귀 호출의 종료 조건을 잘 설정하면 불필요한 깊은 호출을 방지할 수 있다.

특히, 매번 상태를 변경하거나 갱신하여 기본 조건에 빨리 도달하도록 설계해야 한다.

재귀 함수를 구현하는 절차

1. 기본 조건 설정 (Base Condition):

기본 조건은 재귀 호출이 끝나야 할 시점을 정의하는 것이다.

만약 기본 조건이 없다면, 함수가 계속해서 자기 자신을 호출하여 무한 루프에 빠지게 되고, 결국 스택 오버플로우 오류를 발생시킨다.

기본 조건은 문제의 가장 작은 단위를 처리하는 코드로 작성해야 하며, 일반적으로 재귀 호출의 종료를 의미합니다. 

2. 더 작은 문제로 분할:

재귀의 핵심은 문제를 작은 문제로 나누는 것이다. 원래 문제를 더 작은 하위 문제로 분할함으로써, 최종적으로 기본 조건에 도달할 수 있다. 하위 문제는 원래 문제와 동일한 성질을 가져야 한다. 이렇기 때문에 재귀 호출이 문제를 반복적으로 해결할 수 있게 되는 것이다. 

또한 각 재귀 호출에서 문제의 크기를 줄여야 한다는 것이다. 만약 문제의 크기가 줄어들지 않으면, 기본 조건에 도달할 수 없게 되어 함수가 계속해서 호출되는 문제가 발생한다.

3. 재귀 호출:

마지막 단계는 재귀적으로 자기 자신을 호출하는 것이다. 이때, 더 작은 문제를 해결하기 위해 동일한 함수를 호출하게 된다. 재귀 호출은 기본 조건에 도달할 때까지 계속되며, 기본 조건에 도달하면 결과가 반환되기 시작한다.

이 과정에서 주의할 점은, 함수가 재귀 호출을 할 때마다 상태가 변화해야 한다는 것이다. 그렇지 않으면 문제의 크기가 줄어들지 않아 무한 루프에 빠질 수 있다.

재귀 함수 구현 시 주의해야 할 점

1. 기본 조건을 확실하게 설정해야 한다.
2. 재귀 깊이 고려해야 한다. 

재귀 호출은 호출할 때마다 메모리의 스택 공간을 사용한다. 따라서 재귀 호출이 너무 깊어지면 메모리가 부족해질 수 있다. 특히, Python에서는 재귀 깊이가 기본적으로 제한되어 있어, 그 한도를 넘어서면 RecursionError가 발생한다.

따라서 재귀 깊이를 고려하여 설계해야 하며, 가능한 경우 반복문을 통해 문제를 해결하는 방법도 고려해야 합니다. 혹은 sys.setrecursionlimit() 함수를 사용해 최대 재귀 깊이를 조정할 수 있습니다.

import sys

# 재귀 깊이 제한을 늘리기
sys.setrecursionlimit(2000)

그러나 이 방법은 메모리 사용량을 늘리기 때문에 신중히 사용해야 한다.

3. 반복적 재계산을 방지해야한다. 
많은 재귀 함수에서 동일한 하위 문제를 여러 번 계산하는 경우가 발생할 수 있다. 이로 인해 중복 계산이 일어나고 성능이 크게 저하될 수 있다. 이를 방지하기 위해 메모이제이션(Memoization)을 사용하여 이미 계산된 값을 저장하고 재사용하는 방법을 고려해야 한다.

출처: "코딩 테스트 합격자 되기-박경록" 

7-1. 큐의 개념

큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 

일상생활에서 줄 서는 것이 큐 구조이다. 먼저 선 사람이 먼저 들어간다. 

이런 큐의 특징을 선입선출, FIFO(First in First out) 이라고 한다. 

큐도 스택처럼 꺼내는 연산을 팝, 삽입하는 연산을 푸시라고 한다. 

*큐의 특성을 활용하는 분야 

큐의 동작 방식은 프로그래밍 언어에서 많이 활용된다. 대표적으로 여러 이벤트가 발생했을때 발생한 순서대로 처리가 필요할 때 큐가 활용된다. 작업 대기열이나 이벤트 처리의 경우 큐 구조로 처리된다. 

큐의 ADT(abstract data type, 추상자료형)

*연산

*상태

front는 큐의 앞, rear는 큐의 뒤를 의미한다. 

큐는 앞에서 데이터를 꺼내고(팝), 뒤에서 데이터를 넣으므로(푸시) 이렇게 앞 뒤의 최종 데이터의 위치를 기억해야한다. 

초기에는 front와 rear모두 초깃값을 -1로 설정한다. 

*큐의 세부동작 이해하기 

푸시 연산 

1. isFull() 연산을 통해 현재 큐가 가득 찼는지 확인한다. 

2. 큐가 가득 차지 않았다면, rear을 +1 하고 다음 rear가 가리키는 위치에 값을 푸시한다. 

팝 연산

1. isEmpty() 연산을 통해 큐가 비었는지 확인한다. 해당 연산을 통해 front, rear의 값이 같은지 확인해서 큐에 원소가 없는데 팝하는 동작을 방지한다. 

2. 만약 큐가 비어있지 않다면 front을 +1 한다. 이렇게 하면 front, rear가 0으로 같아지고, 

3. isEmpty() 연산 시 큐가 빈것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있다. 

front의 다음 부터 rear까지만 큐가 관리하는 데이터라고 생각해야 한다. 

이런식으로 큐를 관리하다보면, 실제 data 공간에 비해 큐가 관리하는 데이터가 줄어들게 되면 메모리 공간을 낭비한 상황을 만날 수 있다. 이렇게 된 이유는 큐를 한 방향으로 관리하기 때문이다. 이렇게하면, fornt 이전의 부분을 활용할 수 없게된다. 

이를 개선하기 위해 원형 큐를 사용한다. 

코딩테스트에서 파이썬을 사용하면 그냥 리스트만 사용해도 충분하게 이런 형태들의 큐를 사용할 수 있다. 

* 큐 구현하기 

큐를 간단하게 구현하는 방식은 크게 2가지가 있다. 

1. 리스트를 활용하는 방식

queue = []

# 큐에 데이터 추가
queue.append(1)
queue.append(2)

# 큐의 맨 앞 데이터 제거, 스택과의 차이는 pop()에 인수로 0을 넣어 맨 앞 데이터를 제거했다는 점이다
first_item = queue.pop(0)
print(first_item) # 출력: 1

2. 덱을 활용하는 방식

from collections import deque

queue = deque()

# 큐에 데이터 추가 
queue.append(1)
queue.append(2)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_item) # 출력: 1

실제로 큐를 구현할 때 덱을 사용하는 이유는 속도 때문이다. 

pop(0)을 10 만번하면 0.79초가 소요되고,

popleft()를 10 만번하면 0.007초로 매우 크게 차이가 난다. 

[문제]

1. 큐를 이용하여 주어진 데이터를 순차적으로 처리하는 알고리즘을 설계하고 구현하세요. 이 알고리즘의 시간 복잡도는 어떻게 되나요? 큐를 사용하지 않고도 데이터를 순차적으로 처리할 수 있는 다른 방법을 설명하세요.

=>

from collections import deque

queue = deque()

# cnt를 인덱스 삼아 순회 
cnt = 0
while queue:
	print(queue[cnt])
	# value = queue[cnt].popleft() # 팝 코드
    	# queue.append(value) # 푸시 코드

이 알고리즘의 시간 복잡도는 큐의 원소 개수가 n이라고 하면, O(N)이다. 

큐를 사용하지 않고도 데이터를 순차적으로 처리할 수 있는 다른 방법은 배열을 순회하여 순차적으로 처리하는 방법이 있다. 

2. 주어진 문자열에서 연속된 중복된 문자를 제거한 새로운 문자열을 반환하는 알고리즘을 설계하고 구현하세요. 단, 문자열 내에서 문자의 순서는 유지해야 합니다. 시간 복잡도를 분석하세요.

=> 

from collections import deque

test = 'aaappllee'
test = deque(test)
newT=[]

for i in range(len(test)):
        if not newT or newT[-1] != test[i]:
            newT.append(test[i])
print(newT)


#=> 이렇게 시도했더니 문자열 순서가 안맞는 문제가 있음
# check = 0
# ok = 0
# cnt = 0
# while 1:
#     if check == 0:
#         value = test.popleft()
#         rem = value
#         test.append(value)
#         check =1
#     else:
#         if test:
#             value = test.popleft()
#             if value == rem:
#                 ok = 1
#                 pass
#             else:
#                 test.append(value)
#                 rem = value
#                 ok = 0
        
#     # cnt+=1
#     # if cnt == len(test):
#     #     break
#     print(test)

# print(test)

큐의 크기가 n이라면 O(n) 인 시간복잡도를 가지는 알고리즘이다. 

3. 큐와 스택의 차이점을 설명하고, 각각의 자료구조가 적합한 상황을 예시와 함께 설명해보세요. 두 자료구조의 시간 복잡도에 대한 일반적인 차이도 설명하세요.

=>

*큐와 스택의 차이점

      큐: 앞에서도 pop할 수 있다. (먼저 들어간 것을 pop 할 수 있다.) 

      스택: 앞에서는 pop할 수 없다. (먼저 들어간 것을 pop 할 수 있다.) 뒤에서부터 pop할 수 있다. 

*각각의 자료구조가 적합한 상황

*각각의 구조가 적합한 상황의 예시

* 두자료구조의 시간 복잡도에 대한 일반적인 차이

  두 자료구조의 시간 복잡도에 대한 일반적인 차이는 다음과 같은 경우에서 확인할 수 있다.

  스택이 맨 앞에서 원소를 꺼내려고 할때 O(N)의 시간복잡도가 걸리지만, 큐의 경우 O(1)의 시간복잡도가 걸린다. 

4. 큐를 이용하여 우선순위가 있는 작업을 처리하는 방법에 대해 설명하세요. 우선순위가 높은 작업을 먼저 처리할 수 있는 자료구조의 동작 원리와 그에 따른 시간 복잡도를 설명해보세요.

* 큐를 이용해 우선순위가 있는 작업을 처리하는 방법

이때, 우선순위 큐(Priority Queue)를 사용할 수 있다. 우선순위 큐는 각 작업에 우선순위를 부여하고, 우선순위에 따라 요소를 삽입하고  삭제 처리하는 자료구조이다. 

* 우선순위 큐의 동작 원리

우선순위 큐는 요소를 큐에 추가하거나, 가장 높은 우선순위를 가진 요소를 큐에서 제거하는 동작이 있다. 

이러한 동작을 수행하기 위해 완전 이진 트리 구조를 가진 자료 구조인 힙(Heap)을 사용한다. 

(완전 이진 트리 구조란? 모든 레벨이 완전히 채워져 있으면서, 마지막 레벨만 왼쪽부터 차례대로 노드가 채워진 형태)

*힙의 종류

힙은 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 최소 힙(Min Heap), 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 최대 힙(Max Heap)이 있다. 

우선 순위 큐에서 작업을 처리할 때는, 우선순위에 따라 요소가 정렬된다. 우선순위가 가장 높은 요소가 루트에 위치하게 된다. 

이후에 우선순위가 높은 요소가 먼저 처리된다. 

* 우선순위 큐의 시간 복잡도

힙 (Heap)이란?

힙은 이진 트리 기반의 자료구조로, 최소 힙 (Min-Heap)과 최대 힙 (Max-Heap)으로 나뉜다. 

• 최소 힙: 각 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 구조.
• 최대 힙: 각 부모 노드가 자식 노드보다 크거나 같은 값을 가지는 구조.

파이썬의 heapq 모듈은 기본적으로 최소 힙을 사용하며, heapify() 함수는 주어진 리스트를 이러한 힙 구조로 정렬한다. 

heapq.heapify()의 동작

heapify()는 주어진 리스트를 인덱스 0부터 힙의 조건에 맞게 재배치한다. 이때, 첫 번째 원소(인덱스 0)가 최소값을 가지도록 정렬된다.  힙은 완전 이진 트리의 성질을 가지기 때문에, heapify()의 시간 복잡도는 O(n)이다. 

사용 예시 

'''

우선순위 큐 구현

'''

import heapq

tasks = [(3, 'Task A'), (1, 'Task B'), (2, 'Task C'), (1, 'Task D')]

heapq.heapify(tasks)
result = [i[1] for i in tasks]


print(result)

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

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

문제 해결 방법

딕셔너리를 잘 활용하여 문제를 해결한다. 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dic = {}
revDic = {}
for i in range(n):
    tmpS = input().strip()
    dic[i+1]=tmpS
    revDic[tmpS]=i+1

for i in range(m):
    tmpV = input().strip()
    if tmpV.isdigit():
        tmpV= int(tmpV)
        print(dic[tmpV])
    else:
        print(revDic[tmpV])

시간/공간 복잡도

O(n)

어려웠던 점

• 자료구조 조회할 때, 시간초과를 해결하기 위해서는 리스트보다 해시테이블을 구조인 딕셔너리 사용(O(1)) 이 더 빠르기 때문에 효과적이다.  

알게된 점

• 키 값을 통해 값을 찾거나 밸류 값을 통해 값을 찾아야 하는 경우, 두개의 딕셔너리를 활용하면 아주 효율적이다. 
• 문자열이 숫자 값인지 확인할때, 대상.isdigit()함수를 사용하면 확인할 수 있다. (숫자일 경우 True 반환)

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

문제 해결 방법

재귀함수 혹은 DP를 활용한다. 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline
t = int(input())


def fibonacci(n, count):
    if n<=1:
        if n ==0:
            count[0]+=1
        if n==1:
            count[1]+=1

        print(count[0], count[1])
        return n
    
    a = 0
    b = 1

    for i in range(2, n+1):
        c = a + b
        a = b
        b = c


    print(a, b)
    return b 
        

for i in range(t):
    n = int(input())
    count = [0, 0]
    fibonacci(n, count)

# 0 1 1 2 3 5 8

시간/공간 복잡도

O(n)

최적화 및 개선

• 피보나치 함수 알고리즘을 구현할 때, 재귀함수로 구현후 시간 초과가 나면 DP로 구현하면 시간 복잡도를 줄일 수 있다. 

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

문제 해결 방법

리스트를 잘 활용하여 문제를 해결한다. 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline

n = int(input())
tmp = []
for i in range(n):
    entire = input().strip()
    if entire=='all': 
        tmp = list(range(1, 21))
    elif entire=='empty':
        tmp.clear()
    else:
        s, v = entire.split()
        v = int(v)
        if s == 'add':
            if v not in tmp:
                tmp.append(v)
        
        if s == 'check':
            if int(v) in tmp:
                print(1)
            else:
                print(0)
        
        if s == 'remove':
            if v in tmp:
                tmp.remove(v)
        
        if s == 'toggle':
            if int(v) in tmp:
                tmp.remove(v)
            else:
                tmp.append(v)

시간/공간 복잡도

O(n)

어려웠던 점

• 입력값의 타입에 대해 잘 고려하지 않아서 조건문이 제대로 실행되지 않았던 점
• sys모듈에서 input()함수를 사용할 때, 개행문자(/n)가 붙어서 조건문이 제대로 실행되지 않았던 점

느낀점

• sys모듈에서 input()함수를 사용할 때, 개행문자(/n)를 꼭 처리하여 문제를 해결해야겠다. 
• 변수 타입에 대해 잘 고려하고 문제를 풀어야겠다. 
• 리스트를 비우기 위해 대상.cleare() 함수를 사용하면 된다. 

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

문제 해결 방법

배추가 심긴 위치를 순회한다. 방문여부를 알 수 있는 visited 배열이 필요하다. 

좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다. 

이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 이때 지렁이의 개수를 +1 한다 

bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 심겨진배추가 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 값이 0이 아니고 방문한 적이 없으면 현재자리의 방문체크를 해준다.  

그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다. 

코드 구현

정답 코드 

import sys
from collections import deque
input=sys.stdin.readline

dx= [0, 0, 1, -1]
dy= [1, -1, 0, 0]

answer=[]
def bfs(y, x):
        queue = deque()
        visited[y][x] = True
        queue.append([y, x])

        while queue:
            ny, nx = queue.popleft()
            for ii in range(4):
                yy= ny+dy[ii]
                xx= nx+dx[ii]

                if 0<=yy<n and 0<=xx<m and mapp[yy][xx]==1 and  visited[yy][xx] == False:
                    visited[yy][xx] = True
                    queue.append([yy, xx])

t = int(input())
for j in range(t):
    m, n, k = map(int, input().split())
    mapp = [[0] * m for _ in range(n)]
    visited = [[False] * m for _ in range(n)]
    cnt = 0
    for i in range(k):
        wm, wn = map(int, input().split())
        mapp[wn][wm] = 1
    
    for ix in range(n):
        for jx in range(m):
            if mapp[ix][jx]==1 and visited[ix][jx] == False:
                    cnt+=1
                    bfs(ix, jx)
    answer.append(cnt)

for i in answer:
  print(i)

시간/공간 복잡도

따로 생각하지 않았다. 

최적화 및 개선

• 따로 하지않음

어려웠던 점

• BFS는 큐에 넣기 전에 방문처리를 해야 중복 방문처리를 하지 않게 된다는 것을 알게됐다. 

6-1. 스택 개념

스택은 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다. 

먼저 들어간 것이 마지막에 나오는 규칙을 선입후출, FILO(First In Last Out)이라고 한다. 

이때, 스택에 삽입하는 연산을 push, 빼는 연산을 pop이라고 한다. 

6-1. 스택의 정의

스택 자료형의 동작 형태를 설계하는 것은 추상 자료형(ADT)을 정의하는 것이다. 

추상 자료형ADT(abstract data type) 이란?

=> 인터페이스만 있고 실제 구현은 되지 않은 자료형

스택은 push, pop, 스택이 가득 찼는지 확인(isFull), 스택이 비었는지 확인isEmpty)과 같은 연산을 정의해야 한다. 

또한 스택에는 최근에 삽입한 데이터의 위치(현재 가리키는 인덱스)를 저장할 함수인 top도 있어야 한다. 

스택 구현하기

스택은 최근에 삽입한 데이터를 대상으로 뭔가 연산 해야 할 경우 적합. 

# 스택 ADT 구현

stack = [] #스택 리스트 초기화 
max_size = 10 # tmxordml 최대 크기 

def ifFull(stack):
    # 스택이 가득 찼는지 확인하는 함수 
    return len(stack) == max_size

def isEmpty(stack):
    # 스택이 비어있는지 확인하는 함수 
    return len(stack) == 0

def push(stack, item):
    # 스택에 데이터를 추가하는 함수
    if ifFull(stack):
        print("스택이 가득 찼다.") 
    else:
        stack.append(item)
        stack.append("데이터가 추가됐다. ")

def pop(stack):
    # 스택에서 데이터를 꺼내는 함수
    if isEmpty(stack):
        print("스택이 비었다. ")
        return None
    else:
        return stack.pop()

그러나 파이썬의 리스트는 크기를 동적으로 관리하기 때문에 max_size나 isFull(), isEmpty()함수는 따로 구현하지 않는다. 

코드의 push(), pop()함수는 기존의 원소 추가 함수append(), 원소 꺼내는 함수 pop()이 있기 때문에 따로 구현하지 않아도 된다. 

주의: 실전에서는 문제에 스택을 활용해야 풀 수 있다는 생각을 하지 못해서 문제를 풀지못하는 경우가 대부분임

따라서 스택 관련 문제를 많이 풀어보고, 해당 문제는 스택을 사용하면 좋겠다는 감을 익히는 것이 중요함

질문

1. 스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계하고 구현해 보세요. 이 알고리즘의 시간 복잡도와 공간 복잡도는 각각 어떻게 되나요? 스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법을 설명해 보세요.

답:

<스택을 이용하여 주어진 문자열을 뒤집는 알고리즘을 설계>

문자열의 길이가 n이라고 가정한다. 

1. 문자열의 문자를 임의의 리스트에 하나씩 넣는다. 

2. 빈 임의의 문자열 변수를 하나 선언한다. 

3. 임의의 리스트에서 pop()을 하여 꺼낸 값을 빈 임의의 문자열 변수에 + 연산을 하여 추가한다. 

3번은 문자열의 길이만큼 행한다. 

<위 알고리즘의 시간 및 공간 복잡도>

전체 시간복잡도 = 1번 과정에 대한 시간 복잡도 n + 3번 과정에 대한 시간복잡도 n^2 = O(n^2)

전체 공간 복잡도 = 문자열의 길이 n만큼 nbyte = O(n)

<스택을 사용하지 않고도 문자열을 뒤집을 수 있는 다른 방법>

파이썬의 슬라이스를 사용해 뒤집는 방법이 있다. 

2. 스택이 재귀적인 함수 호출과 어떻게 관련이 있는지 설명해 보세요. 재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법을 예시를 통해 설명할 수 있나요?

답:

<스택이 재귀적인 함수 호출과 어떻게 관련이 있는가?>

재귀적인 함수 호출은 함수 호출 조건을 5로 준다면, 첫번째로 함수를 호출 한것이 해당 함수를 두번째로 호출하게되고 두번째로 호출 한 함수에서 해당 함수를 세번째로 호출하게 되고 , , ,이런식으로 진행이 되다가 조건에 따라 추가적인 함수 호출을 하지않게 된다. 마지막으로 함수를 호출한 것이 실행되면서 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 네번째로 호출한 함수에서 다섯번째로 함수 호출한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다. 직전에 세번째로 호출한 함수에서 네번째로 함수 호출을 한 이후의 로직이 실행되고 실행이 끝나면 해당 함수는 처리가 완료되어 끝난다... 이렇게 첫번째 함수까지 처리되어 재귀 함수의 실행이 끝난다. 

이렇듯 재귀적인 함수의 호출은 스택의 LIFO(Last In, First Out) 원칙에 따라 진행되는 것을 알 수 있다. 

<재귀 함수를 스택을 사용하여 비재귀적으로 변환하는 방법과 그 예시>

비재귀적 방식이란 함수가 자기 자신을 호출하지 않고, 대신 반복문과 같은 구조를 사용해서 문제를 해결하는 방식이다. 

예를들면 대상인 피보나치 함수를 재귀로 구현하면 다음과 같다. 

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
print(fibonacci(3))

위 재귀 함수를 비재귀적 방식으로 다시 구현하면 다음과 같다. 

def fibonacci(n):
    if n <= 1:
        return n

    a = 0
    b = 1
    
    for i in range(2, n+1):
        c = a + b
        a = b
        b = c
    
    return b

print(fibonacci(3))

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)