최소힙

2023년 8월 31일 알고리즘 문제풀이 문제 1 백준 16439 문제 링크 1차 시도 나의 생각 세 종류의 치킨을 고르는 것은 조합(Combination)을 이용했다. 근데 라이브러리를 사용하지 않고 3중 for문으로 구현했다. 라이브러리 쓰는 법도 익혀야지.. 어쩄든 한 사람은 세 종류의 치킨 중 선호도가 가장 높은 것으로 점수를 나타내니 최소힙을 이용하되 음수로 바꾼 후 넣은 후 heappop하여 점수를 구했다. 그리고 각 조합 때마다 현재까지 최고 점수랑 비교하며 업데이트 해주었다. 결과 정답 코드 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 27 28 29 30 31 32 import sys from heapq import heappop, heappush n, m = map(int, sys.stdin.readline().split()) graph = [] for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split()))) def cal(): max_val = 0 for i in range(m): for j in range(m): if j == i: continue for k in range(m): ans = 0 if k == i or k == j: continue for person in range(n): arr = [] heappush(arr, -1*graph[person][i]) heappush(arr, -1*graph[person][j]) heappush(arr, -1*graph[person][k]) tmp = heappop(arr) tmp *= -1 ans += tmp max_val = max(max_val, ans) return max_val answer = cal() print(cal()) 문제 2 백준 1939 문제 링크 ...

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로 유지해야할지, 혹은 큰 배열과 작은 배열의 수를 갖게 유지해야할 지 여러모로 헷갈렸다. 차라리 하나를 우직하게 했으면 정답은 나왔으려나.. 여러 생각에 헤메다가 시간만 허비하고 코드를 완성하지 못했다. ...