Programming [Python] (411) 썸네일형 리스트형 #296 백준 파이썬 [11946] ACM-ICPC https://www.acmicpc.net/problem/11946 SOLUTION 문제는 크게 어렵지 않지만 데이터를 저장하고 정렬함에 있어 혼돈이 올 수 있다. acm_icpc 결과 리스트를 [팀][문제 번호][정답 시간, 오답 수]로 3차원 배열을 만들어준다. 정답 시간엔 최댓값 + 1을 넣어준다. 정답이 나오지 않을 경우엔 틀린 문제에 +1을 해준다. 입력 자체가 시간 순으로 들어오므로 AC가 한 번 나온 이후로는 더 이상 틀린 문제를 카운트하지 않는다. 맞힌 문제 내림 차순, 총 시간 오름 차순, 팀 번호 오름차순으로 정렬해준다. 식으로 표현하면 다음과 같다. grade = sorted(grade[1:], key = lambda x: (-x[1], x[2], x[0])) PYTHON CODE n.. #295 백준 파이썬 [11945] 뜨거운 붕어빵 https://www.acmicpc.net/problem/11945 PYTHON CODE N, M = map(int, input().split()) for _ in range(N): print(input()[::-1]) #294 백준 파이썬 [11944] NN https://www.acmicpc.net/problem/11944 PYTHON CODE N, M = map(int, input().split()) N_word = str(N) NN = '' while len(NN) < len(N_word) * N: NN += N_word print(NN[:M]) #293 백준 파이썬 [11943] 파일 옮기기 https://www.acmicpc.net/problem/11943 PYTHON CODE A, B = map(int, input().split()) C, D = map(int, input().split()) print(min(A+D,B+C)) #292 백준 파이썬 [1202] 보석 도둑 - 우선 순위 큐 https://www.acmicpc.net/problem/1202 SOLUTION 우선 순위 큐를 구현한 최대 최소힙을 통해 풀이하였다. 이를 모른다면 공부를 먼저 하고오길 추천한다. 현재 가장 작은 무게를 수용할 수 있는 가방(=capacity) 이하의 모든 보석(capable_gem) 중 가장 값이 큰 것을 뽑아내고 이를 가방이 끝날 때 까지 반복하는 것이 목표다. 다음과 같은 알고리즘을 따른다. 1) Bag의 최솟값을 heappop 해준다. 해당 Bag은 현재의 capacity 즉, 수용량이 된다. 2) 수용량 이하 무게의 모든 보석 Gem을 capable_gem에 무게를 제외한 값만 heappush하여 넣어준다. 3) capacity이하의 모든 무게의 보석을 꺼냈으면 capable_gem(최대 힙.. #291 백준 파이썬 [2220] 힙 정렬 https://www.acmicpc.net/problem/2220 SOLUTION 가장 많은 스왑을 하게 되는 힙 정렬 순서는 어떻게 될까? 노트에 10까지 써보니 n 힙 정렬에서 n을 삭제하면 n-1 힙 정렬과 동일해진다는 것을 알게 되었다. 즉 이전 리스트를 받아 최댓값을 대입했을 때 가장 많은 스왑을 가져가면 되는 것이다. n번 째에 가장 많은 스왑을 일으키기 위해서는 n이 가장 하단 레벨의 1 옆으로 가야한다. 해당 max heap에서 7이 추가 될 경우 1은 오른쪽 맨 아래로 이동하게 되고 기존의 1자리에는 7이 위치하게 된다. 7이 가장 상단에 올라가기 위해 은 7은 3과 스왑, 다시 7은 6과 스왑되며 2번의 스왑을 일으키게 된다. 이를 해결하기 위해서 Bottom Up방식을 이용했다. 1).. #290 백준 파이썬 [1715] 카드 정렬하기 https://www.acmicpc.net/problem/1715 SOLUTION 우선 순위 큐를 힙으로 구현하여 사용할 수 있다. 알고리즘은 다음과 같다. 0) 총 비교한 횟수(answer)를 0으로 둔다. 1) 현재의카드 묶음(card_deck) 중 가장 작은 2개의 카드 묶음을 꺼낸다. 2) 두 개를 더한 값 = 현재 단계에서 비교한 횟수 3) 두 개를 더한 값을 총 비교한 횟수에 더해준다. 4) 두 개를 더한 값을 다시 카드 더미 안에 넣는다. 5) 1 ~ 4 과정을 힙에 하나의 덱만 남을 때 까지 반복한다. PYTHON CODE import heapq import sys N = int(input()) card_deck = [] for _ in range(N): heapq.heappush(card.. #289 백준 파이썬 [1766] 최단경로 - 다익스트라 https://www.acmicpc.net/problem/1753 SOLUTION 해당 문제는 다익스트라 알고리즘으로 풀 수 있다. 다익스트라 알고리즘은 https://www.youtube.com/watch?v=611B-9zk2o4이 분이 굉장히 잘 설명해주셨다. 서로서로 연결된 그래프의 K번째 노드에서 1,2,3, ... V개의 노드에 도달하는 가장 짧은 거리들을 구하는 것이다. 이 때 가장 짧은 노드는 지속적으로 갱신되기 때문에 우선 순위 큐를 구현하여 처리해야한다. 일반 리스트에 append하고 최소값을 구하는 방법으로는 시간 복잡도가 굉장히 오래걸리기 때문. 우선 순위 큐는 힙으로 구현할 수 있다. 힙에 추가 및 삭제되며 저장될 때는 이진 트리를 따르기 때문에 빠르게 최소값을 출력할 수 있다. 다.. 이전 1 ··· 12 13 14 15 16 17 18 ··· 52 다음
