흙금이네 블로그

아이디어 루트 노드에서 시작한 DFS로 리프 노드에서부터 서브 트리에 속한 노드 개수를 구해 나간다. 풀이 #1 간선 정보를 2차원 리스트 graph에 저장하고, 서브 트리의 노드 개수를 저장하는 N+1 길이의 리스트 dp를 만든다. 함수 dfs에서 현재 노드의 서브 트리에 속한 노드 개수를 저장하는 cnt를 현재 노드를 고려하여 1로 초기화한다. for문에서 자식 노드들의 간선 정보에 포함된 현재 노드를 지우고, 자식 노드들의 반환값을 cnt에 더한다. 자식 노드들의 반환값을 모두 더한 cnt를 현재 노드 번호를 인덱스로 dp에 저장한 후 반환한다. 리프 노드에서는 for문이 실행되지 않고 처음 저장된 1이 그대로 반환된다. 루트 노드을 인자로 함수 dfs를 호출한 후, 쿼리에 따라 서브 트리의 노드 ..

아이디어 DFS과 백트래킹으로 남은 포지션에 선수들을 채워 나가며 능력치 합의 최댓값을 찾는다. 풀이 #1 (Python) 각각의 테스트 케이스에 대해 선수들의 능력치를 리스트 S에 입력 받는다. 메모리 절약과 DFS에서 빠른 접근을 위해 능력치가 0이 아닌 선수들만 인덱스와 능력치를 추가해 나간다. 포지션 할당 표시를 위해 0으로 채워진 리스트 visited를 생성하고 함수 dfs를 호출한다. 함수 dfs에서는 차례로 i 번째 선수를 적합한 포지션 중 남은 포지션에 배치하여 할당 표시 후, 현재 선수의 능력치 a를 능력치 합 total에 더하여 다음 선수로 함수를 재귀 호출한다. 배치가 끝나면 결과값 res와 능력치 합 total을 비교해 결과값을 능력치 합의 최댓값으로 갱신해 나간다. import s..

아이디어 부분 문자열들의 팰린드롬 여부를 확인하고 동적 계획법으로 분할 최소 개수를 구해 나간다. 풀이 #1 S의 길이를 N에 저장하고, S의 부분 문자열이 팰린드롬인지 여부를 저장하기 위한 2차원 리스트 is_pal을 만든다. is_pal[i][j]는 문자열 S의 인덱스 i부터 인덱스 j까지의 부분 문자열이 팰린드롬이면 1, 그렇지 않으면 0을 나타낸다. 팰린드롬 분할 최소 개수를 저장하기 위해 0으로 채워진 N+1 길이의 리스트 dp를 만든다. 이후 코드상 인덱스 에러 방지를 위해 문자열 S에서 인덱스 j까지의 팰린드롬 분할 최소 개수는 dp[j+1]에 저장한다. for문은 1부터 시작하므로 is_pal[0][0]과 dp[1]은 for문 실행 전에 저장한다. 길이가 1인 부분 문자열과 바로 앞의 문자..

아이디어 DFS로 넴모들을 격자판에 배치하고 2×2 사각형 칸에 모두 넴모가 배치된 경우는 더 탐색하지 않는다. 풀이 #1 (Python) N이나 M이 1인 경우 2×2 사각형 칸이 존재할 수 없으므로 격자판에서 넴모를 배치하는 모든 경우의 수를 출력한다. 그렇지 않으면 넴모 배치를 위한 2차원 리스트 visited를 만드는데, 인덱스 에러 방지를 위해 행과 열 크기를 1씩 늘린다. (1, 1)을 시작점으로 하여 방문 표시 후 함수 dfs를 호출하고, 시작점 방문 표시를 지우고 다시 함수 dfs를 호출한다. 함수 dfs에서는 현재 칸을 기준으로 현재 칸, 위쪽 칸, 왼쪽 칸, 좌상단 칸에 모두 넴모가 배치되면 백트래킹으로 종료한다. 격자판 한 행씩 왼쪽에서 오른쪽으로 넴모들을 배치해 나가고, 종료 없이 ..

