2023년 8월 17일 알고리즘 문제풀이
문제 1 올바른 괄호
1차 시도
나의 생각
문자열을 앞부터 한글자씩 스택에 넣는다. 여는 괄호’(‘는 무조건 넣고, 닫는 괄호’)’는 경우가 나누어진다. 스택에 마지막으로 들어가있는 원소가 여는 괄호면 합쳐서 올바른 괄호니 마지막에 들어간것을 pop해준다. 스택이 비어있으면 올바른 괄호가 아니라는 의미이다.
단어의 모든 글자를 순회했는데 아직 스택에 괄호가 남아있다면 올바르지 못한 괄호이다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque
def solution(s):
answer = True
arr = list(s)
q = deque()
for i in range(len(s)):
if arr[i] == '(':
q.append(arr[i])
else:
if not q or q[-1] != '(':
return False
elif q[-1] == '(':
q.pop()
continue
if q:
return False
else:
return answer
문제 2 디스크 컨트롤러
1차 시도
나의 생각
지금 수행중인 요청이 끝나기 전에 들어온 요청들을 힙에 담는다. 단, index 위치를 바꿔 소요되는 시간이 먼저 오도록 한다. 최소힙을 통하여 힙에 담긴 요청들 중 작업 시간이 가장 짧은것 부터 처리한다.
start는 현재 작업중인 것의 요청 시간, now는 현재 작업중인 것이 끝나는 시간이라고 생각하면 이해가 더 쉽다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from heapq import heappop, heappush
def solution(jobs):
answer,now,i = 0,0,0
start = -1
waiting = []
while i < len(jobs):
for j in jobs:
if start < j[0] <= now:
heappush(waiting, [j[1],j[0]])
if waiting:
working = heappop(waiting)
start = now
now += working[0]
answer += (now-working[1])
i += 1
else:
now += 1
answer //= len(jobs)
return answer
문제 3 백준 1003
1차 시도
나의 생각
피보나치 수열이기 때문에 간단하게 다이나믹 프로그래밍을 이용하면 될 것이라고 생각했다. 하지만 시간초과가 문제였다. 각 결과를 배열에 저장하는 방법을 사용하려 했으나 결국 시간을 줄이지 못해서 오답처리 됐다. 아예 함수를 호출하지 않아야 할 것 같다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import sys
sys.setrecursionlimit(10**9)
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
cnt = 0
def fibo(x):
global cnt
if x == 0:
cnt += 1
return 0
elif x == 1:
return 1
else:
return fibo(x-1)+fibo(x-2)
ans = fibo(n)
print(cnt,ans)
2차 시도
나의 생각
함수를 호출하지 않아야 했다. 값을 도출하지 않고 1과 0의 갯수만 세는 문제이기 때문에 가능할 것 같다. 0부터 규칙을 직접 찾아봤더니 n일 때 1이 호출되는 횟수는 n-1일 때 0이 호출되는 횟수와 1이 호출되는 횟수의 합과 같았다. n일 때 0이 호출되는 횟수는 n-1일 때 1이 호출되는 횟수와 같았다. 이를 이용해 배열을 만들었더니 해결되었다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
import sys
sys.setrecursionlimit(10**9)
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
arr = [[0, 0] for _ in range(n+1)]
arr[0][0] = 1
for i in range(1, n+1):
arr[i][0] = arr[i-1][1]
arr[i][1] = arr[i-1][0] + arr[i-1][1]
print(arr[n][0], arr[n][1], sep=' ')
