본문 바로가기

코딩테스트19

[백준] 1041: 주사위 파이썬 리뷰 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. 처음 보는 유형이라 굉장히 복잡하게 느껴졌습니다. 하지만 주사위 면이 보이는 경우에 따라 나눠 생각하면 3가지 밖에 되지 않기 때문에 생각한 거 보다 간단했습니다. (M 면이 보이는 주사위의 수) X (M 면의 최소합) 으로 3가지 경우를 모두 구해 더해주면 됩니다. M 면의 최소합을 구하는 것이 굉장히 생소했습니다. 주사위 특성상 마주보는 면을 제외하고 모든 면이 인접해있다. 따라서 A,B,C,D,E,.. 2021. 2. 19.
[알고리즘] LCS (Longest Common Subsequence) 문제 LCS 문제는 두 문자열이 주어졌을 때 두 문자열이 공통으로 가지는 문자의 가장 긴 길이를 구하는 문제입니다. 이 때, 공통으로 가지는 문자의 순서가 바뀌어선 안됩니다. 예시는 다음과 같습니다. 해당 문제는 동적계획법을 이용해 O(N^2)의 시간 복잡도로 해결할 수 있습니다. 동적계획 방법입니다. 1. 각 문자열 별로 dp 테이블을 만들기 위해 2차원 배열을 선언합니다. 2. dp 테이블의 인덱스 0은 문자열이 0개일 때이므로 모두 0으로 초기화합니다. 3. 이후 테이블을 초기화 할 때 해당 자리의 문자열(Xi, Yj)을 비교합니다. 3-1. 문자열이 다르면 i 또는 j를 줄인 것 중 큰 값으로 테이블을 초기화합니다. 3-2. 문자열이 같으면 i와 j 모두 줄인 값에서 +1 하여 초기화합니다. 4. LC.. 2021. 2. 15.
[백준] 14501: 퇴사 파이썬 리뷰 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. dp 계산을 N부터 시작하는 방법을 사용해야 했습니다. 뒤에서 부터 계산을 해보면 다른 동적 계획법과 풀이 방법은 비슷합니다. 파이썬 코드 import sys readline = sys.stdin.readline N = int(readline()) T, P = [], [] for _ in range(N): t, p = map(int, readline().split()) T.append(t) P.append(p) d = [0] * (N+1) for i in range(N - 1, -1, -1): # i일에 상담을 하는 것이 퇴사일을 넘기면 상담을 하지 않음 if i .. 2021. 2. 14.
[백준] 2133: 타일 채우기 파이썬 리뷰 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이는 블로그 1, 블로그 2 를 참고했습니다. d(i-4) * 2 + ... + d(0) * 2 부분이 이해하기 힘들었습니다. 점화식은 역시 그려봐야 이해가 됩니다... 파이썬 코드 N = int(input()) d = [0]*31 d[0] = 1 for i in range(2, N+1, 2): d[i] = d[i-2] * 3 for j in range(0, i-2, 2): d[i] += d[j] * 2 print(d[N]) 2021. 2. 13.

티스토리툴바