개발윗미

Python으로 구현한 21608번 상어 초등학교 문제 풀이입니다. https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net from heapq import heappush, heappop # 만족도 0이면 0, 1이면 1, 2면 10, 3이면 100, 4면 1000 def satisfied() : result = 0 for r in range(n) : for c in range(n) : if not board[r][c] : continue ..

[문제] 정렬된 두 묶음의 숫자 카드가 있을 때 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A + B번의 비교를 해야 합니다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요합니다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있습니다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라집니다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요합니다. 그러나 10장과 40장을 합췬 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50..

heapq 라이브러리는 힙(Heap) 기능을 다룰 수 있도록 해준다. 파이썬에서의 힙은 최소 힙(Min Heap)으로 구성되어 있으며, 원소를 Heap에 모두 삽입했다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 정렬을 수행할 수 있다. 기본적으로 Heap에 원소를 삽입할 때 사용하는 메서드는 heapq.heappush( ) 이고 Heap에서 원소를 빼낼 때 사용하는 메서드는 heapq.heappop( ) 이다. 아래는 heapq를 통해 원소들을 오름차순으로 정렬한 예제이다. [오름차순 예제] import heapq def heapsort(i): number = [] result = [] for value in i: heapq.heappush(number, value) for i in range(le..