[2023 알고리즘 스터디] 1조 김예진 3주차 - 백준 25501, 17608, 2161, 17478

3주차 알고리즘 스터디

 

스택 & 큐

https://www.youtube.com/watch?v=7iLoLcna7Hw&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=16

 

재귀 함수

https://www.youtube.com/watch?v=gFpKGWdEE5g&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=17

 

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

-탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
-대표적인 그래프 탐색 알고리즘으로 DFS와 BFS가 있음
-두 가지는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야한다.

 

스택 자료구조

-저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조
-입구와 출구가 동일한 형태로 스택을 시각화 가능

 

큐 자료구조

-먼저 들어 온 데이터가 먼저나가는 형식(선입선출)의 자료구조
-큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능

 

재귀 함수

-재귀 함수란 자기 자신을 다시 호출하는 함수를 의미
-재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 함.
-종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있음.

재귀 함수 사용의 유의 사항

-재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음.
(단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 함.)
-모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음.
-재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음.
-컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임.
(그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많음.)

 

 

# 25501 - 재귀의 귀재

25501번: 재귀의 귀재 (acmicpc.net)

25501번: 재귀의 귀재

import sys
input = sys.stdin.readline

def recursion(s, l, r):
    global cnt
    cnt +=1
    if(l>=r):
        return 1
    elif(s[l] != s[r]):
        return 0
    else:
        return recursion(s, l+1, r-1)
def isPalindrome(s):
    return recursion(s, 0, len(s)-1)
T = int(input())
for _ in range(T):
    s = input().rstrip()
    cnt = 0
    a = isPalindrome(s)
    print(a, cnt)

 

 

 

 

# 17608 - 막대기

17608번: 막대기 (acmicpc.net)

17608번: 막대기

import sys

input = sys.stdin.readline

n = int(input())
stack = []

for _ in range(n):
   stack.append(int(input()))
   
last = stack[n - 1]
count = 1

for i in reversed(range(n)):
    if stack[i] > last:
       count += 1
       last = stack[i]
       
print(count)

 

 

 

 

# 2161 - 카드1

2161번: 카드1 (acmicpc.net)

2161번: 카드1

n = int(input())
card = list() #인덱스 필요
discard = list()

for i in range(1, n + 1):
    card.append(i)

while len(card) != 1:
    discard.append(card.pop(0)) 
    card.append(card.pop(0))

for i in range(n - 1):
    print(discard[i], end = ' ') #버려진 카드 먼저 한줄로 출력

print(card[0]) #마지막 남은 카드 출력

 

 

 

 

# 17478 - 재귀함수가 뭔가요?

17478번: 재귀함수가 뭔가요? (acmicpc.net)

17478번: 재귀함수가 뭔가요?

#17478번 문제 같은 경우는 팀원 대부분이 어렵고 복잡하다고 느껴 다양한 코드를 공유하며 이야기를 나눠 보았습니다.

def e(n): # fn함수가 끝나고 나서 실행되는 재귀함수
    if n >= 0:
        print(("____"*(n))+"라고 답변하였지.")
        e(n-1) # 재귀 함수 실행
    else:
        return 0 # 재귀 함수 종료
def fn(n):
    if n > 0: # 0 초과일 경우
        print(("____"*(s-n))+"\"재귀함수가 뭔가요?\"")
        print(("____"*(s-n))+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.")
        print(("____"*(s-n))+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.")
        print(("____"*(s-n))+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"")
        return fn(n-1)  # 재귀 함수 실행
    else: # 0 이하일 경우
        print(("____"*(s-n))+"\"재귀함수가 뭔가요?\"")
        print(("____"*(s-n))+"\"재귀함수는 자기 자신을 호출하는 함수라네\"")
        e(s) # e 함수 실행
s = int(input()) # 재귀함수 실행 횟수 입력
print("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.")
fn(s)