OSNIM

구현, 문자열 문제 : https://www.acmicpc.net/problem/2941 제출 코드 import sys input = sys.stdin.readline string = input().strip() croatia = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] cnt = 0 for alpha in croatia: string = string.replace(alpha, '*') print(len(string)) 첫번째 문자가 크로아티아 알파벳에 있는 문자중 첫번째 문자와 같으면 2자리 또는 3자리를 비교하는 방식으로 풀려고 했습니다. 그런데 너무 복잡해지고 풀이가 산으로 가는 것 같아 검색으로 힌트를 얻었습니다. 크로아티아 알파벳의 문자들을 rep..

수학, 구현, 브루트 포스 문제 : https://www.acmicpc.net/problem/4673 제출 코드 import sys print = sys.stdout.write check = [0] * (10001) for i in range(1, 10001): string = str(i) temp = i for j in string: temp += int(j) if temp < 10001: check[temp] = 1 for i in range(1, 10001): if not check[i]: print(f"{i}\n") 결과 및 정리 처음에 문제가 단순한 수학 함수여서 쉽게 풀 수 있을 줄 알았습니다. 하지만 10 이하의 셀프넘버 중 2, 4, 6, 8이 안되는 이유를 못찾았습니다. 그런데 자기 자신..

Level 3, Greedy 문제 : https://programmers.co.kr/learn/courses/30/lessons/42884?language=python3 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 1. 나간 기준 오름차순 정렬 2. 카메라 위치 -30001로 초기화 3. if 나간 지점 >= 다음 차량 진입 지점 ( 두 차량이 겹치는 경우) continue (다음 차량 확인) else: 차량 나간 지점에 마지막 카메라 위치 초기화 answer += 1 제출 코드 def solution(routes): answer = 0 routes.sort(key = lambda x : x[1]) lastC..

문제: https://programmers.co.kr/learn/courses/30/lessons/42861?language=python3# 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 첫번째 제출 코드 (오답) import heapq as hq def solution(n, costs): answer = 0 visited = set() q = [] SUM = 0 costs.sort(key=lambda x: (x[2], x[0], x[1])) for start, end, cost in costs: if start in visited and end in visited: continue answer += co..

힙을 이용한 최단 경로 알고리즘 구하기 import heapq as hq def dijkstra(start, graph, distance): q = [] # 시작 노드로 가기 위한 최단 거리는 0으로 설정 hq.heappush(q, [0, start]) distance[start] = 0 while q: #최단 거리의 섬과 거리 dist, now = hq.heappop(q) #현재 섬이 처리 되었다면 스킵 if distance[now] < dist: continue #현재 섬과 연결된 다른 섬들을 확인 for e, c in graph[now]: #도착지, 비용 cost = dist + c # 현재 노드를 거쳐 다른 섬으로 이동하는 거리가 더 짧은 경우 if cost < distance[e]: distan..

Level 1 Greedy(탐욕법) 문제 : https://programmers.co.kr/learn/courses/30/lessons/42862?language=python3# 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 첫번째 정답 코드 def solution(n, lost, reserve): answer = 0 reserve.sort() lost.sort() temp = reserve[:] for i in reserve: if i in lost: lost.remove(i) temp.remove(i) r..

완전탐색, Level 3 문제 : https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 정답 코드 def solution(brown, yellow): answer = [] # m : 노란 카펫의 가로 # n : 노란 카펫의 세로 for m in range(1, yellow+1): if yellow%m == 0: n = yellow//m if (m+2)*(n+2) == brown + yellow: answer.a..

