🌱 → 🌳

예제 1) 1이 될 때 까지 while True: # (N==K로 나누어떨어지는 수)가 될 때까지 1씩 빼기 target = (n//k)*k count += (n-target) n = target if n

요구사항에 따라 적절한 알고리즘 설계하기 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항) 시간제한이 1초인 문제를 만났을 때, 일반적인 기준 N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계 N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계 N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계 N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계 알고리즘 문제 해결 과정 (일반적으로) 1. 지문 읽기 및 컴퓨팅적 사고 2. 요구사항(복잡도) 분석 3. 문제 해결을 위한 아이디어 찾기 4. 소스코드 설계 및 코딩 일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 📌 문제 해설 "Xi>Xj를 만족하는 서로 다른 좌표의 개수와 같아야된다" 라는 뜻은 즉 Xi가 리스트 안에서의 크기 순서를 출력하면 된다는 말 (크기 순서는 0부터 시작.) 즉, 리스트안에서 자기보다 작은 숫자의 개수를 세는 것이므로, 자신이 리스트 안에서의 크기 순서를 출력하면 됨 📌 코드 실패 코드 (시간 초과) n = int(input())..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 정답코드: from collections import Counter import sys a = int(sys.stdin.readline()) b= [] for i in range(a): b.append(int(sys.stdin.readline())) b.sort() c = a//2 # 산술평균 print(round(sum(b)/a)) # 중앙값 print(b[c]) # 최빈값 cnt = Counter(b).mo..

처음 작성한 코드 import sys n = int(input()) m = [] for i in range(n): m.append(int(sys.stdin.readline())) m.sort() for i in m: print(i) → 메모리 초과 발생 시간복잡도를 줄이기 위해 sys를 쓰는 건 알겠지만 메모리 초과,, 공간복잡도를 줄이기 위해서는 어떻게 해야하는 지 몰라서 인터넷을 찾아봤다. 정답 코드 import sys n = int(sys.stdin.readline()) m = [0] * 10001 for i in range(n): m[int(sys.stdin.readline())] += 1 for i in range(10001): if m[i] != 0: for j in range(m[i]): p..

2750 - 수 정렬하기 시간 복잡도가 O(n²)인 정렬 알고리즘 ex) 삽입 정렬, 버블 정렬 a = int(input()) arr = [] for i in range(a): arr.append(int(input())) arr = sorted(arr) for i in range(len(arr)): print(arr[i]) 2751 - 수 정렬하기 2 시간 복잡도가 O(nlogn)인 정렬 알고리즘 ex) 병합 정렬, 힙 정렬 등 아직 알고리즘을 배우지 않은 상태이므로 내장 함수 사용 → import sys를 하여 input()의 시간을 줄였음 import sys a = int(input()) num = [] for i in range(a): num.append(int(sys.stdin.readline()..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 정답 코드: def is_prime(n): if n == 1: return False for j in range(2, int(n**0.5)+1): if n % j == 0: return False return True t = int(input()) for i in range(t): num = int(input()) a,b = num//2, num//2 while a > 0: i..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 처음 코드: while(1): a=int(input()) if a ==0: break cnt=0 for i in range(a+1,2*a+1): if i == 1: continue for j in range(2,int(i**0.5)+1): if i % j == 0: break else: cnt+=1 print(cnt) 각 테스트 케이스마다 계속 소수를 계산하니까 시간 초과 발생 정답 코드:..