개발자 아지트

재귀 함수란?

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

이를 통해 문제를 반복적으로 분해하다가, 더 이상 분해할 수 없는 기본 조건(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))

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

[ObjectId]

ObjectId는 MongoDB에서 기본적으로 사용하는 고유 식별자입니다. MongoDB의 각 문서는 고유한 _id 필드를 갖는데, 이 필드는 자동으로 생성되며 기본적으로 ObjectId 타입입니다. ObjectId는 12바이트의 BSON(비너리 JSON) 데이터로 구성되어 있습니다.

ObjectId의 구성 요소

ObjectId는 다음과 같은 12바이트로 구성됨

1. 타임스탬프 (4바이트): ObjectId가 생성된 시간을 초 단위로 표현합니다. 이를 통해 객체가 생성된 시간 순서대로 정렬할 수 있음
2. 랜덤 값 (5바이트): 머신의 고유성을 보장하기 위해 생성된 무작위 값
3. 증가하는 카운터 (3바이트): 같은 머신에서 같은 시간에 생성된 ObjectId 간의 충돌을 방지하기 위한 증분 카운터

이러한 구조 덕분에 ObjectId는 고유성과 생성 시간 정보를 효율적으로 보장할 수 있음

ObjectId 예시

MongoDB에서 자동 생성된 ObjectId

2. unique: true

unique: true는 해당 필드에 대해 고유 인덱스를 생성하여, 중복된 값을 허용하지 않도록 합니다. 즉, 데이터베이스에 저장된 문서들 간에 이 필드의 값이 중복될 수 없음

• 특징:
  • 필드에 대해 고유 인덱스가 생성됨
  • 중복된 값을 가진 문서를 저장하려고 하면 중복 키 오류가 발생함
  • 인덱스가 생성되어 조회 성능이 향상될 수 있음

5-1. 배열 개념

배열은 인덱스와 값을 1대 1 대응하여 관리하는 자료구조이다. 

배열은 인덱스를 통해 어떤 위치에 있는 값이든 한 번에 접근할 수 있다. 

이런 방식을 임의 접근(random access)라고 한다. 

파이썬에서 배열 선언하는 방법

arr = [0, 0, 0]
arr = [0] * 3

리스트 생성자를 사용하는 방법

arr = list(range(3)) #[0, 1, 2]

리스트 컴프리헨션을 활용하는 방법

arr = [0 for _ in range(3)] # [0, 0, 0]

파이썬에서는 배열을 지원하는 문법은 따로 없고, 대신 리스트라는 문법을 지원한다. 

(사실 엄밀히 말하자면 배열과 리스트는 다른 개념임)

파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현됐다. 

파이썬의 리스트는 다른 언어의 배열 기능을 그대로 사용하면서 배열의 크기는 가변적으로 사용할 수 있다. 

배열과 차원

배열은 2차원, 3차원, ..., 다차원 배열 까지 사용할 수 있다. 

그러나 컴퓨터의 메모리 구조는 1차원이다. 

이는 2차원, 3차원, ..., 다차원 배열도 실제로는 1차원 공간에 저장된다는 뜻이다. 

배열은 몇 차원이든 상관없이 메모리에는 연속적으로 할당된다. 

1차원 배열

배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연속적으로 할당된다. 

2차원 배열

2차원 배열은 1차원 배열을 확장한 것이다. 

2차원 배열 활용 예시 

# 2차원 배열을 리스트로 표현
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

# arr[2][3]에 저장된 값 출력
print(arr[2][3]) # 12

# arr[2][3]에 저장된 값을 15로 변경
print[2][3] = 15

리스트 컴프리헨션을 통한 2차원 배열 활용 예시 

# 크기가 3 * 4인 리스트를 선언하는 예시 
arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

arr = [[1, 2, 3], [4, 5, 6]]

위의 배열에서  첫번째 행과 두번째 행의 메모리 주소는 연속된다. (1행의 인덱스 2 다음 바로 2행의 인덱스0의 주소가 이어진다. )

5-2. 배열의 효율성

배열 연산의 시간복잡도를 통해 배열의 효율성은 아래와 같다. 

배열 연산의 시간 복잡도

아까 배열은 인덱스를 통해 임의 접근 방법을 사용한다고 했다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다. 

