Coding Test

https://www.acmicpc.net/status?user_id=yuu_ta&problem_id=10844&from_mine=1 ✔ 유형 : DP✔ 문제 풀이: 일의 자리 수에 어떤 수가 오느냐에 따라 경우의 수가 달라짐을 알고, 점화식을 세워 배열을 채워나간다.  코드import sysinput = sys.stdin.readlineMOD = 1000000000N = int(input())# 1 = 2: for i in range(2, N+1): DP[i][0] = DP[i-1][1] % MOD for j in range(1, 9): DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % MOD ..

https://www.acmicpc.net/problem/11053✔ 유형 : DP(LIS)✔ 문제 풀이:  LIS(Longest Increase Sequence) 의 로직과 비슷하다. DP[i] 를 i 번째 까지 가장 긴 증가하는 부분 수열의 개수라고 정의했을 때. i보다 앞쪽에 있는 원소들과 비교해서 i번째의 수보다 작을 때 개수를 업데이트 한다. 정리하자면,DP[i] : 현재까지 계산된 i위치에서의 LIS의 길이DP[j] + 1 : j위치까지 LIS에 현재 원소를 추가한 길이 그리고 D[i] 는 위의 두 경우의 수 중 최대값으로 업데이트 해주어야한다. 따라서, "현재 원소를 이전 LIS 에 추가했을 때 더 긴 LIS가 되는가?"를 조건을 생각해주면 되는것이다. 코드import sysinput = s..

https://www.acmicpc.net/problem/2156✔ 유형 : DP✔ 문제 풀이: 점화식을 세우는 접근방식은 다음과 같다 1. 맨 마지막 포도주를 무조건 선택한다 했을 때, 연속 두개를 선택하고 싶다면, arr[i] ( 마지막 포도주 ) , arr[i-1]( 마지막에서 두번째 포도주), 그리고 3개를 연속해서 선택할 수 없으므로arr[i-2]는 선택하지 않는다. 2. 맨 마지막 포도주를 무조건 선택하고, 그 전 포도주는 선택하지 않을 때,arr[i] ( 마지막 포도주 )를 선택하고, arr[i-1]는 선택하지 않는다. 3. 맨 마지막 포도주를 절대 선택하지 않을 때DP[i-1]  포도주의 개수가 N-1때의 최대값을 반영하면 된다. 이를 일반화 하면DP[i]는 세가지의 경우의 수로 일반화 하..

https://www.acmicpc.net/problem/1463 ✔ 유형 : DP✔ 문제 풀이: 정수에 사용할 수 있는 연산은 총 3가지인데, 빠르게 1을 만들려면 세가지 연산을 시행했을 때 값이 가장 작아야 한다.X라는 수를 1로 만들으려 했을 때,위 세가지 연산을 시행하면 우선 1번의 연산을 한 것이 된다. DP[X] = 정수 X에 연산을 시행했을 때 1이 되는 최소 연산 수행 횟수라고 정의할 때 다음과 같이 문제를 작게 나눌 수 있다.DP[X] = 1 + DP[X에 세가지 연산중 하나로 실행한 결과]와 같게 된다. 따라서 X에 세 가지 연산을 실행한 결과 값 중 가장 작은 값을 반영해서최소 연산 횟수를 저장해 나갈 수 있다. 다시 정리해보면 아래 점화식을 세울 수 있다. 코드import sysN ..

✔ 유형 : DP✔ 문제 풀이:  코드import sysimport copyinput = sys.stdin.readlineN = int(input())arr = list(map(int, input().split()))DP = copy.deepcopy(arr)for i in range(1, N): DP[i] = max(DP[i]+DP[i-1], arr[i]) #resultprint(max(DP))

https://www.acmicpc.net/problem/1932✔ 유형 : DP✔ 문제 풀이: DP memorization 방식으로 2차원 배열에 작은 값의 결과부터 저장  문제 접근  DP 점화식  코드import sysinput = sys.stdin.readline# input 1N = int(input()) # size of trianglearr = list()DP = [[0 for _ in range(N)] for _ in range(N)] # memorization# input 2for i in range(N): line = list(map(int, input().split())) arr.append(line)# initial valueDP[0][0] = arr[0][0]# ..

