우노

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42576 풀이 해당 문제는 아래 3가지 방법으로 해결할 수 있습니다. 해결책 1 : 두 배열을 정렬한 뒤, 루프를 통해 1:1 비교를 하고, 서로 다른 항목을 찾는 방법 해결책 2 : 해시를 사용하는 방법 해결책 3 : collections.Counter를 사용하는 방법 해당 포스트에선 “해결책 3”에 대한 설명을 다루고 있습니다. collections.Counter는 리스트에 존재하는 각 요소의 개수를 세주는 모듈입니다. 세부 설명은 아래 예제 코드와 같습니다. 코드 import collections def solution(participant, completion): # 1. Count..

문제 링크 https://www.acmicpc.net/problem/2240 풀이 예제 입력1에 대한 DP 테이블은 아래와 같이 구성할 수 있습니다. 행 : 지난 초 (i) 열 : 사람이 움직인 횟수 (j) dp[i][j] : i초까지 j번 움직였을 때, 얻을 수 있는 최대 자두 수 DP 테이블은, i초에 자두를 먹을 수 있는 조건과 먹을 수 없는 조건을 통해 채울 수 있습니다. 자두를 먹을 수 있는 조건 i초에 자두가 2번 나무에서 떨어지고, 사람의 이동 횟수가 홀수라면(j % 2 == 1), 현재 2번 나무에 위치해 있다는 뜻이므로, 자두를 받아먹을 수 있음 dp[i][j] = max( i-1초 때 j 열의 자두 수, i-1초 때 j-1 열의 자두 수 ) + 1 이전 위치로부터 움직여서 받아 먹을 것..

문제 링크 https://www.acmicpc.net/problem/10844 풀이 자릿수 N이 주어졌을 때, 해당 자릿수의 자연수 중에서 계단 수를 만족하는 자연수는 몇개인지? 1의 자리 자연수들 중, 1~9는 계단 수를 만족하므로, 총 9개가 계단 수가 됩니다. 해당 문제는 아래 점화식과 2차원 DP 테이블을 사용해 해결할 수 있습니다. dp[자릿수][해당 자릿수에서 가장 뒤에 오는 숫자] = 경우의 수 해당 점화식은 아래와 같이 세분화할 수 있습니다. 가장 뒤에 오는 숫자 = 0 dp[자릿수][0] = dp[자릿수 - 1][1] 0의 앞에는 1만 올 수 있기 때문입니다. 가장 뒤에 오는 숫자 = 1~8 dp[자릿수][가장 뒤에 오는 숫자] = dp[자릿수 - 1][가장 뒤에 오는 숫자 - 1] + ..

문제 링크 https://www.acmicpc.net/problem/15486 풀이 예제 입력이 아래와 같다고 가정해봅시다. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 만약, 1일차에 상담을 진행한다면, 해당 상담은 3일동안 진행되며, 4일차부터 다시 상담을 진행할 수 있습니다. 따라서, 1일차에 상담을 진행할 경우의 최대 이익은, ‘1일 차의 상담 금액 + 4일부터의 최대 상담 금액’이 됩니다. 이러한 원리를 뒤쪽 날짜부터 적용함으로써 문제를 해결할 수 있습니다. 뒤쪽 날짜부터, 매 상담에 대하여 ‘현재 상담 일자의 이윤(p[i]) + 현재 상담을 마친 일자부터의 최대 이윤(dp[t[i] + i]])’을 계산하면 됩니다. 이후, 계산..

문제 링크 https://www.acmicpc.net/problem/11053 풀이 최장 증가 부분 수열이란? 각 원소가 이전 원소보다 크다는 조건을 만족하는 부분 수열 중, 가장 긴 부분 수열을 의미합니다. 따라서, 아래 DP 테이블과 점화식을 사용해 해결할 수 있습니다. dp[i] : i번째 수를 마지막 원소로 가지는 부분 수열의 최대 길이 0 ~ i-1번째 원소들을 순서대로 탐색하며, [i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + 1]을 dp[i]로 기록합니다 세부 동작 과정은 아래 링크를 통해 이해할 수 있습니다. https://wooono.tistory.com/575 코드 import sys n = int(sys.stdin.readline()) arr = list(map(int, ..