만약 배열에 데이터를 추가하거나 삭제해야 한다면? 추가후에 기존에 있던 것들을 처리할 필요가 있는지,  혹은 대상을 삭제하고 기존에 있는 것들을 처리할 필요가 있는지 확인이 필요하다. 

1. 맨 뒤에 삽입할 경우

• 임의 접근을 통해 맨뒷 자리를 찾을 수 있다. 
• 맨 뒤에 값을 추가한 후에 기존의 값들을 이동할 필요가 없다. 
• 즉, 시간 복잡도는 O(1)이다. 

2. 맨 앞에 삽입할 경우

• 임의 접근을 통해 맨 앞 자리를 찾을 수 있다. 
• 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 현재 갖고 있는 데이터의 개수가 N개라면,  O(N))
• 즉, 시간 복잡도는 O(N)이다. 

3. 중간에 삽입할 경우

• 임의 접근을 통해 중간에 삽입할 자리를 찾을 수 있다. 
• 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 뒤로 밀어야 야 하는 데이터의 개수가 N개라면,  O(N))
• 즉, 시간 복잡도는 O(N)이다. 

위의 경우 들을 봤을때, 배열로 데이터를 저장하기 전에는 항상 이런 비용을 생각하는 것이 바람직하다. 

이렇듯 배열을 선택할 때 고려할 점은 다음과 같다. 

배열을 선택할 때 고려할 점

1. 할당할 수 있는 메모리 크기를 확인해야 한다. (파이썬에서는 리스트를 사용하므로, 배열 크기에 대한 고민은 할 필요가 없다. 공부를 위해 읽어두기)

• 운영체제마다 배열을 할당할 수 있는 메모리의 값은 다르지만, 보통 정수형 1차원 배열은 1천 만개, 2차원 배열은 3천*3천 크기를 최대로 생각한다. 따라서 이 이상의 값의 데이터를 관리하고자 하면 런타임에서 배열 할당에 실패할 수 있다. 

2. 중간에 데이터 삽입이 많은지 확인해야 한다. 

• 배열은 선형 자료구조이기 때문에, 중간이나 맨 처음의 위치에 데이터를 자주 삽입하면 시간복잡도가 높아져, 시간초과가 발생할 수 있다. 

5-3. 코딩테스트에서 자주 활용하는 리스트 기법

리스트에 데이터를 추가하는방법 

1. append()

# 리스트의 맨 끝에 데이터 추가
tmp_list = [1, 2, 3]
tmp_list.append(4) # [1, 2, 3, 4]

2. + 연산자

tmp_list = [1, 2, 3]
tmp_list = tmp_list + [4, 5] # [1, 2, 3, 4, 5]

3. insert()

# 특정 위치에 데이터를 삽입할 수 있다. 
tmp_list = [1, 2, 3]
tmp_list.insert(2, 9) #[1, 2, 9, 3]

리스트에서 데이터를 삭제하는 방법

1. pop() 

# 특정 위치에 데이터를 삭제할 수 있다. 
# 삭제한 데이터의 값을 반환한다. 
tmp_list = [1, 2, 3]
pop = tmp_list.pop(2) # 3
print(tmp_list) # [1, 2]

2. remove()

# 특정 데이터를 찾아 삭제할 수 있다. 
# 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제한다. 
tmp_list = [1, 2, 3]
tmp_list.remove(2) # [1, 3]

리스트 컴프리헨션으로 데이터에 특정 연산 적용하기

리스트 컴프리헨션은 기존 리스트를 기반으로 새 리스트를 만들거나, 반복문이나 조건문을 통해 복잡한 리스트를 생성하는 등 다양한 상황에서 사용할 수 있는 문법이다. 

리스트에 제곱 연산 적용 예시 

tmp_list = [1, 2, 3]
squares = [num**2 for num in tmp_list] #[1, 4, 9]
# tmp_list의 값은 여전히 [1, 2, 3] 이다.

리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐, 연산 대상 리스트를 바꾸지 않는다. 

유용하게 쓰이는 리스트 연관 메서드 

alphabet = ["a", "b", "c", "a"]

# 리스트의 전체 데이터 개수 반환 함수 len()
len(alphabet) # 4

# 특정 데이터가 처음 등장할 적의 인덱스를 반환하는 index()메서드, 만약 값이 없는경우 -1 반환
alphabet.index("a") # 0