아이디어 아이들 수에서 최장 증가 부분 수열의 길이를 뺀다. 풀이 리스트 child에 아이들의 번호를 입력 받아 저장하고, 1로 채워진 N 길이의 리스트 dp를 만든다. 이중 for문에서 j번째 아이의 번호가 앞에 있는 i번째 아이 번호보다 크면 증가 부분 수열 길이를 비교해 갱신한다. 마지막에 아이들 수 N에서 최장 증가 부분 수열의 길이를 빼서 출력한다. import sys N = int(input()) child = list(map(int, sys.stdin.readlines())) dp = [1]*N for i in range(N-1): for j in range(i+1, N): if child[i] < child[j] and dp[j] < dp[i]+1: dp[j] = dp[i]+1 print(..

아이디어 DFS로 주어진 연산자로 가능한 식을 만들어 그 최댓값과 최솟값을 찾는다. 풀이 #1 (Python) 덧셈, 뺄셈, 곱셈, 나눗셈을 수행하는 람다식들을 리스트 cal에 저장한다. 리스트 operator에 각 연산자의 개수를 저장하고, 최댓값과 최솟값을 저장하는 리스트 res를 생성한다. 함수 dfs에서는 재귀 호출로 주어진 연산자를 사용하여 식을 만들고, 식을 모두 만들면 결과값과 비교하여 갱신해 나간다. cal = [lambda a, b: a+b, lambda a, b: a-b, lambda a, b: a*b, lambda a, b: a//b if a > 0 else -(-a//b)] def dfs(idx, total, a, s, m, d): global res if idx >= N: if t..

아이디어 동적 계획법으로 암호를 구성하는 숫자들이 직전의 숫자와 붙을 수 있는지 여부를 확인하여 가짓수를 구한다. 풀이 10과 20을 제외하고 0으로 시작하거나 30처럼 0이 포함된 암호는 해석할 수 없으므로 0을 출력한다. elif문에서 0이 아니면서 N의 길이가 1인 암호는 1을 출력한다. 그 외의 경우는 1로 채워진 N+1 길이의 리스트 dp를 생성하고, for문에서 암호를 구성하는 숫자들을 차례로 확인한다. 만약 현재 숫자가 0인 경우 직전 숫자와 붙여야 하므로 앞의 숫자 이전의 경우로 되돌린다. 직전 숫자가 0이 아니면서 현재 숫자를 직전 숫자와 붙일 수 있으면 직전 숫자까지의 가짓수와 그 이전 가짓수를 더한다. 그 외에 직전 숫자와 붙일 수 없는 경우는 직전 숫자까지의 가짓수로 저장한다. co..

아이디어 DFS로 가능한 순열 순서를 탐색하되, 백트래킹으로 중간에 500 미만이 되는 순서는 더 탐색하지 않는다. 풀이 #1 (Python) 운동 키트 중량 증가량을 리스트 A에 저장하고, 방문 표시를 위해 리스트 visited를 생성한 후 함수 dfs를 호출한다. 함수 dfs에서는 사용하지 않은 운동 키트들에 대해 visited에 표시한 후, 재귀 호출로 중량 total을 갱신하며 탐색해 나간다. 중간에 중량이 500 미만이 되면 현재 탐색을 종료하고 되돌아가고, 운동 일수 day가 N이 되면 결과값 res를 1 증가시킨다. def dfs(day, total): global res if total = N: res += 1 return for i in range(..

아이디어 1149번 RGB거리와 유사한 문제로, 동적 계획법으로 각 칸에서 가능한 최댓값과 최솟값을 갱신해 나간다. 풀이 min_dp와 max_dp에는 각각 현재 줄에서 각 칸의 가능한 누적 점수 최솟값과 최댓값을 저장하고, min_prev와 max_prev는 각각 이전 줄까지 각 칸의 누적 점수 최솟값과 최댓값을 저장한다. 차례로 숫자 세 개를 a, b, c에 입력 받고, 이전 줄에서 내려올 수 있는 누적 점수와 더해 min_dp와 max_dp를 갱신한다. min_dp와 max_dp 갱신 이후 min_prev와 max_prev에 각각 현재 min_dp와 max_dp을 저장하고 다음 for문을 진행한다. import sys input = sys.stdin.readline def solution(): N ..

아이디어 버블 소트는 1회전마다 바로 뒤의 수보다 큰 앞의 수가 한 칸씩 뒤로 이동하며 정렬된다. 따라서 정렬 후 수들이 뒤로 이동한 거리의 최댓값을 구한다. 풀이 딕셔너리 A에 순서를 키로, 수를 값으로 저장하고, 수가 작은 순으로 그 순서를 정렬한다. for문에서 정렬 전의 순서에서 정렬 후의 순서를 뺀 값의 최댓값을 res에 저장한 후, 1 증가시킨 res를 출력한다. import sys input = sys.stdin.readline def solution(): N = int(input()) A = dict() for i in range(N): A[i] = int(input()) A = sorted(A, key=lambda i: A[i]) res = 0 for i in range(N): res =..