jae_coding

문제 문제 링크 문제 접근 0, 1이 쓰여진 낱장의 타일 -> 00, 1 이 쓰여진 낱장의 타일 goal: N이 주어졌을 때, 가질 수 있는 모든 가짓수 output: 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지 N의 개수 1(1): 1 2(2): 00, 11 3(3): 001, 100, 111 4(5): 0011, 0000, 1100, 1111, 1001 5(8): 00001, 10000, 11100, 11111, 10011, 11001, 00100, 00111 점화식 An = A(n-2) + A(n-1) 코드 메모리 초과 코드 import sys sys.setrecursionlimit(10**6) def fib(N, memo): if N == 1: return 1 elif N ==..

문제 문제 링크 문제 접근 dp를 활용하는게 효율적인 코드를 만들 것 같다. 개수에 따라서 최대 값을 dp에 저장시킴으로써 정답을 도출할 수 있을 것으로 예상했다. 코드 import sys N = int(sys.stdin.readline()) P = list(map(int, sys.stdin.readline().split())) dp = list([0] * (N + 1)) for i in range(1, N+1): for j in range(1, i+1): dp[i] = max(dp[i], dp[i-j] + P[j-1]) print(dp[len(dp)-1]) 느낀점 파이썬에서 dp를 이용하기 위해서 list의 개수를 두번째 for 를 이용하기 위해서 N + 1개로 만들어주어야 하는 것을 깨닫게 되었다. ..

문제 문제 링크 문제 접근 비트 마스킹을 통해서 문제를 풀어봐야겠다. 이 문제 또한 문제의 패턴을 잘 파악해야 한다. 내가 생각한 패턴은 표와 같이 생각을 해보았다. A[n][0] = 1, 일반화 공식: A[n][m] = A[n-1][m] + A[n][m-1] 0 1 2 3 4 5 6 7 8 9 1자리 1 1 1 1 1 1 1 1 1 1 2자리 1 1 + 1 = 2 2 + 1 = 3 4 5 6 7 8 9 10 3자리 1 3 6 10 15 21 28 36 45 55 코드 import sys N = int(sys.stdin.readline()) lst = list([1] + [0] * 9 for _ in range(N)) lst[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in..

문제 문제 링크 문제 접근 N에서 M으로 가는 경우의 수를 구하는 것이다. N이 M보다 작거나 같으므로 조합공식 mCn을 적용시킨다. 코드 import sys def factorial(N): result = 1 for i in range(1, N+1): result *= i return result T = int(sys.stdin.readline()) for _ in range(T): N, M = map(int, sys.stdin.readline().split()) # M >= N # Combination ans = int(factorial(M) / (factorial(N) * factorial(M-N))) print(ans) 느낀점 조합에 대한 공식을 도출하는데까지의 시간이 좀 걸린 것 같다.

문제 문제 링크 문제 접근 dp 문제이자 일반식을 도출해내는 문제인 것 같아서 바로 접근을 시도해보았다. An이 피보나치 수열과 동일하다는 일반화를 공식화해내었다. An = A(n-2) + A(n-1), n >= 2일 때의 일반식을 도출해냈다. 코드 import sys def fib(N, memo): if N == 1 or N == 2: return 1 elif N not in memo: temp = fib(N-2, memo) + fib(N-1, memo) memo[N] = temp return memo[N] else: return memo[N] memo = dict() N = int(sys.stdin.readline()) print(fib(N, memo)) 느낀점 피보나치 수열을 알고있고, 일반식에 대..

문제 문제 링크 문제 접근 dp알고리즘과 일반화 공식 An을 구하는 것이 좋은 접근일 것이다 A1 = 1, A2 = 3이라는 것을 미리 구해주는 것이 가장 좋다. 그리고 A3 = 5, A4 = 11이라는 점을 활용하여 피보나치 함수를 변형하여 An = A(n-2) + 2 * A(n-1)을 일반화해준다. 구하고자하는 An에 % 10007을 이용하여 결과를 도출한다. 코드 import sys # 재귀 함수의 제한 범위를 늘려주는 방법 sys.setrecursionlimit(10**6) num = int(sys.stdin.readline()) memo = dict() def cal(N, dictionary): if N == 1: return 1 elif N == 2: return 3 else: if N not..

문제 문제 링크 문제 접근 dictionary를 활용하면 문제에 대한 접근성이 좋을 것 같다. dictionary key에 대한 value는 N개의 letter에서 몇번째 자리의 수가 key인지 알면 좋을 것 같다. 예를 들어 2, GCF, ACDEB에서 C의 dictionary key는 1010으로 GCF에서 C의 자리 10과 ACDEB의 C의 자리 1000을 더해준 값과 같이 dictionary를 구성해준다. 여기서 몇번째 자리가 가장 높은지에 대한 index리스트를 구성해준다. 이때 index리스트는 내림차순으로 구성해준다. 그리고 결과는 자리수가 높은 순서대로 9부터 1씩 감소하면서 문자의 index를 정해준 후 index리스트를 곱하여 준 후 합을 구하여 준다. 코드 import sys def ..

문제 문제 링크 문제 접근 강의실은 한정적이기 때문에 최소 강의실 사용한다. 강의는 모두 Si ~ Ti까지 강의를 진행한다. 수업이 끝난 직후에 다른 수업이 진행 가능하다. 강의 시작시간이 낮은 강의부터 오름차순 정렬을 진행한다. 강의가 끝나는 시간을 우선순위큐에 푸쉬를 해주면서 정렬된 강의의 시작시간이 진행중인 강의 종료시간보다 느리다면 우선순위 큐를 팝 해준 후 종료시간 푸쉬를 해준다. 그렇지 않으면 종료시간만 푸쉬를 해준다. 결론적으로 강의 시간이 곂치게 된다면 두개의 강의가 동시에 들어가기때문에 강의실의 개수는 우선순위 큐의 길이가 된다. 코드 import sys import heapq def main(): N = int(sys.stdin.readline()) SiTi = list() for _ ..

문제 문제 링크 문제 접근 B에 있는 수를 재배열 하면 안 된다에서 많은 고민을 하였지만 알고리즘 상에서 상관없기 때문에 재배열은 아니다. 리스트를 2개를 이용하지만 A 리스트는 오름차순, B리스트는 내림차순으로 정렬을 한다 두 리스트를 index 값끼리 곱하여 합을 구한다 코드 import sys def main(): N = int(sys.stdin.readline()) sum = 0 sorted_A = list() sorted_B = list() A = sys.stdin.readline().strip().split() B = sys.stdin.readline().strip().split() for i in range(N): sorted_A.append(int(A[i])) sorted_B.append(..