본문 바로가기

Computer Science/Algorithm48

[백준] 1654번 랜선 자르기, 시간초과 - 이분탐색(풀이 암기) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 시간 초과 나온 풀이 # BOJ_1654 import sys # 입력 k, n = map(int, input().split()) lines = [] for _ in range(k): lines.append(int(sys.stdin.readline())) # 전체 합을 k로 나눈 값에서 내림차순으로 시작한다. sum = 0 for line in lines: sum += .. 2023. 1. 25.
[백준] 10816번 숫자 카드2, 시간 초과 - 이진탐색 + 알파 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 처음엔 count()를 이용하여 몇 개가 들어갔는지 구하였다. 그렇게 하니 시간복잡도가 O(n^2)으로 2% 대에서 시간 초과가 나왔다. 그래서 이진탐색 사용 # BOJ_10816 import sys # 입력 n = int(input()) cards = list(map(int, sys.stdin.readline().split())) m = int(input()) .. 2023. 1. 21.
[백준] 2562번 최댓값, 줄 단위 정수 리스트로 입력 받기 https://www.acmicpc.net/problem/2562 2562번: 최댓값 9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오. 예를 들어, 서로 다른 9개의 자연수 3, 29, 38, 12, 57, 74, 40, 85, 61 이 주어 www.acmicpc.net 여러 줄의 정수 입력받기 n = int(input()) # 입력 받을 정수 개수 li = [int(input()) for _ in range(n)] 출처: https://bio-info.tistory.com/157 [Python] 정수 및 배열 입력 받기 (알고리즘 입력) / sys.stdin.readline(입력 빠르게하기) * 전체 코드 ### 정수 1개 입력받.. 2023. 1. 17.
[백준] 1676번 팩토리얼 0의 개수 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2의 배수와 5의 배수의 합집합 구할 때처럼 1) 10으로 안 나눠지는 2의 배수 (여집합) 2) 10으로 안 나눠지는 5의 배수 (여집합) 1)과 2)의 최솟값에 10의 배수를 더해주는 식으로 코드를 구현했다. (공집합) # BOJ_1676 # 입력 n = int(input()) # 10의 약수는 1, 2, 5, 10이므로 1, 2, 3, ..., n이 이하의 수 중에서 10의 배수는 어차피 2, 5의 배수이므로 # 2, 5의 배수의 개수 중에 최솟값을 구하면 되겠다. two_mu.. 2023. 1. 12.
[백준] 1764번 듣보잡, 시간초과 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net set 사용해서 제대로 푼 것 같은데 자꾸 시간초과가 나온다. # BOJ_1764 import sys # 입력 n, m = map(int, sys.stdin.readline().split()) names = [] for _ in range(n + m): name = sys.stdin.readline() names.append(name) # 중복된 원소 찾기 names.sort() overlap .. 2023. 1. 11.
[백준] 1181번 단어정렬 - 시간초과 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 1. 입력할 때 공백 부분(\n) 리스트에 빼고 넣기 # 공백 있는 문자열 name = " B l o ck DM a s k " # 양쪽 공백 제거 result1 = name.strip() # 왼쪽 공백 제거 result2 = name.lstrip() # 오른쪽 공백 제거 result3 = name.rstrip() print(f"name : |{name}|") print(f"name.st.. 2023. 1. 9.
[백준] 10828번 스택 구현 - 시간초과문제 스택 문제 예시와 답 모두 맞는 것 같은데, 시간 초과가 뜬다. 고작 O(N)일 뿐인데... 이상하다. # BOJ_10828 n = int(input()) stack = [] for _ in range(n): command = list(map(str, input().split())) # push if command[0] == 'push': stack.append(int(command[1])) # pop elif command[0] == 'pop': if len(stack) == 0: print(-1) else: print(stack[-1]) del stack[-1] # size elif command[0] == 'size': print(len(stack)) # empty elif command[0] ==.. 2023. 1. 8.
[백준] 2108번 통계학, 중앙값: 인덱스 조심(반올림 말고 내림) https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 풀이 # BOJ_2108 import math # 수 입력 n = int(input()) nums = [] for i in range(n): nums.append(int(input())) # 1. 산술평균 구하기 sum = 0 for num in nums: sum += num print(round(sum / n)) # 2. 중앙값 구하기 nums.sort() # 오름차순으로 정렬 index = math.f.. 2023. 1. 7.
[백준] 1929번 소수 구하기, 실버3, python https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 단순히 소수만 구하면 안되고 입력값이 1000000 이므로 시간복잡도 O(N^2)이면 100억이 되어 시간 초과가 뜨게 된다. 이런 경우 에라토스테네스의 체의 원리를 구현하여 푸는 것으로 문제를 해결 하면 좋다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 .. 2023. 1. 7.

티스토리툴바