https://www.acmicpc.net/problem/9461 ✔ 유형 : DP✔ 문제 풀이: 규칙을 찾아 수가 작은 경우부터 결과 값을 배열에 채워나감. 이번 문제 같은 경우에는 초기값이 많았다.처음 변이 1인 삼각형에서 시작해서 변이 1인 삼각형과 2인삼각형이 일직선상에 놓이기 전까지는 일반화를 할 수가 없다.따라서, DP[0] = 0DP[1] = 1DP[2] = 1DP[3] = 1DP[4] = 2DP[5] = 2 N = 5일 때까지는 값을 정해줘야 한다. 그 이후에는 다음과 같은 점화식을 따른다. DP[N] = DP[N - 5] + DP[N - 1] 점화식을 이용해 배열을 채워 나가면 N일 때의 값을 구할 수 있다.  코드import sysinput = sys.stdin.readlineN = i..

https://www.acmicpc.net/problem/2579✔ 유형 : DP✔ 문제 풀이: 계단을 오를 때, 앞에서부터 계산해서 최대값을 구하는 것이 아닌, 최종 도착지를 정해놓고 그전 계단을 밟았을때 밟지 않았을 때 중의 최댓값을 구해나가 memorization을 한다.  ⬇️ 코드import sysinput = sys.stdin.readlineN = int(input())arr = list()for _ in range(N): arr.append(int(input()))DP = [0] * (N+1)DP[1] = arr[0]if N >=2: DP[2] = DP[1] + arr[1]for i in range(3, N+1): DP[i] = max(DP[i-2] + arr[i-1], DP..

https://www.acmicpc.net/problem/1700✔ 유형 : 그리디✔ 문제 풀이: 멀티탭에서 콘센트를 뽑을 때 어떤 우선순위로 뽑을지 기준을 올바르게 정해야함⬇️코드import sysinput = sys.stdin.readlineN, K = map(int, input().split())# N : 멀티탭 구멍의 개수, K = 전기 용품 총 사용 횟수schedule = list(map(int, input().split()))# 전기용품의 이름이 k이하의 자연수로 사용 순서대로 주어진다.multi_tab = [] # always len(multi_tab) == Nresult = 0#Schedule 순회for i in range(0, len(schedule)): # O(n) if sched..

https://www.acmicpc.net/problem/3055✔ 유형 : BFS✔ 문제 풀이: 시간당 고슴도치의 위치와, 시간당 물의 위치를 매 주기마다 업데이트 하고, 물도착시간이 고슴도치의 도착시간보다 느릴 때 고슴도치가 이동 가능함을 이용해 문제를 해결한다. 최소한으로 도착했을 때의 시간을 알아야 하기 떄문에 BFS를 사용한다. 코드import sysfrom collections import dequeinput=sys.stdin.readline # input함수 바꾸기# 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'# 비버의 굴 = D# 귀여운 고슴도치 = S# 매 분기 도치는 4방향중 한칸 이동가능. 물은 매분마다 비어있는 곳으로 확장. 한변을 공유하는 곳이면..

https://www.acmicpc.net/problem/2665✔ 유형 : 다익스트라✔ 문제 풀이: 문제에서 구하고자 하는 것은 최단 거리가 아니라 검은 방을 최대한 적게 지나야 하는 것이다.시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데,/ 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.문제에 흰 방에 대한 최소 기준이 없다. 이 문제의 목표는 1. 처음에서 끝으로 도달2. 검은 방을 적게 거침 다익스트라 : 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘. 다익스트라 알고리즘을 이용하여 최단거리 = 검은방으로 바꾼 횟수로 문제를 해결하면 된다. 코드import ..

https://www.acmicpc.net/problem/2294 ✔ 유형 : DP✔ 문제 풀이: 여러개의 하위 문제를 먼저 푼후 그 결과를 쌓아올려 주어진 문제를 해결한다. 메모- 처음에 DFS로 풀었는데, 메모리 초과나서 방법을 찾다가 DP를 공부하고 DP로 풀었다. 근데 이게 정답인듯!!! DP 풀이1. 테이블 정의    D[i] = K 로 만들기 위해 필요한 연산 횟수의 최소값 2. 점화식    D[15] = D[14] + 1  ( 1을 더한 이유는 D[15-1]에 1을 더하는 연산 한번을 더하면 D[15]이기 때문)    D[15] = D[9] + 1  ( 1을 더한 이유는 D[15-6]에 5를 더하는 연산 한번을 더하면 D[15]이기 때문)    D[15] = D[3] + 1  ( 1을 더한 ..