문제
| 난이도 | 번호 | 문제 이름 |
|---|---|---|
 | 1935 | 후위 표기식2 |
| 3273 | 두 수의 합 |
 | 20002 | 사과나무 |
 | 4095 | 최대 정사각형 |
HOW TO SOLVE
- 후위 표기식2 :
- 두 수의 합 :
- 사과나무 :
- 최대 정사각형 :
후위 표기식2
# chr(i) => i에 해당하는 아스키코드 문자 반환
# ord(i) => i에 해당하는 아스키코드 숫자 반환
from collections import defaultdict
n = int(input())
postfix = list(input())
stack = []
dic = defaultdict(int)
for i in range(65, 65 + n):
dic[chr(i)] = int(input())
for x in postfix:
if x.isalpha():
stack.append(dic[x])
else:
if x == '+':
stack.append(stack.pop() + stack.pop())
elif x == '-':
stack.append(stack.pop(-2) - stack.pop())
elif x == '*':
stack.append(stack.pop() * stack.pop())
elif x == '/':
stack.append(stack.pop(-2) / stack.pop())
print("{:.2f}".format(stack.pop()))풀이
후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하기
스택을 사용한 단순한 구현 문제이다.
문제에서 각 피연산자에 대응하는 값이 입력으로 주어지는 데, 이때 A부터 순서대로 주어진다.
이를 딕셔너리에 저장했다.
후위 표기식이 무엇이고 어떻게 연산을 해야하는지는 구글링을 통해 찾았다.
메인 로직은 단순하다.
먼저, 입력으로 받은 후위 표기식을 순회하면서,
현재 원소가 알파벳이라면 스택에 추가한다.
만약, 알파벳이 아니라면 즉, 연산자라면 스택에서 원소 2개를 pop() 한다.
(단, 연산자 별로 계산 순서가 다르기 때문에, pop() 을 적절히 사용해야 한다.)
최종적으로는 스택에 계산 결과가 1개 존재하므로 이를 출력한다.
chr(x) : x에 해당하는 아스키코드 문자를 반환한다.
ord(x) : x에 해당하는 아스키코드 숫자를 반환한다.소수점 출력은,
{ x:.yf }.format(..)를 사용한다.
x는 format의 인자의 위치를 의미하고,
y는 소수점 자릿수를 의미한다.
(y == 2라면, 소수점 2번째 자리까지 출력하겠다는 의미)
두 수의 합
n = int(input())
seq = list(map(int, input().split()))
x = int(input())
# 투 포인터를 사용하기 위해 정렬
seq.sort()
# 포인터 2개, 만족하는 쌍의 개수
l, r, cnt = 0, n - 1, 0
while l < r:
if seq[l] + seq[r] == x: # 만족하는 쌍을 찾았다면
cnt += 1 # 횟수 증가
# r을 줄여서 다른 쌍을 찾는다.
# l은 늘리지 않는 이유는 -> r - 1이 r과 같은 수라면, (l, r - 1)이 같은 쌍이 되는데 (l + 1, r - 1)로 같은 쌍인지 아닌지 카운트하지 못하기 떄문.
r -= 1
elif seq[l] + seq[r] > x: # 합이 x보다 크다면
r -= 1 # r을 줄여서 합을 줄인다.
else: # 합이 x보다 작다면
l += 1 # l을 늘려서 합을 늘린다.
print(cnt)풀이
자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하기
조건 :
1 ≤ n ≤ 100000,1 ≤ x ≤ 2000000
조건에 의해서 으로 시간초과가 발생하므로, 다른 알고리즘을 찾아야 한다.
처음에는 이진 탐색을 생각했는데 기준으로 잡을만한게 뚜렷하지 않았고, 이진탐색은 적절하지 않은 것 같아서 다른 알고리즘을 생각 해야했다.
떠오른 풀이는 투 포인터 알고리즘이다.
각 포인터를 왼쪽 끝과 오른쪽 끝에 두고, 두 포인터가 가리키는 수들의 합을 구해서 x와 같은지, 큰지, 작은지를 판단한다.
여기서 투 포인터 알고리즘은 이진탐색과 마찬가지로, 반드시 리스트를 먼저 정렬해야 한다.
또 유의해야 할 점은, 만족하는 쌍을 찾았을 때 l과 r 모두 줄이거나 늘리면 안되고, 둘 중 하나만 값을 바꿔야 한다.
예를 들어 리스트가 수열 : [1, 2, 5, 7, 8, 12, 12], x = 13 라고 하자.
처음에는 (1, 12)로 하나를 찾았다.
만약 l과 r 모두를 갱신하면 다음으로는 2와 12를 가리킨다.
하지만, 리스트를 보면 (1, 12)의 쌍이 하나 더 있는 것을 알 수 있다.
따라서, l과 r 모두를 갱신하면 놓치는 쌍이 존재할 수 있다.
코드의 시간복잡도 :
- while문(투 포인터) :
- sort() :
사과나무
# 주어진 구간으로 이루어진 정사각형의 총이익
def helper(prefix_list, a, b, c, d):
return prefix_list[c][d] - (prefix_list[a - 1][d] + prefix_list[c][b - 1]) + prefix_list[a - 1][b - 1]
n = int(input())
prefix_list = [[-1001] * (n + 1) for _ in range(n + 1)] # 누적합 리스트
# (i, j)의 누적합 구하기
for i in range(1, n + 1):
graph = list(map(int, input().split()))
for j in range(1, n + 1):
prefix_list[i][j] = prefix_list[i][j - 1] + prefix_list[i - 1][j] - prefix_list[i - 1][j - 1] + graph[j - 1]
_max = int(-1e9)
# 정사각형의 크기
for k in range(n):
# (a, b) : 시작점
for a in range(1, n - k + 1):
for b in range(1, n - k + 1):
c, d = a + k, b + k # (c, d) : 끝점
# (a, b) ~ (c, d)인 정사각형의 총이익 갱신
_max = max(_max, helper(prefix_list, a, b, c, d))
print(_max)풀이
N * N 과수원에서 K × K 의 크기의 정사각형 모양으로만 수확이 가능하다. 이때 얻을 수 있는 최대 총이익을 구하기.
조건 :
만약, K마다 모든 경우의 수를 비교하게 되면, 총 시간 복잡도는 이다.
- k = 1 ... N * N번 비교
- k = 2 ... (N - 1) * (N - 1)
- k = 3 ... (N - 2) * (N - 2)
- k = N ... (N - (N - 1)) * (N - (N - 1))
이므로 이를 모두 곱하면 임을 알 수 있다. (아마도...)
따라서 다른 알고리즘을 생각해야 한다.
정사각형을 과수원에 올려놓는 시뮬레이션을 하면서,
이전에 배웠던 2차원 리스트의 누적합이 떠올랐다.
이를 적용하면 최악의 경우에도 시간복잡도가 이므로 충분히 통과할 수 있다.
최대 정사각형
코드 #1, #2 모두 DP로 해결
코드 #1
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
dp[i][j] = graph[i][j]
for i in range(1, n):
for j in range(1, m):
if graph[i][j]:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
print(max(map(max, dp)))풀이
정사각형 관련 문제를 풀어본 기억이 있어서 DP가 생각났다.
정사각형을 이루는 조건은, 현재 (i, j) == 1 일 때
(i - 1, j) == 1: 위쪽(i, j - 1) == 1: 왼쪽(i - 1, j - 1) == 1: 왼쪽 위 대각선
를 모두 만족해야 한다.
그리고 셋 중에서 가장 작은 값에 1을 더한 값이 dp[i][j] 의 값이 된다.
이 로직은 단순하게 생각하면 당연하다.
예를 들어, 셋 다 1이라면 현재 위치까지 포함해서 2 * 2 정사각형이 만들어진다.
| 1 | 1 |
| 1 | 1 |
만약, 하나라도 1이 아니라면 모두 이어지지 않은 끊어진 각각의 사각형이 되므로,
그 중 가장 작은 값(min)이 dp[i][j] 가 된다.
끊어진 각각의 사각형의 예시는 다음과 같다.
| 1 | 1 |
| 0 | 1 |
처음에 최대 정사각형의 크기를 계산할 때 이중-for문 내에,
_max = max(_max, dp[i][j])로 최대 크기를 계산했는데 틀렸다고 나왔다.왜 그런지는 의문이다..
코드 개선
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
dp = [list(map(int, input().split())) for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
if dp[i][j]:
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
print(max(map(max, dp)))코드 #1 에서는
graph와dp를 따로 선언해서 사용했는데dp만 사용해도 상관없다.즉, 입력도 DP에 저장하고 계산도 DP로 수행한다.
코드 #2
while True:
n, m = map(int, input().split())
if n == 0 and m == 0:
break
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * (m + 1) for _ in range(n + 1)]
_max = 0
# (1, 1)부터 시작 => 그래야 정사각형 비교하기 편해짐
for i in range(1, n + 1):
for j in range(1, m + 1):
# 정사각형이 될 수 있을 때
if graph[i - 1][j - 1] == 1:
# 왼쪽, 위, 왼쪽 위 대각선 중 0이 하나라도 있으면 정사각형이 될 수 없다.
# 최솟값이 0일경우 dp[i][j] = 0 + 1 = 1이다.
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
_max = max(_max, dp[i][j]) # 최대 정사각형 크기
print(_max)풀이
코드 #2는 코드 #1과 거의 유사하다.
단, dp 리스트를 입력과 계산을 모두 수행하는 리스트로 사용하고 크기도 (n + 1) * (m + 1) 로 선언한 점이 다르다.
또한, 이중-for문 내에서 조건문도 graph[i - 1][j - 1] == 1 로 graph[i][j] == 1 과는 살짝 다르다.
전체적인 로직은 서로 다르지 않다.
