[이코테] 3강 스택/ 재귀함수/2493번 탑 문제

스택

 

먼저 들어온 데이터가 나중에 나가는 선입후출

입구와 출구가 동일한 형태

박스쌓기 구조

 

파이썬, 리스트 형태로 구현가능

append(), pop() 연산으로 오른쪽에서 삽입,삭제

 

print(stack[::-1]) //최상단 원소부터 출력

print(stack) //최하단 원소부터 출력

 

재귀함수(recursive  function)

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

 

유의사항

- 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다

- 재귀함 수가 반복문보다 유리한 경우도 있고 불리한 경우도 있음

- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부 스택 프레임에 쌓임

- 스택 사용해야할 때 구현상 스택 라이브러리 대신 재귀함수 이용하는 경우 많음

재귀함수 종료조건 명시

반복문으로 구현했을 때보다 코드 간결

 

최대공약수 계산 (유클리드 호제법)

유클리드 호제법

: 두 자연스 a,b에 대해 (a>b), a를 b로 나눈 나머지를 r이다

이때 a,b의 최대공약수는 b와 r의 최대공약수와 같습니다.

def gcd(a,b):
	if a%b == 0:
    	return b
    else:
    	return gcd(b, a%b)
        
print(gcd(192, 162)) //a,b순서는 상관없음

 

 

 

 

2493번 탑 문제

 

 

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

 

 

#  [6,9,5,7,4]
# 4->7, 7->9, 5->9, 9,6 -> x
# stack 사용

N = int(input())  # 탑의 개수
top_list = list(map(int, input().split()))  # 탑 리스트

# 최댓값 저장할 스택, 인덱스와 top의 값 삽입
stack = [] 
# 수신 탑 인덱스 저장
answer = []

for i in range(N):
    while stack:
        if stack[-1][1] > top_list[i]:  # 수신 가능한 상황
            answer.append(stack[-1][0] + 1)
            break
        else:
            stack.pop()
    if not stack:  # 스택이 비면 레이저를 수신할 탑이 없다.
        answer.append(0)
    stack.append([i, top_list[i]])  # 인덱스, 값

print(" ".join(map(str, answer)))

 

stack[][]가 무슨의미인지 몰랐음

 

x = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(x[-1][0])

Output:7

 

 

 

 

참고

 

https://jjangsungwon.tistory.com/44

[ 백준 2493 ] 탑 - Python

 

너무 어렵다.... 혼자 구현 못함