on my way
[코딩테스트 합격자 되기 - 3주차] 스택 (프로그래머스 문제 풀이) 본문
06. 스택
06-1. 스택 개념
스택은 어원에서 짐작할 수 있듯이 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조이다.
이렇게 먼저 들어간 것이 마지막에 나오는 규칙을 선입후출 또는 FILO(First In Last Out)라고 한다.
이때 스택에 삽입하는 연산을 푸시push, 꺼내는 연산을 팝pop이라고 한다.
06-2 스택의 정의
ADT는 우리말로 추상 자료형abstract data type으로, 추상 자료형이란 인터페이스만 있고 실제로 구현은 되지 않은 자료형이다.
일종의 자료형의 설계도라고 생각하면 된다. 그렇다면 스택은 어떤 정의가 필요한 자료구조인가?
언어에 따라 표준 라이브러리에서 스택 제공 여부는 다르다. 파이썬의 경우 스택을 제공하진 않지만 대안으로 리스트 메서드인 append( ), push( ) 메서드로 스택을 대체할 수 있다.
덱(deque)은 한쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이다. 이런 덱의 특징을 조금만 응용하면 스택처럼 사용할 수 있다.
스택의 ADT
우선 스택에는 ➊ 푸시push, ➋ 팝pop, ➌ 가득 찼는지 확인isFull, ➍ 비었는지 확인isEmpty과 같은 연산을 정의해야 한다. 그리고 스택은 최근에 삽입한 데이터의 위치를 저장할 변수인 ➎ 탑top도 있어야 한다.
여기서는 스택의 내부 데이터를 배열로 관리하는 모습을 예로 들었다. 하지만 스택의 원소는 배열이 아니라 다른 자료구조로 관리할 수도 있다.
data 배열을 보면 최대 크기는 maxsize이므로 인덱스의 범위는 0부터 maxsize - 1이다.
top은 가장 최근에 추가한 데이터의 위치를 참조한다. 지금 그림에서는 아무 데이터도 없으므로 top에 -1이 들어 있다. 만약 top이 0이면 데이터가 1개 있는 것이다.
스택 세부 동작
스택에 데이터를 추가하는 경우를 생각해보자. 이번에 설명할 내용은 이 푸시 연산을 수행할 때 스택 내부에서 일어나는 과정이다.
그림은 push(3) 연산을 수행하며 데이터 3이 추가되는 모습을 보여준다.
반대로 pop( ) 연산을 수행한다면?
스택 구현하기
스택 ADT를 구현하면 다음과 같다.
stack = [ ] # 스택 리스트 초기화
max_size = 10 # 스택의 최대 크기
def isFull(stack):
# 스택이 가득 찼는지 확인하는 함수
return len(stack) == max_size
def isEmpty(stack):
# 스택이 비어 있는지 확인하는 함수
return len(stack) == 0
def push(stack, item):
# 스택에 데이터를 추가하는 함수
if isFull(stack):
print("스택이 가득 찼습니다.")
else:
stack.append(item)
print("데이터가 추가되었습니다.")
def pop(stack):
# 스택에서 데이터를 꺼내는 함수
if isEmpty(stack):
print("스택이 비어 있습니다.")
return None
else:
return stack.pop( )그러나 파이썬의 리스트는 크기를 동적으로 관리하므로 max_size나 isFull( ), isEmpty( ) 함수는 실제 문제를 풀 때 구현하지 않는다.
실제로 다음 코드를 보면 max_size, isFull( ) 함수는 사용하지 않고 isEmpty( ) 함수는 len(stack) == 0으로 검사한다.
stack = [ ]
# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)
# 스택에서 데이터 꺼냄
top_element = stack.pop( )
next_element = stack.pop( )
# 스택의 크기를 구함
stack_size = len(stack)
# top_element : 3
# next_element : 2따라서 스택 관련 문제를 많이 풀어보며 ‘이 문제는 스택을 사용하는 게 좋겠다’라는 감을 익히는 것이 필요하다.
실행 예시
#############################################################
# | cafe | http://cafe.naver.com/dremdelover |
# | Q&A | https://open.kakao.com/o/gX0WnTCf |
# | business | ultrasuperrok@gmail.com |
#############################################################
# 1. 자료구조 개념:
# 스택(Stack)은 선입후출(FILO, First In Last Out) 원칙에 따라 작동하는 자료구조입니다.
# 새로운 요소는 스택의 상단에 추가되고, 상단의 요소만이 삭제될 수 있습니다.
# 2. 예시 입력 / 출력:
# 입력: [1, 2, 3, 4]
# 출력: [1, 2, 3] (4를 pop한 결과)
# 3. 자료구조의 시간 복잡도:
# - Push: O(1)
# - Pop: O(1)
# - Top: O(1)
# 4. 해당 자료구조로 풀 수 있는 문제 예시:
# - 괄호 짝 맞추기
# - 브라우저 뒤로 가기 기능
# - 트리의 깊이 우선 탐색(DFS)
# 5. 상세과정:
# - 스택 생성: 리스트를 초기화하여 스택으로 사용
# - Push: 리스트의 append 메소드를 사용하여 요소를 스택의 맨 위에 추가
# - Pop: 리스트의 pop 메소드를 사용하여 스택의 맨 위 요소를 삭제하고 반환
# - Top: 리스트의 마지막 요소를 참조하여 스택의 맨 위 요소를 확인
# 스택 생성
stack = []
# Push 연산: 요소를 스택의 맨 위에 추가
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
print(stack) # 출력: [1, 2, 3, 4]
# Top 연산: 스택의 맨 위 요소 확인
print(stack[-1]) # 출력: 4
# Pop 연산: 스택의 맨 위 요소 삭제 및 반환
stack.pop()
print(stack) # 출력: [1, 2, 3]
재귀의 정의 및 개념
재귀(recursion) : 자신을 정의할 때 자기 자신을 재참조하는 방법
재귀함수 : "자기 자신을 재참조하도록 만든 함수"
def func():
print("called")
func()
func()자기 자신을 재참조하는 재귀함수를 정의하고 실행하면 에러가 뜬다.
called
<대략 1,000번 called가 출력됨>
RecursionError: maximum recursion depth exceeded while calling a Python objectRecursion에러라고 되어있고 maximum recursion depth exceed가 원인인 것 처럼 보인다.
일단 함수가 호출되면, 해당 함수의 코드와 필요한 변수 및 기타 정보들을 표시하기 위한 메모리 공간이 잡힙니다.
func() 함수를 호출했을때도 마찬가지일 것이다. 그리고 func()함수에서 func() 함수를 호출할때를 생각해보면, 이전 함수가 종료되기 전에 다른 함수가 호출된 상황이다. 따라서 함수 2개에 대한 메모리 공간이 잡히게 된다. 그림으로 표현하면 아래와 같다.
runtime error가 발생하는 프로그램은 정상이 아니다. 즉 위와 같은 재귀함수는 의미가 없다. 재귀함수의 정의에 뭔가 추가 되야한다.
재귀함수는 자기 자신을 재참조 하는 함수이다. 단, 무한한 재귀(infinite recursion)을 가지지 않는다. 반드시 바로 풀수있거나 혹은 종료조건을 포함한 base case(재귀함수 호출을 더 이상 하지 않고 -문제를 더 간단히 할 필요 없이- 문제를 직접 해결할 수 있는 사례)가 1개 이상 존재한다. 같은 문제를 좀더 간단한 문제로 감소 시키는 방식으로 동작한다.
[재귀의 예시]
가장 간단한 팩토리얼을 생각해보면, 팩토리얼의 정의는 아래와 같다.
1! = 1
2! = 2 * 1
3! = 3 * 2 * 1
N! = N * (N-1) * (N-2) ..... * 1
이를 반복문으로 구현하면 아래와 같다. (Iterative solution)
# 반복문을 활용한 구현
def iterative_factorial(N) :
answer = 1;
while N >= 1:
answer = answer * N;
N = N - 1
return answer;
print(iterative_factorial(3))
같은 문제를 풀기위해 재귀적인 해결책을 고민해본다.(Recursive solution)
재귀의 정의에서 본 것처럼, 어떤 문제를 재귀로 풀 때는 2가지를 고민해야 한다.
1. 문제를 처리하는 방식을 어떻게하면 유지하면서, 더 간단하면서 작게(Simpler & Smaller) 할 수 있을 것인가.
2. base case는 어떻게 되는가. 어느 순간에 더 이상 재귀가 호출되지 않고 직접 문제를 풀도록 할 것인가.
딱히 생각이 잘 나지 않을때는 아래와 같이 작성해 보는것이 좋다.
값이 N일때 해를 구하는 과정을 나열해보고 (N-1)일때 나열해보고 (N-2)일때 나열해보고, 규칙이 있는지 살펴보는 것이다.
규칙이 있는지 살펴볼때는 (N-1)일때 구하는 과정을 N일때 구하는 과정에 포함시킬수 있는지 를 보는것이 좋다.
(즉, (N-1) 일때 해를 구하는 과정이 N일때 해를 구하는 과정의 일부가 될 수 있는지)
아래 그림을 보면 (N-1)!의 해를 구하는 과정은 N!의 해를 구하는 과정의 일부가 됨을 알 수 있습니다. 그리고 (N-2)!의 해를 구하는 과정은 (N-1)!의 해를 구하는 과정의 일부가 될 수 있다.
즉, 위 내용을 정리하면 아래와 같이 식을 세울수 있습니다.
N! = N * (N-1)!
(N-1)! = (N-1) * (N-2)!
점점 이렇게 숫자를 줄이다 보면, N이 1이 될 때까지 줄일 수 있다.
N이 1일 경우엔 1!이니 바로 1을 반환해도 된다. 즉 1이라는 값을 반환하고, 더이상 새로운 팩토리얼을 추가로 구할 필요가 없다. (base case에 해당)
종합하면 우리는 아래와 같은 식을 얻을 수 있다.
- N! = N* (N-1)!
- 단 N이 1일 경우엔 1
처리하는 방식을 유지하면서, 문제를 좀 더 간단하면서 덜 복잡하게 만들었다.
(N!은 크기가 N인 문제이다. 이를 N *(N-1)!이라고 한순간 N은 상수값이므로 문제가 아니고 우리의 문제는 크기가 (N-1)인 문제가 된다. 점점 반복할수록 해당 시점에 풀어야 하는 문제의 크기가 줄어드는 것이다. 이걸 복잡성이 줄어든다고 표현할 수 있다.)
재귀함수의 구현
숫자 하나를 입력 받고, N!을 구해주는 함수가 그냥 있다고 가정해본다.
def Fact(N):이 함수가 있다고 가정하고 위 점화식을 구현해보자.
어쨌든 위 함수는 N!을 반환하는 함수이다. 인자로 N-1을 넣으면 N-1!을 반환한다.
이와 같이 내가 구해야 할 문제를 푸는 함수가 있다고 가정한 후, 점화식 부터 세우는게 먼저 다.
그 후에 해당 함수에 점화식을 그대로 구현하면 재귀함수가 완성
def Fact(N):
if(N==1): # base case : 1! = 1이므로 더이상 추가로 팩토리얼을 구하지 않고 직접 반환
return 1
return N * Fact(N-1) # N! = N * (N-1)!
재귀의 다양한 예시 - 하노이 탑
[하노이 탑]
아래와 같이 3개의 기둥이 있고, 첫 번쨰 기둥에는 크기가 큰 막대가 제일 아래에 있고 위로갈수록 크기가 조금씩 작은 막대가 있다.
이 문제의 목적은 첫 번째 기둥에 있는 모든 막대를, 아래 규칙을 지키면서 세 번째 기둥이 옮기는 것이다.
규칙
1. 한번에 하나의 기둥만 옮길수 있다.
2. 크기가 작은 기둥위에 크기가 큰 기둥을 올릴 수 없다.
막대의 개수가, 1개일때와 2개일 때 이동하는 과정을 쭉 나타내보자
1. 막대가 한 개
막대가 하나밖에 없으므로 맨 처음 기둥에 있는 막대를 바로 3번째로 옮기면 된다.
2. 막대가 두 개
3. 막대가 세 개
이 문제를 재귀로 풀기 위해 울기가 고민해야 할 것은 2가지 이다.
1. 문제를 어떻게 하면 처리하는 방식을 유지하면서, 더 간단하면서 작게(Simpler & Smaller) 할 수 있을 것인가.
2. base case는 어떻게 되는가. 어느 순간에 더 이상 재귀가 호출되지 않고 직접 문제를 풀도록 할 것인가.
막대가 하나일 때는 바로 옮기면 된다.
막대가 2개일 때와, 3개일 때를 한번 봅시다. 보면 아래와 같은 패턴이 발견된다. (이는 막대가 많아져도 마찬가지일 것이다.)
1. 첫 번째 기둥의 맨 밑의 막대를 제외하고, 나머지 막대를 두 번째 기둥에 옮깁니다.
2. 첫 번째 기둥의 맨 밑의 막대를 세 번째 기둥에 옮깁니다.
3. 두 번째 기둥에 있는 막대를 세 번째 기둥에 옮깁니다.
이를 활용하면, 아래처럼 막대 3개를 옮기는 문제를 막대 2개를 옮기는 문제와 막대 1개를 옮기는 문제로 축소할 수 있다.
여기서 발생하는 막대 2개를 옮기는 문제는 막대 1개를 옮기는 문제로 축소할 수 있기 때문에 결론적으로 막대 3개를 옮기는 문제를, 막대 1개를 옮기는 문제로 축소해서 해를 구한다고 보면 된다.
def hanoi(from,by,to,cnt):
- cnt는 막대를 몇개 옮길 것인지, from, by, to는 각각 기둥의 번호
맨 처음에는 from,by,to가 1,2,3 즉 첫번째 기둥은 1, 두번째 기둥은 2, 세번째 기둥은 3으로 된다.
그리고 이것은 첫번째 기둥에서 세번째 기둥으로 cnt개의 막대를 옮기는 하노이 문제를 풀어주는 것이다.
코드로 얘기하면 기둥 번호 from에서 to 까지 cnt 개의 막대를 옮기는 하노이 문제를 푸는 것입니다.
막대가 3개일 때 풀이 설명을 보시면 막대가 2개인 문제로 축소하는 과정에서 2번째 기둥을 3번째 기둥이라고 생각하는 부분이 있다.
이것을 코드로 표현하면 from을 1로 to를 2로 하면 된다.
이렇게 하면 맨 처음 기준으로, 첫번째 기둥에서 두번째 기둥으로 막대를 옮기는 문제를 해결하는 것이 된다.
즉 내가 막대를 옮기고 싶을때 source에 해당 되는 기둥을 from으로 하고, destination에 해당 되는 기둥을 to로 하고 나머지를 by로 하면 된다.
def hanoi(_from, _by, _to, cnt):
if cnt == 1:
print(f"{_from}->{_to}")
return
hanoi(_from, _to, _by, cnt - 1)
print(f"{_from}->{_to}")
hanoi(_by, _from, _to, cnt - 1)
# 예시: 3개의 디스크를 사용하는 하노이 탑 문제를 해결
hanoi(1, 2, 3, 3)// 출력
1->3
1->2
3->2
1->3
2->1
2->3
1->3스택을 활용하는 경우
1. 함수의 호출
함수가 호출되면, 해당 함수의 실행에 필요한 정보(반환 주소, 매개변수, 지역변수, 코드 등)가 스택에 저장된다.
보통 이러한 정보를 "스택 프레임"이라고 부르기도 한다.
함수가 종료되면, 이 정보를 사용해서 실행 흐름을 함수가 호출된 지점으로 돌려보낸다.
def function1():
print("Function 1 시작")
function2()
print("Function 1 끝")
def function2():
print("Function 2 시작")
# 여기서 추가적인 함수 호출이 있을 수 있음
print("Function 2 끝")
# function1을 호출하여 시작
function1()
Step 1)
function1()이 호출이 되었을때 스택 프레임 모습이다.
function1이 스택에 푸시 되었음을 알 수 있다.
Step 2)
function1()에서 function2()가 호출되는 시점이다.
function2()가 호출되었을 때, function1()은 아직 종료되지 않았으므로 function1() 역시 스택에 계속 있다.
Step 3)
function2()가 종료되었을 때 모습이다.
여전히 function1()은 아직 종료되지 않았으므로 funtion2()역시 계속 스택에 있다.
Step 4)
function1()까지 모두 종료된 모습이다.
이런 방식으로 스택에 나중에 호출(푸시)된 함수가 먼저 팝 되는 것을 볼 수 있다.
2. 뒤로 가기
웹 브라우저를 사용하다 보면 뒤로가기 버튼을 예시로 보자.
페이지를 A->B->C로 방문했을때, C페이지에서 뒤로가기를 하면 C->B->A로 뒤로가기가 수행되야 한다.
# 웹 페이지 이력을 저장할 리스트
history = []
# 웹 페이지 방문
history.append("홈페이지")
history.append("뉴스 페이지")
history.append("이메일 페이지")
# 현재 방문 중인 페이지 출력
print("현재 페이지:", history[-1])
# 뒤로 가기
history.pop()
print("뒤로 가기 후 페이지:", history[-1])
# 뒤로 가기
history.pop()
print("뒤로 가기 후 페이지:", history[-1])// 출력
현재 페이지: 이메일 페이지
뒤로 가기 후 페이지: 뉴스 페이지
뒤로 가기 후 페이지: 홈페이지
06-3. 몸풀기 문제
문제08. 괄호 짝 맞추기
def solution(s):
stack = []
for e in s:
if e==')' :
if not len(stack): return False
else: stack.pop()
elif e=='(':
stack.append(e)
if not stack: return True
return False# 예시 코드
def solution(s):
stack = [ ]
for c in s:
if c == "(":
stack.append(c)
elif c == ")":
if not stack:
return False
else:
stack.pop( )
if stack:
return False
else:
return True
시간 복잡도 : f
N은 s의 길이
s를 순회하며 괄호의 쌍을 확인하므로 시간 복잡도는 O(N)
참고로 괄호 쌍을 확인할 때 append( ) 메서드와 pop( ) 메서드의 시간 복잡도는 O(1)
문제09. 10진수를 2진수로 변환하기
def solution(decimal):
return bin(decimal)[2:]처음엔 이런식으로 풀었지만 스택을 활용해야겠다고 생각했다.
def solution(decimal):
stack = []
while(1) :
stack.append(decimal % 2)
if decimal == 1: break
decimal //=2
answer = ''
while len(stack):
answer += str(stack.pop())
return int(answer)# 예시 코드
def solution(decimal):
stack = [ ]
while decimal > 0:
remainder = decimal % 2
stack.append(str(remainder))
decimal //= 2
binary = ""
while stack:
binary += stack.pop( )
# 이 문제에서는 스택 활용을 보여주기 위해 pop()을 했지만 문자열에 계속해서 문자를 더할 때는 join() 메서드가 더 효율적입니다.
return binary
시간 복잡도 :
N은 이진수로 변환할 숫자. N을 이진수로 변환하는 과정은 N이 1이 될 때까지 2로 계속 나누므로 연산 횟수는 O(logN).
하지만 문자열의 += 연산자는 수행할 때마다 객체를 새로 생성하기 때문에 시간 복잡도는 O((logN)^2)
join( ) 메서드를 활용하면 시간 복잡도를 O(logN)으로 낮출 수 있다.
06-4. 합격자가 되는 모의 테스트
문제10. 괄호 회전하기
def solution(s):
result = 0
for _ in range(len(s)):
s = s[1:] + s[0]
stack = []
for c in s:
if c=='(' or c=='{' or c=='[':
stack.append(c)
else:
if not stack:
break
if c==')' and stack[-1]=='(':
stack.pop()
elif c=='}' and stack[-1]=='{':
stack.pop()
elif c==']' and stack[-1]=='[':
stack.pop()
else:
break
else:
if not stack:
result += 1
return result사실 한번에 풀지 못함. for-else 구문을 처음 배웠다.
# 예시 코드
def solution(s):
answer = 0
n = len(s)
for i in range(n):
stack = [ ]
for j in range(n):
# ➊ 괄호 문자열을 회전시키면서 참조
c = s[(i + j) % n]
if c == "(" or c == "[" or c == "{": # ➋ 열린 괄호는 푸시
stack.append(c)
else:
if not stack: # ➌ 짝이 맞지 않는 경우
break
# ➍ 닫힌 괄호는 스택의 top과 짝이 맞는지 비교
if c == ")" and stack[-1] == "(":
stack.pop( )
elif c == "]" and stack[-1] == "[":
stack.pop( )
elif c == "}" and stack[-1] == "{":
stack.pop( )
else:
break
else: # ➎ for문이 break에 의해 끝나지 않고 끝까지 수행된 경우
if not stack:
answer += 1
return answer❶ 문자열을 회전하며 참조하는 반복문. 문제에서 문자열의 문자를 왼쪽으로 밀면서 이동한다고 했고, 이는 맨 앞에 있는 문자는 맨 뒤로 가는 것과 같다. 다만 구현 부분에서는 진짜 문자열을 회전시키면 연산 비용이 많이 드므로 인덱스를 활용한다. 즉, i를 첫 번째 문자의 위치를 가리키는 값이라 생각해 회전을 간단히 구현했다. j는 i 이후 등장하는 문자를 가리키는 인덱스이다. 예를 들어 볼까요? 다음 그림은 i = 2입니다. 즉, 3번째 문자를 첫 번째 문자라고 친다.
i를 기준으로 다음 문자를 하나씩 가리킨다. 이때 다음 문자를 계산하기 위한 값을 오프셋이라 부르고, 이 오프셋 역할을 하는 것이 j이다. 즉, i + j와 같은 방법으로 첫 번째(j = 0), 두 번째(j = 1) 값을 표현한다. 그리고 회전 시킨 배열에서의 j 번째 값의 위치를 표현하기 위해 (i + j) % n과 같이 모듈러 연산을 해준다. 예를 들어 i = 2, j = 4라면 논리상으로는 4번째 값인 (, 실제 배열에서는 인덱스 0을 가리켜야 한다. 이렇게 하면 회전 구현은 끝이다.
➋ 여는 괄호가 있으면 스택에 푸시. append( ) 메서드는 리스트 맨 뒤에 데이터를 추가하므로 스택의 푸시 동작과 일치.
➌ c는 현재 참조하는 문자입니다. 닫는 괄호를 참조할 때 스택에 아무 값도 없으면 닫는 괄호와 짝을 맞출 여는 괄호가 아예 없다는 뜻이다. 그러면 검색을 중단하고 다음 회전 문자열을 확인하기 위해 for문을 빠져나간다.
➍ 는 c가 참조한 닫힌 괄호가 있을 때 스택에 여는 괄호가 있는 경우이다. 이 경우 최근 여는 괄호, 즉, 스택의 top 위치(stack[-1])의 괄호와 짝이 맞는지 비교한다. 짝이 맞으면 팝 연산을 수행한다.
➎ 파이썬에는 for-else문이 있습니다. else문은 for문이 끝까지 실행되었을 때 동작한다. 이 문제에서는 괄호의 모든 짝이 맞으면 실행된다. 즉, 모든 짝이 맞는 문자열마다 answer를 1만큼 증가시킨다.
파이썬은 음수 인덱스도 지원한다. 음수 인덱스의 시작 기준은 맨 뒤의 원소이며, -1부터 거꾸로 -2, -3과 같이 인덱싱 한다. 따라서 인덱스 -1은 맨 뒤의 원소를 의미한다.
시간 복잡도:
N은 s의 길이, 회전한 괄호 문자열의 유효성을 체크할 때 이중 반복문을 활용하므로 시간 복잡도는 O(N^2)
참고로 괄호 쌍을 확인할 때 append( ) 메서드와 pop( ) 메서드의 시간 복잡도는 O(1)
문제11. 짝지어 제거하기
def solution(s):
while(1):
stack = []
for c in s:
if not stack:
stack.append(c)
else:
if c==stack[-1]:
stack.pop()
else:
stack.append(c)
if not stack:
return 1
else:
if ''.join(stack) == s: return 0
else: s = ''.join(stack)내가 짠 코드의 시간 복잡도 : O(N^2)
나는 처음부터 모든 과정을 구현하는 형태로 짰는데 예시 코드는 매우 간단했다.
def solution(s):
stack = [ ] # 스택 초기화
for c in s:
if stack and stack[-1] == c: # ➊ 스택이 비어 있지 않고,
# 현재 문자와 스택의 맨 위 문자가 같으면
stack.pop( ) # ➋ 스택의 맨 위 문자 제거
else:
stack.append(c) # ➌ 스택에 현재 문자 추가
return int(not stack) # ➍ 스택이 비어 있으면 1, 그렇지 않으면 0 반환예시 코드의 시간 복잡도 : N은 s의 길이. O(N)
문제12. 주식 가격
처음에는 O(n^2)으로 풀다가 안풀리고 문제를 이해하기 어려워서 예시 코드를 참고함
def solution(prices):
N = len(prices)
answer = [0 for _ in range(N)] # ➊ 가격이 떨어지지 않은 기간을 저장할 배열
stack = [0] # ➋ 스택 초기화
for i in range(1, N):
while stack and prices[i] < prices[stack[-1]]:
# ➌ 가격이 떨어졌으므로 이전 가격의 기간 계산
j = stack.pop()
answer[j] = i-j
stack.append(i)
# ➍ 스택에 남아 있는 가격들은 가격이 떨어지지 않은 경우
while stack:
j = stack.pop()
answer[j] = N-1-j
return answer
문제13. 크레인 인형 뽑기 게임
# 예시 코드
def solution(board, moves):
# ➊ 각 열에 대한 스택을 생성합니다.
lanes = [[ ] for _ in range(len(board[0]))]
# ➋ board를 역순으로 탐색하며, 각 열의 인형을 lanes에 추가합니다.
for i in range(len(board) - 1, -1, -1):
for j in range(len(board[0])):
if board[i][j]:
lanes[j].append(board[i][j])
# ➌ 인형을 담을 bucket을 생성합니다.
bucket = [ ]
# ➍ 사라진 인형의 총 개수를 저장할 변수를 초기화합니다.
answer = 0
# ➎ moves를 순회하며, 각 열에서 인형을 뽑아 bucket에 추가합니다.
for m in moves:
if lanes[m - 1]: # 해당 열에 인형이 있는 경우
doll = lanes[m - 1].pop( )
if bucket and bucket[-1] == doll: # ➏ 바구니에 인형이 있고,
# 가장 위에 있는 인형과 같은 경우
bucket.pop( )
answer += 2
else: # ➐ 바구니에 인형이 없거나, 가장 위에 있는 인형과 다른 경우
bucket.append(doll)
return answer
# 참고해서 수정한 내 코드
def solution(board, moves):
N = len(board)
bucket = [[] for _ in range(N)]
for i in range(N-1, -1, -1):
for j in range(N):
if board[i][j]: bucket[j].append(board[i][j])
answer = 0
for m in moves:
if bucket[m-1]:
n = bucket[m-1].pop()
if bucket and n == bucket[-1]:
bucket.pop()
answer += 2
else:
bucket.append(n)
return answer
for문을 range(N-1, -1, -1)하기 전에 board[j][i]로 만들었다가, 수정후에는 반영을 안해서 결과가 이상하게 나왔었다.
이중 for문 연습하자.
문제14. 표 편집
https://cafe.naver.com/dremdeveloper/1001
스택을 활용하는 경우
이전 포스팅에서 스택에 대해 알아봤습니다. 그렇다면 이 스택은 도대체 어디서 활용되는 걸까요? 일상 생활에서도 자주 접할 수 있는 스택은, 우리가 생각하는 것보다 훨씬 다양...
cafe.naver.com
https://cafe.naver.com/dremdeveloper/985
재귀의 다양한 예시 - 하노이탑
이전 포스팅에서는 재귀의 정의, 재귀를 설계하는 법, 간단한 예시에 대해 알아봤습니다. 혹시 재귀에 대해 잘 모르시는 분들은 아래 포스팅 부터 읽고 와주시면 좋습니다. 이번...
cafe.naver.com
https://cafe.naver.com/dremdeveloper/984
재귀의 정의 및 개념
[재귀함수의 정의] Wiki를 찾아보니 재귀(recursion)의 정의는 아래와 같습니다. 프로그래밍 관점에서 보면 보통 재귀라는 용어는 함수에서 많이 사용되지요. 즉 위...
cafe.naver.com
문제10 괄호 회전하기
# 문제 10 괄호 회전하기★ 정답률 _ 64% | 저자 권장 시간 _ 30분 | 권장 시간 복잡도 _ O(N2) | 출제 _ 월간 코드 챌린지 [문제 URL](https:/…
wikidocs.net
'algorithm > CodingTest' 카테고리의 다른 글
| Java 코딩테스트:: Java 기본 문법 (0) | 2024.06.26 |
|---|---|
| SQL 코딩테스트 01: WHERE절, HAVING절, 윈도우 함수, CTE, LEFT JOIN (0) | 2024.06.20 |
| [코딩테스트 합격자 되기 - 2주차] 배열 (프로그래머스 문제 풀이) (1) | 2024.01.10 |
| [코딩테스트 합격자 되기 - 1주차] 알고리즘의 효율 분석, 코딩테스트 필수문법 (2) | 2024.01.07 |
| C++ 알고리즘:: 다이나믹 프로그래밍 (0) | 2021.10.30 |
