공작소

문제 링크 : https://www.acmicpc.net/problem/1082 문제스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호..

문제 링크 : https://www.acmicpc.net/problem/17069 문제유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.파이프를 밀 수 있는 방향..

문제 링크 : https://www.acmicpc.net/problem/14852 문제2×N 크기의 벽을 2×1, 1×2, 1×1 크기의 타일로 채우는 경우의 수를 구해보자.입력첫째 줄에 N(1 ≤ N ≤ 1,000,000)이 주어진다.출력첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.풀이 과정# 14852. 타일 채우기 3 ( GOLD 4 )import sysinput = sys.stdin.readline# 2xN 크기의 벽을 2x1, 1x2, 1x1# ## #. #.# .. #. ..# 2x1을 채우는 방법 (x2)# A A# B A# 2x2를 채우는 방법# i-1 (x2)# #A #A# #B #A# i-2 (x3)# AA AA BC # BB BC AA# 번외로, 1x2 를..

문제 링크 : https://www.acmicpc.net/problem/13398 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.입력첫째 줄에 정수 n(1 ≤ ..

커누스-모리스-프랫 알고리즘 (Knuth–Morris–Pratt algorithm, KMP) 은 문자열 S 에서 문자열 A 를 찾고자 할 때 단순히 모든 경우를 다 비교해보면서 찾는 방식 보다는 접두사와 접미사를 이용해 불필요한 문자열 탐색 횟수를 줄여 문자열을 효율적으로 찾아낼 수 있는 문자열 매칭 알고리즘이다. 하나씩 비교하는 문자열 매칭문자열 S의 길이를 N, 문자열 A의 길이를 M이라 할 때, 문자열 S 에서 문자열 A를 찾을 때의 시간 복잡도는 O(NM) 이다.S = input()A = input()for i in range(len(S)): for j in range(len(A)): if S[i+j] != A[j]: break if j == len(A) - 1: print(i)# I..