Programming [Python] (411) 썸네일형 리스트형 #106 백준 파이썬 [1927] 최소 힙 https://www.acmicpc.net/problem/1927 #Solution 파이썬 heapq 모듈을 사용하면 쉽게 구할 수 있다. 힙 정렬에 대한 이해도가 된 상태에서 사용하는 걸 권장! 시간복잡도는 O(log2n) import sys import heapq numbers = int(input()) heap = [] #Max Heap for _ in range(numbers): num = int(sys.stdin.readline()) if num != 0: heapq.heappush(heap, num) else: try: print(heapq.heappop(heap)) except: print(0) #105 백준 파이썬 [11279] 최대 힙 https://www.acmicpc.net/problem/11279 #Solution heapq를 활용하지만 이 함수는 min heap만을 지원한다. 따라서 num을 음수로 만들어줘 최대값을 출력한다. import sys import heapq numbers = int(input()) heap = [] #Max Heap for _ in range(numbers): num = int(sys.stdin.readline()) if num != 0: heapq.heappush(heap, (-num)) else: try: print(-1 * heapq.heappop(heap)) except: print(0) #104 백준 파이썬 [1766] 문제집 - 위상정렬 + 힙 https://www.acmicpc.net/problem/1766 #Solution 해당 문제는 '사이클'이 없고 '방향'만 존재하는 그래프(DAG: Directed Acyclic Graph)에서 정점(Vertex)을 나열하는 방법으로 풀 수 있다. 이를 위상정렬 (Topological Sort)이라고 한다. 또한 힙을 이용해 우선순위 큐를 구현해 시간을 최소화해야한다. 0) 정점과 연결된 다른 정점 리스트, 정점에 들어오는 그래프 개수 리스트 2개를 만들어준다. 1) 진입 루트(Indegree)가 없는 정점을 먼저 최소 힙에 넣어준다. 2) 해당 정점과 연결되어있는 노드에서 진입 루트 개수를 하나씩 빼준다. 3) 최소 힙을 출력(heappop)해주고 다시 1)로 돌아가고 힙이 빌 때까지 반복한다. 힙을.. #103 백준 파이썬 [2010] 플러그 https://www.acmicpc.net/problem/2010 #Solution input 자체가 굉장히 많기 때문에 input()함수로 풀면 시간 초과가 난다. 따라서 sys.stdin.readline()으로 풀어준다. import sys tap_num = int(input()) consent_num = sum([int(sys.stdin.readline()) for _ in range(tap_num)]) print(consent_num - tap_num + 1) #102 백준 파이썬 [10814] 나이순 정렬 https://www.acmicpc.net/problem/10814 #Solution Lambda를 이용한 간단한 정렬 문제 member_num = int(input()) member_list = [] for _ in range(member_num): member_age, member_name = map(str, input().split()) member_age = int(member_age) member_list.append((member_age, member_name)) #나이 숫자 정렬 > 가입순 정렬 member_list.sort(key = lambda member: (member[0])) for member in member_list: print(member[0], member[1]) #101 백준 파이썬 [1181] 단어 정렬 https://www.acmicpc.net/problem/1181 #Solution lambda를 이요한 리스트 내부 정렬 words_num = int(input()) words_list = [] for _ in range(words_num): word = str(input()) word_count = len(word) words_list.append((word, word_count)) #중복 삭제 words_list = list(set(words_list)) #단어 숫자 정렬 > 단어 알파벳 정렬 words_list.sort(key = lambda word: (word[1], word[0])) for word in words_list: print(word[0]) #100 백준 파이썬 [2217] 로프 - 그리디 알고리즘 https://www.acmicpc.net/problem/2217 #Solution 그리디 알고리즘을 이용한 풀이이다. 시간초과가 나오지 않을까 걱정했지만 다행히도 아래 풀이법으로 정답을 맞췄다. 내림차순으로 로프를 정렬한 뒤 (n번째 큰 수) * n 이 최대값이 되는 수를 찾는 방법이다. 단순하다. rope_num = int(input()) rope_list = [] answer = 0 for _ in range(rope_num): rope_list.append(int(input())) rope_list.sort(reverse = True) for i in range(rope_num): if answer < rope_list[i] * (i + 1): answer = rope_list[i] * (i + .. #99 백준 파이썬 [2447] 별 찍기 - 10 https://www.acmicpc.net/problem/2447 #Solution 이 문제는 프랙탈 도형을 그리는 문제이다. 프랙탈 같은 경우는 최소 단위로 쪼갤 수 있기에 분할 정복 알고리즘(Divide and Conquer)을 이용해 풀 수 있다. 분할 정복 알고리즘의 단계를 분할, 정복, 합치기 세 개로 나누면 쉽게 기억할 수 있다. def stars(n): matrix=[] for i in range(3 * len(n)): if i // len(n) == 1: matrix.append(n[i % len(n)] + " " * len(n) + n[i % len(n)]) else: matrix.append(n[i % len(n)] * 3) return(list(matrix)) star = ["***".. 이전 1 ··· 36 37 38 39 40 41 42 ··· 52 다음
