[2023 알고리즘 스터디] 4조 안수빈 3주차 - 백준 10994, 6603, 10799, 13335

스택 & 큐

그래프 탐색 알고리즘

탐색이란?

- 많은 양의 데이터 중 원하는 데이터를 찾는 과정

대표적 그래프 탐색 알고리즘 : DFS / BFS

 

자료구조

- 스택 자료구조 : 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조

                            입구와 출구가 동일한 형태로 스택을 시각화 가능

                            삽입과 삭제, 두 연산으로 구성됨

 

- 큐 자료구조 : 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조

                        입구와 출구가 모두 뚫혀 있는 터널과 같은 형태로 시각화 가능

                         (python의 경우) deque 라이브러리 사용 - 효율적인 방법

 

재귀함수

재귀함수란?

- 자기 자신을 다시 호출하는 함수 

※ dfs를 구현할 때 자주 사용되는 방법 중 하나

 

★ 재귀함수의 종료 조건을 반드시 명시해야함.

종료 조건을 제대로 명시하지 않는다면 함수는 무한히 호출될 수도 있음.

 

 

#10994 - 별 찍기 19

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

10994번: 별 찍기 - 19

재귀함수를 이용한 코드 :

n = int(input())
len = 4*n-3
star = [[' '] * len for _ in range(len)]

def draw(n, idx):
    if n == 1:
        star[idx][idx] = '*'
        return
    a = 4*n - 3

    for i in range(idx, a+idx): 
        #위아래
        star[idx][i] = '*'
        star[idx+a-1][i] = '*'
        
        #양옆
        star[i][idx] = '*'
        star[i][idx+a-1] = '*'

    return draw(n-1, idx+2)

draw(n,0)
for i in range(len):
    for j in range(len):
        print(star[i][j], end="")
    print()

n에 따라서 4*n-3만큼 칸수들이 생긴다. 그리고 테두리 안에 있는 것의 내부에는 똑같은 것들이 반복된다.

n을 1씩 줄이면서 양옆, 좌우의 값들을 2씩 더해준다.

 

반복문으로 푼 코드 :

n = int(input())
for i in range(1, n):
    last = (n-i) * 4 + 1
    print("* " *(i-1) + "*" * last + " *" * (i-1))
    print("* " * i + " " * (last-4) + " *" * i)
print("* " * (2*n-1))
for i in range(n-1, 0, -1):
    last = (n-i) * 4 + 1
    print("* " * i + " "*(last-4) + " *" * i)
    print("* " * (i-1)+ "*" * last + " *" * (i-1))

 

 

#6603 - 로또

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

6603번: 로또

from itertools import combinations
while(True):
    s = list(map(int, input().split())) 
    if s[0]==0: #입력의 마지막 줄에는 0이 주어지므로 s의 첫 번째 원소가 0이라면 출력을 중지
        break
    del s[0]
    s = list(combinations(s, 6)) #입력된 원소 중 6개 중복없이 뽑기
    for i in s:
        print(" ".join(map(str, i)))
    print()

문제를 보자마자 조합이 생각나 라이브러리부터 combinations을 이용하였다.

 

combinations을 쓰는 방법 말고 재귀함수를 사용하여 dfs로 풀 수 있다.

def dfs(depth, idx):
    if depth == 6:
        print(*out)
        return

    for i in range(idx, k):
        out.append(S[i])
        dfs(depth + 1, i + 1)
        out.pop()

while True:
    array = list(map(int, input().split()))
    k = array[0]
    S = array[1:]
    out = []
    dfs(0, 0)
    if k == 0:
        exit()
    print()

 

 

#10799 - 쇠막대기

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

10799번: 쇠막대기

bar = list(input())
ans = 0
sta = []
for i in range(len(bar)):
    if bar[i] =="(":
        sta.append("(") #'('이 나오면 스택에 넣는다
    else: #')'인 경우
        if bar[i-1]=="(": #')'가 나오고 이전 문자가 '('라면 레이저. 현재 쌓인 '('개수만큼 더하기
            sta.pop()
            ans += len(sta)
        else: #')'가 나오고 이전 문자도 ')'라면 쇠막대기 끝머리 표현 
            sta.pop() #스택의 '('를 pop해줌
            ans+=1 #정답에 1 더하기
print(ans)

스택을 이용하여 푼 코드이다.

코드 설명은 위의 주석을 보면 된다.

 

 

#13335 - 트럭

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

13335번: 트럭

n, w, l = map(int, input().split())
truck = list(map(int, input().split()))
bridge = [0]*w
time = 0
while bridge:
    time += 1
    bridge.pop(0) #다리 위에 트럭이 올라간 것이므로 pop해줌
    if truck:
        if sum(bridge) + truck[0] <= l: #현재 다리에 있는 트럭과 다음 트럭을 더했을 때 l이하라면 다리에 트럭 넣어주기
            bridge.append(truck.pop(0))
        else:
            bridge.append(0)
print(time)

반복문을 통해 다리의 모든 트럭이 지나갈 때까지 반복한다.

- 모든 트럭을 확인하고 현재 다리에 있는 트럭과 다리를 건너려는 트럭의 무게가 다리의 하중보다 작거나 같다면 트럭을 다리에 추가한다.

- 반대로 다리의 하중보다 크다면 다리에 빈 공간을 추가해준다. 

- 위 방법을 반복하면 모든 트럭이 다 지나가면 반복이 멈춘다.

- 이때 time을 출력한다.