# 사용자가 정한 기준에 따라 데이터를 정렬하는 sort()메서드
# 함수안에 인수가 없을 경우, 오름차순으로 데이터 정렬
alphabet.sort() # ["a", "a", "b", "c"]
# 역순 
alphabet.sort(reverse=True) # ["c", "b", "a", "a"]

# 특정 데이터 개수를 반환하는 count() 메서드
alphabet.count("a") # 2

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

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

문제 해결 방법

그림 정보가 적힌 좌표를 순회한다. 대신 방문여부를 알 수 있는 visited 배열이 필요하다. 

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

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

bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 그림이 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 

이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 

값이 0이 아니고 방문한 적이 없으면 현재자리의 값에서+1을 해준다.  큐에 해당 좌표와 얼마나 끊기지 않고 값을 조회하고있는지에 대한 값 현재 자리의 값+1을 넣어준다. 

순회를 하면서 더이상 큐에 값을 이어 넣을 수 없으면(그림이 끊기면), 얼마나 끊기지 않고 값을 조회했는지에 대한 값을 임의의 리스트에 넣어준다. 

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

코드 구현

정답 코드 

import sys
input=sys.stdin.readline
n, m = map(int, input().split())
from collections import deque

if n==0 and m==0:
    print(0)
    print(0)
    exit(0)

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

tmp=[]
for i in range(n):
    tmp2=list(map(int, input().split()))
    tmp.append(tmp2)

# 그냥 카운트만 하는애 cnt
# 방문 확인용 visited
cnt = 0
visited = [([False] * m) for _ in range(n)]
bigN = 0
def bfs(cnt, dequeA, visited):
    bigN=1
    while dequeA:
        yy, xx, _ = dequeA.popleft()
        visited[yy][xx] = True
        for i in range(4): 
            nx=xx+dx[i]
            ny=yy+dy[i]

            if ny<0 or nx<0 or ny>=n or nx>=m:
                continue
            if visited[ny][nx]==True or tmp[ny][nx]==0:
                continue
            if tmp[ny][nx]>=1 and visited[ny][nx]==False:
                tmp[ny][nx] = bigN+1
                bigN=bigN+1
                visited[ny][nx]=True
                dequeA.append([ny,nx, bigN])
    return cnt, bigN

tmp3=[]
check = 0
dequeA = deque()
for i in range(n):
    for j in range(m):
        if tmp[i][j] == 1 and visited[i][j] == False:
            dequeA.append([i,j, 1])
            cnt+=1
            cnt, bigN = bfs(cnt, dequeA, visited)
            tmp3.append(bigN)
            check =1

print(cnt)

if n == 0 and m ==0 or check ==0:
    print(0)
else:
    print(max(tmp3))

시간/공간 복잡도

따로 생각하지 않았다. 

최적화 및 개선

• 따로 하지않음

어려웠던 점

• BFS 문제를 효율적으로 푸는 방법이 가물가물해서 문제 풀기 어려웠다. 

알게된 것

함수 객체 할당과 함수 호출 구문을 구분하지 못해서 생긴 일 

여러줄을 받을 때 속도 감소를 위해 input()함수 말고 sys 에서 제공하는 readline()함수를 사용하려는 상황이다. 

import sys

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

input=sys.stdin.readline()

tmp=[]
for i in range(n):
    
    # tmp2=list(input.split())
    tmp2=input.split()
    print('tmp2', tmp2)
    tmp.append(tmp2)

print(tmp)

문제가 있는 코드: 이코드에서는 2번째줄 3번째줄만 입력을 받는게 된다. 

• 괄호를 붙이지 않은 경우 (input = sys.stdin.readline):
  • 이 경우 sys.stdin.readline 함수 객체를 input이라는 변수에 직접 할당하는 것이다. 이 상태에서는 input은 함수 객체 자체를 참조하게 된다.
• 괄호를 붙인 경우 (input()):
  • 괄호를 붙이면 함수가 실제로 호출된다. 함수 호출은 해당 함수가 수행하는 작업을 실행하고, 그 결과를 반환한다. 

import sys

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

input=sys.stdin.readline

tmp=[]
for i in range(n):
    
    tmp2=input().split()
    tmp.append(tmp2)

print(tmp)

문제 인지후 바꾼 코드