[2023 알고리즘 스터디] 3조 성동현 3주차 - 백준 2161, 11866, 10994, 6603

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다.

그 중 예시를 들 그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 얘기하는데

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있습니다.

깊이 우선 탐색이라고 불리우는 DFS와 너비 우선 탐색이라고 불리우는 BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 숙지하여야 합니다.

 

 

스택 자료구조

먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조입니다.

입구와 출구가 동일한 형태로 스택을 시각화할 수 있습니다.

 

큐 자료구조

먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조입니다.

큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있습니다.

 

재귀함수

재귀함수란 자기 자신을 다시 호출하는 함수를 의미합니다.

장점으로는 변수를 여러개 만들 필요가 없다는 것과 반복문 사용을 줄일 수 있어 코드가 간결해집니다.

하지만 단점으로는 지속적으로 함수를 호출하게 되기 때문에 단순 반복문에 비해 메모리를 더 많이 사용하게 될 가능성이 있고 종료조건을 제대로 세우지 않는다면 함수가 무한히 호출되는 불상사가 일어날 수 있습니다.

 

 

# 2161 - 카드1

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

2161번: 카드1

 

from collections import deque

def shake_card(N):
    queue= deque([i for i in range(1,N+1)]) #인덱스가 작은 쪽일수록 위쪽에 쌓여있고 클 수록 큰 쪽에 쌓여있다.
    gabage_list=[] # 버린카드를 순서대로 저장하는 리스트
    for _ in range(N-1):
        gabage_list.append(queue.popleft()) #위쪽의 카드 버리기
        queue.append(queue.popleft()) #그 다음 카드를 아래로 옮기기
    gabage_list.append(queue.popleft()) #마지막 장 버리기
    # for i in range(0,len(gabage_list)): #출력
    #     print(gabage_list[i],end=' ')
    print(*gabage_list)
if __name__=="__main__":
    shake_card(int(input()))

해당 문제를 풀면서 print(*arg)처럼 파라미터를 가변인자로 줌으로써 문제에서 원하는 방향으로 간결하게 출력하는 방식을 알게 되었습니다.

 

 

# 11866 - 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

 

def Josephus():
    N,K=map(int, input().split())
    queue=[i for i in range(1,N+1)]
    gabage_list=[]
    for _ in range(N): #N명 제거하기
        for i in range(K-1):
            queue.append(queue.pop(0)) #버렸다가 다시 추가하기
        gabage_list.append(queue.pop(0))
    print("<",end="")
    for i in range(len(gabage_list)-1):
        print(f"{gabage_list[i]},", end=" ")
    print(f"{gabage_list[len(gabage_list)-1]}>")

if __name__=="__main__":
    Josephus()

 

코드가 실행되는 과정을 좀 더 보기 좋게 정리한 내용입니다.

 

# 10994 - 별 찍기 - 19

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

10994번: 별 찍기 - 19

 

def Total_star(N):
    list=[[" "for _ in range(4*N-3)] for _ in range(4*N-3)]

    def star_maker(n, x, y):
        if n==1: #재귀함수 종료조건
            list[y][x]="*"
            return
        l=4*n-3

        for i in range(l):
            list[y][x+i]="*"
            list[y+i][x]="*"
            list[y+l-1][x+i]="*"
            list[y+i][x+l-1]="*"
        star_maker(n-1,x+2,y+2)



    star_maker(N,0,0)
    for i in list:
        print("".join(i))




if __name__=="__main__":
    Total_star(int(input()))

 

 

# 6603 - 로또

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

6603번: 로또

 

def lotto(aList):
    aList.pop(0)
    lotto_part = [0 for _ in range(6)]

    def dfs(start,depth):

        if depth==6: #재귀함수 종료조건
            print(*lotto_part)
            return

        for i in range(start,len(aList)):
            lotto_part[depth]=aList[i]
            dfs(i+1,depth+1)
    dfs(0,0)




if __name__=="__main__":
    while 1:
        aList=list(map(int, input().split()))
        if aList[0]==0:
            break
        lotto(aList)
        print("")

 해당 문제는 파이썬 내장 함수를 사용하면 수월하게 코드를 작성할 수 있지만 재귀함수를 통해 푸는 것을 선택하였습니다.

for문을 통해 조합의 시작숫자를 점차적으로 늘려가기 때문에 문제에서 요구하는 사전식 배열을 쉽게 해결할 수 있었고 종료조건을 알맞게 구현함으로서 재귀함수를 이용해 적절하게 문제를 해결할 수 있었습니다.