문제 링크 https://www.acmicpc.net/problem/11055 풀이 증가 부분 수열이란? 각 원소가 이전 원소보다 크다는 조건을 만족하는 부분 수열을 의미합니다. 따라서, 아래 DP 테이블과 점화식을 사용해 해결할 수 있습니다. dp[i] : i번째 수를 마지막 원소로 가지는 부분 수열의 합 0 ~ i-1번째 원소들을 순서대로 탐색하며, [i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + i번째 원소의 값]을 dp[i]로 기록합니다. 코드 import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().rstrip().split(" "))) # dp 테이블 초기화 dp = [x for x in ar..

문제 링크 https://www.acmicpc.net/problem/1912 풀이 i번째 이전까지 연속된 부분 숫자들의 합을 계산하여, 최댓값을 그때그때 기록합니다. i번째 이전까지 연속된 부분 숫자들의 합이, 그냥 i번째 숫자보다 작은 경우, 이전의 기록들은 무의미해집니다. 해당 경우엔, 다시 i번째 숫자부터 연속된 부분 숫자들의 합을 구하면 됩니다. 예제 입력을 사용해, 시뮬레이션을 진행하면 이해가 쉽습니다. [2, 1, -4, 3, 4, -4, 6, 5, -5, 1] 이 주어진 경우 [2, 3, -1, 3, 7, 3, 9, 14, 9, 10] 이 됩니다. 코드 import sys # 정수 n n = int(sys.stdin.readline()) # n개의 정수로 이루어진 수열 arr = list(m..

문제 링크 https://www.acmicpc.net/problem/12852 풀이 DP 테이블과 점화식을 사용해 해결할 수 있습니다. f(x)는 아래 세 가지 값들 중 최솟값이 됩니다. f(x-1) + 1 x가 2로 나눠지는 경우, f(x//2) + 1 x가 3으로 나눠지는 경우, f(x//3) + 1 뒤에 1을 더하는 이유는, 이전 경우의 수로부터 +1 이 되기 때문입니다. 따라서, f(2)부터 f(N)까지 위의 점화식을 사용해 DP 테이블을 채워나가면 됩니다. 또한, 리스트 안에 또 리스트를 넣어, f(x)가 어떤 수들을 거쳐왔는지를 저장해 나가면 됩니다. 따라서, DP 테이블은 아래와 같은 형식으로 채워지게 됩니다. f(0) = [0, []] f(1) = [0, [1]] f(2) = [1, [1,..

문제 링크 https://www.acmicpc.net/problem/1068 풀이 먼저, 각 노드의 부모 배열을 탐색하며, 지워야하는 노드와 해당 노드가 부모 노드인 자식 노드들의 값들을 모두 특정 값(-2)으로 변환합니다. 이후, 각 노드의 부모 배열을 다시 한 번 탐색하며, 값이 -2 가 아니며, 해당 노드를 부모로 하는 노드가 부모 배열에 없을 경우, 리프 노드의 개수를 +1 합니다. 코드 import sys # 트리의 노드의 개수 n = int(sys.stdin.readline()) # 0번 노드부터 N-1번 노드까지, 각 노드의 부모 arr = list(map(int, sys.stdin.readline().rstrip().split(" "))) # 지우려는 노드 remove_node = int(..

문제 링크 https://www.acmicpc.net/problem/1707 풀이 이분 그래프(Bipartite Graph)란? 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다. 탐색을 진행하며, 현재 노드와 이웃한 노드의 색을 확인하고, 동일한 색으로 칠해져있다면, 이분 그래프가 아닌 것으로 판단합니다. 코드 import sys sys.setrecursionlimit(10**6) # 테스트 케이스의 개수 t = int(sys.stdin.readline()) # 현재 노드와 이웃한 노드 탐색 def dfs(node): global result for neighbor in graph[node]: # 이웃 노드에 색칠이 되어있지 않다면 if (visited[..