level 2 힙 문제 : https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr import heapq def solution(scoville, K): answer = 0 q = [] for i in scoville: heapq.heappush(q,i) while len(q) > 1: if q[0] >= K: break food1, food2 = heapq.heappop(..

문제 : https://www.acmicpc.net/problem/2293 정답 코드 import sys def solve(): for coin in arr: for j in range(coin, K+1): dp[j] += dp[j-coin] print(dp[K]) return if __name__=="__main__": input = sys.stdin.readline N, K = map(int, input().split()) arr = [int(input()) for i in range(N)] # dp[1]는 1개만 골랐을 때 경우의 수 # dp[0]은 하나의 동전만으로 k원 만드는 경우의 수를 의미 = 1 dp = [1] + [0]*K solve() 결과 및 정리 전형적인 DP 문제 메모리가 4MB라..

문제 : https://www.acmicpc.net/problem/2531 첫번째 풀이 (pypy3 2772ms, python3 시간초과) import sys def solve(): left = 0 right = k answer = 1 while left < N: eat = set() # 초밥을 k개 만큼 먹기 for i in range(left, right): eat.add(arr[i%N]) # c가 없으면 1개 추가하기 eat.add(c) answer = max(answer, len(eat)) # 1칸씩 밀기 left += 1 right += 1 print(answer) return if __name__=="__main__": input = sys.stdin.readline # N: 접시의 수 # d..

문제 : https://www.acmicpc.net/problem/2038 골룽 수열은 1이 1개, 2가 2개 있으니 2번, f(3) = 2 이므로 3이 2번 나타나는 단조 증가하는 수열입니다. 수열을 숫자로 풀면 다음과 같습니다. [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8..] 첫번째 제출 (시간초과) import sys def solve(dp): left = 1 right = 0 k = 3 while len(dp) < n: dp = dp + [k]*(dp[left]) left += 1 k = k+1 print(dp[n-1]) return if __name__=="__main__": n = int(sys.stdin.read..

문제 : https://www.acmicpc.net/problem/1484 정답 코드 import sys def solve(): curWeight = 1 memoWeight = 1 answer = [] if G G: if diff == 1: break memoWeight += 1 elif powDiff == G: answer.append(curWeight) memoWeight += 1 elif powDiff < G: curWeight += 1 ..

문제 : https://www.acmicpc.net/problem/2230 정답 코드 import sys def solve(): start = 0 end = 0 answer = 2000000000 while end = M: if answer >= subtraction: answer = subtraction start += 1 if start > end: start -= 1 end += 1 elif subtraction < M: end += 1 print(answer) return if __name__=="__main__": input = sys.stdin.readline N, M = map(in..

문제 : https://www.acmicpc.net/problem/1806 첫번째 제출 코드 (시간초과) import sys def solve(): start = 0 end = 0 answer = N+1 while end = S: if answer > (end+1 - start): answer = (end+1 - start) start += 1 if start > end: end += 1 start -= 1 else: end += 1 if answer == N+1: print(0) else: print(answer) return if __name__ == "__main__": input = sys.stdin.readline N, S = map..

문제 : https://www.acmicpc.net/problem/1644 제출 코드 import sys def makeSieve(n): sqrt = int(n**(0.5)) temp = [1] * (n + 1) for i in range(2, sqrt+1): if temp[i] == 1: for j in range(i*2, n+1, i): temp[j] = 0 return [i for i in range(2, n+1) if temp[i] == 1] def solve(): answer = 0 input = sys.stdin.readline N = int(input()) primes = makeSieve(N) start = 0 end = 0 while end < len(primes): if sum(prim..

문제 : https://www.acmicpc.net/problem/2225 import sys def solve(): arr = [[0] *(N+1) for i in range(K+1)] for i in range(1, K+1): for j in range(1, N+1): if j == 1: arr[i][j] = i elif i == 1: arr[i][j] = 1 else: arr[i][j] = arr[i-1][j] + arr[i][j-1] return arr[K][N] if __name__ == "__main__": input = sys.stdin.readline N, K = map(int, input().split()) print(solve()%1000000000) arr의 행은 K(정수의 개수)를 ..

문제 : https://www.acmicpc.net/problem/2003 정답 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) arr = list(map(int, input().split())) start = 0 end = 0 ans = 0 while end M: start += 1 print(ans) 정리 및 분석 처음에 end를 start와 다르게 해야하는 줄 알고 end를 1부터 시작했습니다. 하지..

Level 2 Mathematics 문제 : https://programmers.co.kr/learn/courses/30/lessons/92335 코딩테스트 연습 - k진수에서 소수 개수 구하기 문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소 programmers.co.kr 제출 코드 def checkPrime(num): if num 0: n, mod = n // base, n % base result += str(mod) # 역순인 진수를 뒤집어 줘야 원래 변환 하고자하는 base가 출력 return result[::-1] def so..

Level 2 완전탐색 문제 : https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 정답 코드 from itertools import permutations def prime(num): sieve = [1] * (num + 1) MAX = int(num ** (0.5)) for i in range(2, MAX + 1): # i 가 소수라면 if sieve[i] == 1: # 배수는 모두 소수가 아니..

Level 2 정렬 문제 : https://programmers.co.kr/learn/courses/30/lessons/42747# 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr 첫번째 제출 코드 def solution(citations): answer = 0 MAX = max(citations) n = len(citations) citations.sort() for h in range(0, MAX + 1): for i in range(n): if citations[i] < ..