흙금이네 블로그

아이디어 동적 계획법으로 세 문자열의 최장 공통 부분 열의 길이를 찾아 나간다. LCS는 Longest Common Subsequence의 약자이기도 하고, Longest Common Substring의 약자이기도 하다. 부분 열(Subsequence)은 어떤 열의 요소들을 원래 순서에 따라 그 일부를 나열한 것이고, 부분 문자열(Substring)은 어떤 문자열 내에 포함된 연속적인 문자열을 의미한다. 따라서 최장 공통 부분 열과 최장 공통 부분 문자열은 공통 부분 요소들의 연속성에 차이가 있다. 부분 열은 연속되지 않은 요소들로도 구성할 수 있지만, 부분 문자열은 연속된 요소들로 구성된다. 이 문제에서는 각 문자열에서 일부 문자들을 순서대로 나열한 문자열 중 가장 긴 공통 문자열의 길이를 찾아야 한다..

아이디어 동적 계획법과 DFS로 동전을 더 이동할 수 없는 곳에서부터 이동할 수 있는 최대 횟수를 구해 나간다. 풀이 람다식으로 입력으로 주어지는 문자열에서 H는 0으로, 나머지는 정수형으로 바꾼 리스트를 리스트 board에 저장한다. 각 칸의 동전 최대 이동 횟수를 저장하는 2차원 리스트 dp와 각 칸의 방문 여부를 표시하는 2차원 리스트 visited를 만든다. 가장 왼쪽 위칸의 행, 열, 이동 칸 수를 인자로 함수 dfs를 호출한다. 함수 dfs에서는 현재 칸을 이미 방문하여 최대 이동 횟수가 dp에 저장되어 있으면 해당 값을 반환하여 종료한다. dp에 저장되어 있지 않으면 최대 이동 횟수를 저장하는 move에 1을 저장하고, visited에 방문 표시를 한다. 보드의 범위를 벗어나지 않고 이동할 ..

아이디어 에라토스테네스의 체로 소수를 판정하고, 메모이제이션을 사용하여 시간을 단축한다. 풀이 예전에 작성한 코드가 재채점 후 시간 초과가 되어 다시 풀어본 문제로, 메모이제이션이나 불필요한 과정을 생략하여 실행 시간을 줄여야 했다. 에라토스테네스의 체로 소수인 수의 인덱스는 True, 소수가 아닌 수의 인덱스는 False로 하는 리스트 p를 만든다. 이때 입력으로 주어지는 짝수 정수를 두 홀수 소수의 합으로 나타내면 되므로 홀수이면서 소수가 아닌 수만 확인한다. 따라서 i는 3부터 시작하여 2만큼 건너뛰고, j는 i*3에서 짝수 크기만큼 건너뛰어 홀수 인덱스만 확인하도록 한다. 메모이제이션을 위해 딕셔너리 memo를 만들고, n이 0이 아닐 때까지 while문을 반복한다. n이 memo에 존재하면 그대..

아이디어 동적 계획법으로 각 칸에서 만들 수 있는 정사각형 한 변의 크기를 저장해 나간다. 풀이 #1 리스트 dp에 배열 첫 줄을 입력 받고, 결과값을 저장하는 변수 res에 배열 첫 줄에서 가장 큰 값을 저장한다. for문에서 arr에 배열을 한 줄씩 입력 받고, 차례로 arr에서 1로 된 칸들에 왼쪽 칸, 위쪽 칸, 좌상단 칸 중 최솟값을 더한다. 위쪽 칸과 현재 칸은 각각 다음 칸에서 좌상단 칸과 왼쪽 칸이 되므로 하나라도 0인 경우 두 칸을 건너뛰도록 한다. res를 현재 줄의 최댓값과 비교해 갱신하고, 다음 for문을 위해 dp를 arr로 대체한다. res는 정사각형 한 변의 길이를 나타내므로 마지막에 res를 제곱하여 출력한다. import sys input = sys.stdin.readlin..

아이디어 백트래킹으로 가장 작은 수의 좋은 수열을 찾는다. 풀이 #1 (Python) 좋은 수열 중 가장 작은 수는 1로 시작하게 되므로 리스트 stack에 길이 1과 문자열 1을 튜플로 저장한다. while문에서 DFS로 문자열 길이 l과 문자열 s를 꺼내 슬라이싱으로 인접한 두 부분 수열 중 같은 쌍을 찾는다. 같은 쌍이 존재하면 break로 다음 값을 꺼내고, 그렇지 않으면 길이가 N인지 비교하고 N이면 출력 후 종료한다. N이 아니면 stack에 다음 길이와 문자열을 추가하는데, stack은 마지막 값부터 꺼내므로 숫자가 큰 순서대로 넣는다. 가장 먼저 찾은 좋은 수열이 가장 작은 수의 좋은 수열이므로 좋은 수열을 찾으면 결과값 출력 후 while문을 종료한다. N = int(input()) st..

아이디어 루트 노드에서 시작한 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(..