우선순위 큐

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 디스크 컨트롤러 문제 링크 ...

2023년 8월 2일 알고리즘 문제풀이 백준 11000 문제 링크 1차 시도 나의 생각 각 수업을 시작하는 시간을 기준으로 정렬하되, 끝나는 시간을 heap에 넣는다. 반복문으로 순회하며 지금 시작할 수업의 시간이 배열에 들어있는 수업 중 끝나는 시간이 가장 빠른 수업의 종료 시간과 비교하였다. 종료 한 후 시작되면 추가적인 강의실이 필요 없다. 하지만 수업이 끝나지 않은 채 다음 수업이 시작된다면 새로운 강의실이 필요하다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 import sys from heapq import heappush, heappop, heappushpop n = int(sys.stdin.readline()) classes = [] for _ in range(n): s,t = map(int,sys.stdin.readline().split()) classes.append([s,t]) classes.sort() heap = [] cnt = 1 for i in range(n): now_class = classes[i] if not heap: heappush(heap,now_class[1]) else: while heap: end_time = heap[0] if now_class[0] >= end_time: heappop(heap) else: break heappush(heap,now_class[1]) cnt = max(cnt,len(heap)) print(cnt)

2023년 7월 30일 알고리즘 문제풀이 백준 5904번 문제 링크 1차 시도 나의 생각 재귀 함수를 통해 각 문자열을 구할 수 있었다. 또한 그 문자열의 길이도 규칙적이므로 몇번째 재귀에서 n번째 문자열이 등장하는지를 알아내어 그 문자열의 index를 통해 구하였다. 하지만 메모리 초과와 시간 초과로 인하여 오답처리 되었다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys sys.setrecursionlimit(10**6) n = int(sys.stdin.readline()) def moo(k): if k == 0: return 'moo' return moo(k-1)+'m'+'o'*(k+2)+moo(k-1) i = -1 while True: i += 1 tmp = moo(i) if len(tmp) >= n: print(tmp[n-1]) break 2차 시도 나의 생각 문자열을 구하면 안된다고 생각하였다. 다음 문자열이 이전 차례의 문자열 두개에 하나의 규칙적인 문자가 껴있는 형태라는 사실에 집중하였다. 예를 들어 S(10)의 몇번째 문자열인지는 S(9)의 문자열을 통해 알 수 있다. 원리는 다음과 같다. ...

2023년 7월 29일 알고리즘 문제풀이 백준 13334번 문제 링크 1차 시도 나의 생각 사람들의 사무실 과 집 둘 중 좌표가 작은 것을 먼저 오게 한 후, 그것을 오름차순으로 배열에 정리하였다. 각 지점을 철로의 시작점으로 삼아 모든 case를 검사하며 최댓값을 업데이트했다. 다 검사해버리니 당연히 시간초과… 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) people = [] for _ in range(n): h,o = map(int,sys.stdin.readline().split()) if h <= o: heappush(people,[h,o]) else: heappush(people,[o,h]) d = int(sys.stdin.readline()) ans = 0 while people: cnt = 0 x = people[0][0] for person in people: if person[0] >= x and person[1] <= x+d: cnt += 1 ans = max(ans,cnt) heappop(people) print(ans) 2차 시도 나의 생각 어떤 사람의 집과 사무실의 거리는 철로의 길이인 d보다 멀 수도있다. 이 사람은 철로를 어디에 설정하든 이용할 수 없다. 따라서 입력을 받을 때 이런 케이스를 지우려고 했다. 또한 정렬을 해버린 만큼 굳이 필요하지 않은 조건들도 제거하였다. 하지만 예외케이스가 있는지 오답처리되었다. ...

2023년 7월 28일 알고리즘 문제풀이 백준 1655번 문제 링크 1차 시도 나의 생각 양 끝과 중간이라는 생각에 deque을 사용하면 어떨까 생각하고 코드를 작성했다. 생각해보니 중간과 끝 사이에 새로운 숫자를 집어넣어야 하는데… 다행히 우선순위 큐, 최소 heap이 생각났지만 너무 늦게 생각나서 코드 작성을 못했다. 다음 시도에선 해봐야지. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys from heapq import heappop, heappush, heappushpop n = int(sys.stdin.readline()) big = [] mid = [] small = [] for _ in range(n): num = int(sys.stdin.readline()) if not mid: mid.append(num) print(num) continue if num >= mid: tmp = heappushpop(big,num) mid.append(tmp) print(mid[0]) else: tmp = heappushpop(small,-num) mid.append(-tmp) mid.sort() print(mid[0]) 2차 시도 나의 생각 heap을 사용하였다. 가운데 값을 기준으로 크냐 작냐에 따라 경우가 나눠질거라고 생각해서 가운뎃값보다 작은 heap, 가운뎃값을 담은 heap, 더 큰 heap 세개로 나누어서 생각했다. 하지만 문제에서 나왔듯 가운데 값이 전체 숫자의 갯수에 따라 2개일 수도 한 개 일수도 있어서 가운데를 담는 배열을 1로 유지해야할지, 혹은 큰 배열과 작은 배열의 수를 갖게 유지해야할 지 여러모로 헷갈렸다. 차라리 하나를 우직하게 했으면 정답은 나왔으려나.. 여러 생각에 헤메다가 시간만 허비하고 코드를 완성하지 못했다. ...