본문 바로가기
728x90

알고리즘316

[python] 백준 1715 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 해결 작은 수의 카드 묶음의 크기를 가진 것 부터 계산을 하는 것이 이득이라는 것을 알 수 있다. 리스트를 쓰고 sort를 쓰면 시간 초과가 난다. 우선순위 큐 (heapq 나 PriorityQueue를 쓰면 좋겠다는 생각으로 풀었다. CODE import sys import heapq n = int(input()) A = [] for _ in range(n): heapq.he.. 2023. 2. 23.
[python] 백준 2343 기타 레슨 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 해결 블루레이 크기란 무엇인가? => 컴퓨터 메모리로 생각하면 편하다. ex) 블루레이 크기 17이면 수의 합이 17이 될 때 까지만 메모리 저장 가능 메모리 크기는 강의 길이가 가장 큰거 이상이여야 한다. 메모리 크기는 모든 강의 길의 합 이하여야 한다. 따라서 메모리 크기의 최소지점과 최대지점 투 포인터를 집아 이분 탐색을 해서 블루레이 크기중 최소를 출력하도록 한다. CODE import sy.. 2023. 2. 23.
[python] 백준 2023 신기한 소수 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 풀이 두자리 이상일때(n≥2) 맨 앞자리는 소수만 가능(2,3,5,7) 나머지 자리는 홀수만 가능(1,3,5,7,9) 그래서 앞자리 만드는 것 부터 시작.(2, 3, 5, 7) 그 다음 수를 이어 붙일 때 소수인지 확인하고 소수이면 이어붙이고 아니면 다른 수 찾기 n자리 수가 되었을 때 출력 전형적인 DFS로 풀 수 있다. CODE import sys sys.setrecursion.. 2023. 2. 22.
[python] 백준 10989 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 기수 정렬 문제 시간초과를 신경써야 하는 문제 최대 수가 10000000이므로 리스트를 100000001개 만들고 입력 수를 인덱스로 해서 하나씩 +1 1부터 100000000까지 인덱스를 돌면서 value가 0이 아닌 값을 추출하면 된다. CODE import sys input = sys.stdin.readline N = int(input()) A = [0]*10001 for _ in range(N): .. 2023. 2. 22.
728x90