모카의 촉촉한 개발 로그

https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net import sys from collections import defaultdict n,m=map(int,input().split()) dic=defaultdict(int) for _ in range(n): x=sys.stdin.readline().rstrip() if len(x)>=m: dic[x]+=1 dic2=sorted(d..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net from itertools import combinations n,m=map(int,input().split()) arr=list(range(1,n+1)) arr2=list(combinations(arr,m)) print(len(arr2)) 위와 같은 코드로 조합의 경우의 수를 셀수도 있지만 해당 문제는 0.5초라는 시간 제한이 이기 때문에 다른 접근 법이 필요하다. def factorial(n)..

https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net from collections import deque dq=deque() n=int(input()) arr=list(map(int,input().split())) for idx,val in enumerate(arr): dq.append([idx+1,val]) x=dq.popleft()[1] res=[1] while dq: if x>0: for _ in range(x-1): if ..

https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제의 조건을 놓쳐 틀린 코드 n=int(input()) arr=list(map(int,input().split())) stack=[] order=1 for x in arr: if x==order: order+=1 else: stack.append(x) for _ in range(len(stack)): if stack[-1]==min(stack): stack.pop() if stack: prin..

https://www.acmicpc.net/problem/17103 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 배열의 i번째 소수만 참고해서 i와 N-i가 소수이면서, i와 N-i의 합이 N이 되는 경우의 개수를 찾으면 된다. 시간 초과난 코드 1 x=int(input()) for _ in range(x): n=int(input()) ch=[0]*(n+1) for i in range(2,int(n**0.5)+1): if ch[i]==0: for j in range(i*2,n+1,i): ch[j]=1 cnt=..

https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 최소 공배수 = 두 수의 곱 나누기 최대 공약수 최대 공약수 구하는 법 [유클리드 호제법] n=int(input()) for _ in range(n): a,b=map(int,input().split()) tmp=a*b while b != 0: r = a % b a = b b = r print(a) # 최대공약수 즉, a,b는 한번의 연산마다 하나는 나머지로, 다른 하나는 다른 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 시간 초과난 나의 코드 1 n,m=map(int,input().split()) arr=list(map(int,input().split())) for _ in range(m): a,b=map(int,input().split()) print(sum(arr[a-1:b])) 시간복잡도 O(n*M)으로 초과 (sum함수로 슬라이싱 연산시 O(N)의 시간 복잡도를 가진다. 시간 초과난..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 시간 초과난 코드 1 n=int(input()) arr=list(map(int,input().split())) arr2 = sorted(list(set(arr))) for i in range(n): for j in range(len(arr2)): if arr[i]==arr2[j]: print(j,end=' ') break 우선 정렬 sorted를..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 메모리 초과된 잘못된 코드 메모리 초과 import sys n=int(input()) arr=[] for _ in range(n): arr.append(int(sys.stdin.readline())) arr.sort() for x in arr: print(x) append를 사용하면 메모리 재할당이 발생해 메모리소비가 크다. 그래서 체크리스트를 사용 체크리스트 import sys n=int(input()) ch=[0..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net n = int(input()) count = 0 while True: if n%5 == 0: count += n//5 print(count) break n -= 3 count +=1 if n < 0: print(-1) break 최저의 count를 만드는 5를 사용한뒤 안되면 차선인 3을 빼면서 탐색