줴림이 공부하줴림
[SWEA] [파이썬 SW 문제해결 기초] 4. Stack2 본문
[계산기]
문자열로 이뤄진 계산식 => 스택 이용하여 계산 가능
- 일반적인 계산 방법: 중위표기법의 수식을 후위표기법으로 변경 후 스택을 이용하여 계산
Step 1: 중위표기식의 후위표기식 변환 방법
1) 입력 받은 중위표기식에서 토큰을 읽음
2) 토큰이 피연산자이면 토큰 출력
3) 토큰이 연산자(괄호 포함)일 경우
- 우선순위가 높으면 → 스택에 push
- 우선순위가 안 높으면 → 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지 스택에서 pop한 후 토큰의 연산자 push
- top에 연산자가 없으면 push
4) 토큰이 오른쪽 괄호 ')'일 경우
- 스택 top에 왼쪽 괄호 '('가 올 때까지 스택에 pop 연산 수행
- pop한 연산자를 출력
- 왼쪽 괄호를 만나면 pop만 하고 출력은 X
5) 중위표기식에 더 읽을 것이 없다면 중지, 있다면 1부터 반복
6) 스택에 남아 있는 연산자들 모두 pop하여 출력
- 스택 밖에 있는 왼쪽 괄호일수록 우선순위 높음
더럽게 길고 복잡하다.
Step 2: 후위표기법의 수식을 스택에 이용하여 계산
1) 피연산자를 만나면 스택에 push
2) 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop하여 연산하고, 연산결과를 다시 스택에 push함
3) 수식이 끝나면, 마지막으로 스택을 pop하여 출력
근데! eval(수식) 함수를 쓰면 간단하게 계산할 수 있다는 사실!!!
- 올바른 수식이 아닌 경우 => SyntaxError
★[백트래킹]
백트래킹(Backtracking): 해를 찾는 중에 '막히면', (즉, 해가 아니면) 되돌아가서 다시 해를 찾아가는 기법
- 최적화 문제 & 결정 문제(ex. 미로 찾기, n-Queen, Map coloring, Subset Sum 등) 해결 가능
ex) 미로 찾기 문제에 백트래킹 활용
1) 입구와 출구가 주어진 미로에서 입구부터 출구까지의 경로를 찾는 문제
2) 이동할 수 있는 방향은 4방향으로 제한
- 2차 리스트에 표현된 미로: 통로는 0, 벽은 1로 표시
이동상황을 스택에 push하여 저장 (이때 시계방향 or 반시계방향으로 이동에 우선순위 둘 수 있음)
이동이 불가능할 때까지 계속해서 진행
이동이 불가능해질 경우: 스택에 있던 이동상황을 pop하면서 뒤로 이동 후 다시 이동
※ 백트래킹 vs. 깊이 우선 탐색
| 백트래킹 | 깊이 우선 탐색 |
| - 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음 = 시도 횟수 감소 - 가지치기(Prunning): 유망하지 않은 노드는 더 이상 탐색 X - 불필요한 경로의 조기 차단 (해답이 될 수 없으면 유망하지 않다.) - N! 가지 경우의 수 문제: 일반적으로 경우의 수 감소, but 여전히 최악의 경우는 지수함수 시간 => 처리 불가능 - 모든 후보를 검사하지 않음 |
- 모든 경로를 추적 - N! 가지의 경우의 수를 가진 문제: 처리 불가능 - 모든 후보를 검사 |
※ 백트래킹을 이용한 알고리즘의 절차
1) 상태 공간 Tree의 깊이 우선 검색을 실시
2) 각 노드가 유망한지를 점검
3) 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속
※ 일반 백트래킹 알고리즘
# power set을 구하는 백트래킹 알고리즘
def backtrack(a, k, input):
global MAXCANDIDATES
c = [0] * MAXCANDIDATES
if k == input: # 원하는 상태에 도달했으면
process_solution(a, k) # 결과를 출력한다.
else: # 아니라면?
k += 1
ncandidates = construct_candidates(a, k, input, c) # 후보군 생성을 위한 함수 호출
for i in range(ncandidates):
a[k] = c[i] # 후보군 중 하나 선택
backtrack(a, k, input) # 다시 재귀함수 호출해서 backtracking 계속함
# backtrack하기 위한 후보군을 구하는 함수를 따로 구현
def construct_candidates(a, k, input, c):
c[0] = True # 해당 원소가 출현
c[1] = False # 해당 원소가 미출현
return 2# 순열을 구하는 백트래킹 알고리즘
def backtrack(a, k, input):
global MAXCANDIDATES
c = [0] * MAXCANDIDATES
if k == input:
for i in range(1, k+1):
print(a[i], end=" ")
print()
else:
k += 1
ncandidates = construct_candidates(a, k, input, c):
for i in range(ncandidates):
a[k] = c[i]
backtrack(a, k, input)
# 후보군을 구하기 위한 함수
def construct_candidates(a, k, input, c):
in_perm = [False] * NMAX
for i in range(1, k):
in_perm[a[i]] = True
ncandidates = 0
for i in range(1, input+1):
if in_perm[i] == False:
c[ncandidates] = i
ncandidates += 1
return ncandidates
★[분할 정복]
설계 전략
- 분할(Divide): 해결할 문제를 여러 개의 작은 부분으로 나눔
- 정복(Conquer): 나눈 작은 문제를 각각 해결
- 통합(Combine): (필요하다면) 해결된 해답을 모음
# 분할 정복 기반의 알고리즘: O(log2n)
def Power(Base, Exponent):
if Exponent == 0 or Base == 0:
return 1
if Exponent % 2 == 0: # 짝수일 때
NewBase = Power(Base, Exponent/2)
return NewBase*NewBase
else: # 홀수일 때
NewBase = Power(Base, (Exponent-1)/2)
return (NewBase*NewBase)*Base# 퀵 정렬 알고리즘
def quickSort(a, start, end):
if start < end:
p = partition(a, start, end)
quickSort(a, start, p-1)
quickSort(a, p+1, end)
# 주어진 리스트에서 피봇을 구하는 알고리즘
def partition(a, start, end):
pivot = (start + end) // 2
L = begin
R = end
while L < R:
# 리스트의 왼쪽에서 오른쪽으로 이동하며 pivot과 비교 조사
while (a[L] < a[pivot] and L < R):
L += 1
while (a[R] >= a[pivot] and L < R):
R -= 1
if L < R:
if L==pivot:
pivot = R
a[L], a[R] = a[R], a[L] # pivot보다 큰 값, 작은 값을 각각 찾으면 둘이 위치 교환
# 리스트의 오른쪽에서 왼쪽으로 이동하며 pivot과 비교 조사
# => pivot보다 작은 값: 왼쪽 / 큰 값: 오른쪽
a[pivot], a[R] = a[R], a[pivot] # pivot보다 큰 값을 못 찾고 L=R이면, pivot과 위치 교환
return R
★4874. Forth 코드의 연산 결과를 출력하는 프로그램을 만드시오. 만약 형식이 잘못되어 연산이 불가능한 경우 ‘error’를 출력한다.
def postFix(strings):
stack = []
i = 0 # 스택 인덱스
operator = ['+', '-', '*', '/']
res = '' # 반환값
tmp = 0 # 잠시 계산할 때 쓸 임시 변수
for i in range(len(strings)-1): # 마지막 '.' 빼버림
if strings[i] not in operator: # s가 숫자인 경우 => stack에 추가
stack.append(strings[i])
# s가 연산자 + 숫자 2개 이상 있는 스택 => 계산 수행 후 stack에 추가
elif (strings[i] in operator) and (len(stack) >= 2):
if strings[i] == '+':
tmp = int(stack.pop(-2)) + int(stack.pop(-1))
stack.append(str(tmp))
elif strings[i] == '-':
tmp = int(stack.pop(-2)) - int(stack.pop(-1))
stack.append(str(tmp))
elif strings[i] == '*':
tmp = int(stack.pop(-2)) * int(stack.pop(-1))
stack.append(str(tmp))
elif strings[i] == '/':
tmp = int(stack.pop(-2)) // int(stack.pop(-1))
stack.append(str(tmp))
else: # 이도저도 아니면 error
res = 'error'
return res # 바로 반환
if len(stack) == 1: # 스택에 진짜 최종 값만 남았을 때
res = stack.pop()
else:
res = 'error'
return res # 바로 반환
return res
T = int(input())
for test_case in range(1, T+1):
strings = list(map(str, input().split()))
res = postFix(strings)
print(f"#{test_case} {res}")처음엔 진짜 모르겠다 싶었는데, 그래도 적으면서 생각 좀 해보니까 뭔가 생각이란 걸 할 수 있게 되더라...
처음 접근법은 문자열 내 문자를 순서대로 스택에 넣고 비교하는 거였는데, 계속 오류가 나서 그냥 쉽게 list로 받아서 풂.
숫자인 경우 먼저 스택에 추가하고(처음에 이거 깜빡하고 안 넣어서 오류났음), 연산자이면서 스택 크기가 2 이상이면 연산한 후에 스택에 넣고, 이도저도 아니면 바로 res 리턴해주고.
그리고 마지막에는 스택에 진짜 최종 1개 값만 있으면 리턴, 다른 나머지 경우는 error 리턴.
4875. NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하는 프로그램을 작성하시오. 도착할 수 있으면 1, 아니면 0을 출력한다. 주어진 미로 밖으로는 나갈 수 없다.
밑에 나오는 4881 문제를 먼저 풀고 돌아왔더니, 이 문제도 백트래킹으로 풀 수 있을 것 같다고 생각했다.
# 오류 발생한 코드 #
def root_find(x, y):
global answer
if maze[x][y] == 3: # 목적지 도착하면 1 리턴
answer = 1
return answer
if maze[x][y] == 1:
answer = 0
return answer
for dx, dy in movement:
nx, ny = x+dx, y+dy
if (0 <= nx <= N-1) and (0 <= ny <= N-1):
if not visited[nx][ny]:
visited[nx][ny] = True
root_find(nx, ny)
visited[nx][ny] = False
T = int(input())
for test_case in range(1, T+1):
N = int(input())
maze = [list(map(int, input().strip())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
movement = [[0, -1], [1, 0], [0, 1], [-1, 0]]
for i in range(N):
for j in range(N):
if maze[i][j] == 2:
start_x = i
start_y = j
break
answer = 0
root_find(start_x, start_y)
print(f"#{test_case} {answer}")근데 테스트 케이스 1번에서부터 오류가 나서 뭐가 문제지 싶어서 보다가, 설마 'if maze[x][y] == 1' 구문 때문인가 싶어서 자세히 살펴봤다. 마음에 걸린 부분은 벽을 만나면 바로 0을 리턴하는 부분이었는데, 사실 벽을 만나면 다시 길을 찾아야 하지, 포기하는 게 아니잖아?? 그래서 for 문 안에 조건을 추가해서 수정해줬더니 패스!!
## 최종 코드 ##
def root_find(x, y):
global answer
if maze[x][y] == 3: # 목적지 도착하면 1 리턴
answer = 1
return answer
for dx, dy in movement:
nx, ny = x+dx, y+dy
if (0 <= nx <= N-1) and (0 <= ny <= N-1):
if not visited[nx][ny] and maze[nx][ny] != 1: # 수정한 부분
visited[nx][ny] = True
root_find(nx, ny)
visited[nx][ny] = False
T = int(input())
for test_case in range(1, T+1):
N = int(input())
maze = [list(map(int, input().strip())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
movement = [[0, -1], [1, 0], [0, 1], [-1, 0]]
for i in range(N):
for j in range(N):
if maze[i][j] == 2:
start_x = i
start_y = j
break
answer = 0
root_find(start_x, start_y)
print(f"#{test_case} {answer}")
4880. 사다리 게임이 지겨워진 알고리즘 반 학생들이 새로운 게임을 만들었다. 가위바위보가 그려진 카드를 이용해 토너먼트로 한 명을 뽑는 것이다. 게임 룰은 다음과 같다. 1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다. 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는데, i번부터 j번까지 속한 그룹은 파이썬 연산으로 다음처럼 두개로 나눈다. 두 그룹이 각각 1명이 되면 양 쪽의 카드를 비교해 승자를 가리고, 다시 더 큰 그룹의 승자를 뽑는 방식이다. 다음은 4명이 카드를 비교하는 경우로, 숫자 1은 가위, 2는 바위, 3은 보를 나타낸다. 만약 같은 카드인 경우 편의상 번호가 작은 쪽을 승자로 하고, 처음 선택한 카드는 바꾸지 않는다. N명이 학생들이 카드를 골랐을 때 1등을 찾는 프로그램을 만드시오.
'''
N: 학생 수, 카드 수
1) 전체를 2개의 그룹으로 나눔 => 승자끼리 카드 비교
2) 각각 1명이 되면 양쪽의 카드를 비교해 승자를 가림
3) 번호가 작은 쪽이 승자
4) 가위바위보가 그려진 카드 (1: 가위, 2: 바위, 3: 보)
'''
def tournament(i, j):
# 그룹 내에 1명만 남음 => 가위바위보
if i==j:
return i
else:
left = tournament(i, (i+j)//2)
right = tournament((i+j)//2+1, j)
return win(left, right)
def win(i, j):
# 가위바위보 하기
if arr[i] == arr[j]: # 비긴 경우 => 번호 작은 쪽이 승자
return min(i,j)
elif arr[i] == 1: # 가위인 경우
if arr[j] == 2: # vs. 바위
return j
else: # vs. 보
return i
elif arr[i] == 2: # 바위인 경우
if arr[j] == 1: # vs.가위
return i
else:
return j
elif arr[i] == 3: # 보인 경우
if arr[j] == 1:
return j
else:
return i
T = int(input())
for test_case in range(1, T+1):
N = int(input()) # 인원 수
arr = [0] + list(map(int, input().split()))
answer = tournament(1, N)
print(f"#{test_case} {answer}")막상 다시 보니까 생각보다 풀 수 있을 정도였다. 아이디어는 바로바로 떠오르진 않았지만... 코드를 어떻게 작성하면 좋을지 구상하는 연습을 좀 많이 해야 할 듯.
★4881. NxN 배열에 숫자가 들어있다. 한 줄에서 하나씩 N개의 숫자를 골라 합이 최소가 되도록 하려고 한다. 단, 세로로 같은 줄에서 두 개 이상의 숫자를 고를 수 없다. 조건에 맞게 숫자를 골랐을 때의 최소 합을 출력하는 프로그램을 만드시오.
일단 이 문제가 백트래킹이고, n-Queen과 비슷한 유형이라는 건 알겠다. 근데 어떻게 구현해야할지 몰라서 인터넷의 도움을 좀 받았는데, 내가 참고한 코드는 전역변수를 사용하더라. 전역변수에 익숙하지 않은 나는 안 사용하는 방식으로 바꿈.
# 오류 난 코드 #
def min_sum(idx, total, visited):
if idx == N:
return total
min_total = 10000
for i in range(N):
if i not in visited:
visited.append(i)
res = min_sum(idx+1, total+arr[idx][i], visited)
visited.pop()
if res < min_total:
min_total = res
return min_total
T = int(input())
for test_case in range(1, T+1):
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = []
answer = min_sum(0, 0, visited)
print(f"#{test_case} {answer}")그리고 제한시간 초과로 Fail이 떴다ㅋ. 이번엔 또 어디가 문제니? GPT한테 넣어서 물어보니까 Prunning이 빠져있다고 함. 그렇다면 Prunning은 어떻게 해줘야 하는데?
지금까지 합이 더 이미 최소보다 더 크면 볼 필요가 없기에 'if total >= answer:' 문을 넣어줘야 한다고 함! 기존에 참고했던 코드에 있긴 했는데 그게 무슨 의미인지 몰라서 뺐었는데, 가지치기였구나...
근데 결국 전역변수를 쓰지 않으면 계속 제한시간 초과가 뜬다. 이 문제도 나중에 다시 풀어봐야할 듯...
## 최종 코드 ##
def min_sum(idx, total, visited):
# idx: 현재 행, total: 누적 합, visited: 방문 열
global min_val # 맨 처음에는 최솟값이 엄청 크게 설정되어 있음
if idx == N: # 행이 맨 끝까지 다 돌았을 때
if min_val > total: # 최솟값이 누적 합보다 크면
min_val = total # 누적 합을 최솟값으로 만들어주고
return min_val # min_val 리턴
if total >= min_val: # 계산 중간에 누적 합이 최솟값보다 크거나 같다.
return min_val # 바로 가지치기 (최솟값 리턴)
for i in range(N):
if i not in visited: # 방문하지 않았다면
visited.append(i) # 방문 표시하고
min_sum(idx+1, total+arr[idx][i], visited) # 다음 행으로 넘어감 / 누적 합 += 방금 방문한 노드
visited.pop() # 다시 뒤로 back할 때
T = int(input())
for test_case in range(1, T+1):
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = []
min_val = 100
min_sum(0, 0, visited)
print(f"#{test_case} {answer}")
'Study > SWEA' 카테고리의 다른 글
| [SWEA] [파이썬 SW 문제해결 기초] 6. Tree (0) | 2025.04.07 |
|---|---|
| [SWEA] [파이썬 SW 문제해결 기초] 5. Queue (0) | 2025.04.07 |
| [SWEA] [파이썬 SW 문제해결 기초] 3. Stack1 (1) | 2025.04.05 |
| [SWEA] [파이썬 SW 문제해결 기초] 2. List2 (0) | 2025.04.05 |
| [SWEA] [파이썬 SW 문제해결 기초] 1. List1 (0) | 2025.04.04 |
