흙금이네 블로그

아이디어 동적 계획법을 이용해 각 칸에서 이동할 수 있는 칸의 경우의 수를 증가시켜 나간다. 풀이 #1 (Python) 게임판의 수를 2차원 리스트 board에 저장하고, 이동 경로의 수를 저장하는 0으로 채워진 2차원 리스트 dp를 생성한다. board의 가장 오른쪽 아래 칸과 dp의 가장 왼쪽 위 칸에 각각 1을 저장한다. board의 가장 오른쪽 아래 칸 값을 1로 바꿔 해당 칸 dp에 해당 칸 경로의 수를 더하는 것을 막는다. 이중 for문에서 현재 칸 (i, j)에서 이동할 수 있는 칸 (i+board[i][j], j)와 (i, j+board[i][j])의 dp에 현재 칸 경로의 수를 더한다. import sys input = sys.stdin.readline def solution(): N =..

아이디어 누적합으로 S에서 홀수 원소들을 최대 K번 삭제한 연속된 짝수 수열의 길이를 구한다. 풀이 22857번 가장 긴 짝수 연속한 부분 수열 (small)의 풀이 #2와 같다. 리스트 arr에는 홀수 원소로 구분된 짝수로 이루어진 수열의 길이를 누적합으로 저장한다. for문에서 S의 각 원소가 홀수면 리스트 arr에 arr의 마지막 값을 다시 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다. arr의 K 번째 원소까지는 앞의 홀수 원소들을 모두 제거할 수 있으므로 그 마지막 값을 결과값 res에 저장한다. for문에서 K개의 홀수 원소를 제거한 짝수로 이루어진 수열 길이의 최댓값으로 res를 갱신해 나간다. arr의 길이 M이 K보다 작다면 결과값 res에는 누적합의 최댓값이 저장되고, for문..

아이디어 S의 홀수 원소로 구분된 연속된 짝수 수열의 길이를 구한 후 그 길이의 합의 최댓값을 찾는다. 풀이 #1 (Python) 리스트 arr의 초기값으로 0을 넣어두고 S의 각 원소가 홀수면 arr에 0을 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다. 따라서 arr에는 짝수로 이루어진 수열의 길이가 홀수 원소로 구분되어 저장되고, 연속된 arr 원소들의 합은 그 원소 수만큼 S에서 홀수 원소를 삭제한 짝수로 이루어진 수열의 길이와 같다. arr을 복제해 리스트 dp에 저장하고, for문에서 앞의 홀수 원소를 반복 횟수만큼 삭제한 수열의 길이로 dp를 갱신해 나간다. 같은 for문 내에서 구한 값이 현재 결과에 영향을 미치지 않도록 dp의 원소들을 역순으로 갱신한다. def solution()..

아이디어 스택을 이용하여 각 위치에서 해당 직사각형의 높이로 만들 수 있는 가장 큰 직사각형 넓이를 구해 나간다. 풀이 6549번 히스토그램에서 가장 큰 직사각형에서 스택을 이용한 풀이 #2와 같다. 첫 번째 수는 N, 직사각형의 높이들은 sys.stdin.readlines로 H에 입력 받고, H 끝에는 0을 추가한다. 직사각형의 넓이를 구하기 위해 필요한 직사각형의 위치들을 스택 stack에 저장하고, 이 위치로 직사각형 양쪽 끝과 H에서 해당 직사각형의 높이를 알 수 있어 각 위치에서의 직사각형의 면적을 구할 수 있다. for문에서는 차례로 직사각형 높이가 증가하면 그 위치를 스택에 넣고 감소하면 스택에서 위치를 꺼내 그 넓이를 계산한다. 위치 i의 직사각형 높이가 stack[-1] 위치의 직사각형 ..

아이디어 동적 계획법으로 피보나치 수를 구해 나간다. 풀이 #1 (Python) 피보나치 수를 저장하기 위해 0으로 채워진 N+1 크기의 리스트 dp를 생성하고, dp[1]의 값으로 1을 할당한다. for문에서 2부터 N까지의 수에 대해 앞의 두 피보나치 수의 합으로 피보나치 수를 계산하고, dp에 저장한다. N = int(input()) dp = [0]*(N+1) dp[1] = 1 for i in range(2, N+1): dp[i] = dp[i-1]+dp[i-2] print(dp[N]) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동작하며, 입력에 대한 결과값이 number 자료형의 범위를 벗어나므로 BigInt를 사용한다. const fs = require('fs'); const..

아이디어 #1 분할 정복으로 해당 범위에서 만들 수 있는 가장 큰 직사각형의 넓이를 구해 나간다. 풀이 #1 각 테스트 케이스의 첫 번째 수는 N, 나머지 직사각형의 높이들은 H에 입력 받아 N이 0이 아닌 동안 while문을 반복한다. 함수 find에서는 인자로 받은 l부터 r까지의 범위에서 가장 큰 직사각형 넓이를 찾는다. l과 r이 같으면 그 직사각형 높이를 반환하고, 그렇지 않으면 포인터 s와 e에 각각 현재 범위 중간인 m과 m+1을 할당한다. 반환값 res에는 가운데 두 직사각형을 합쳐 만들 수 있는 직사각형의 넓이 h*2와 재귀 호출로 가운데를 기준으로 왼쪽과 오른쪽에서 가장 큰 직사각형 넓이 중 최댓값을 할당한다. while문에서는 s부터 e까지의 범위에서 만들 수 있는 직사각형의 넓이를 ..

아이디어 트라이를 이용하여 단어들의 공통 부분을 확인한다. 풀이 테스트 케이스 수가 입력으로 주어지지 않으므로 try except문으로 입력이 주어지는 동안 while문을 반복한다. 클래스로 구현한 트라이 trie를 생성하여 insert로 단어들을 트라이에 넣고, search로 결과값 res에 입력 횟수를 더한다. 트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다. insert 메서드는 단어의 문자들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성하고, 단어가 끝나는 지점에서는 별 문자를 키로 빈 딕셔너리를 저장한다. search 메서드는 문자의 문자들을 루트 노드에서부터 차례로 찾고, 유일한 문자가 아니면 입력 횟수 cnt를 1 증가시킨다. 결과..

아이디어 #1 트라이를 이용하여 접두사인 문자열의 개수를 센다. 풀이 #1 예전에 for문으로 접두사를 찾는 코드를 PyPy3로 제출해서 통과했었는데 재채점 후 시간 초과가 되어 다시 풀어보았다. 클래스로 구현한 트라이 trie를 생성하여 insert로 문자열들을 트라이에 넣고, search로 접두사 여부를 판단한다. 트라이 객체 생성 시 루트 노드를 가리키는 root에 빈 딕셔너리를 할당한다. insert 메서드는 문자열의 문자들이 루트 노드에서부터 차례로 자식 노드로 존재하지 않으면 자식 노드를 새로 생성한다. search 메서드는 문자열의 문자들을 루트 노드에서부터 차례로 찾고, 문자열이 존재하면 1, 그렇지 않으면 0을 반환한다. import sys input = sys.stdin.readline..

아이디어 세그먼트 트리로 구간 곱을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 2042번 구간 합 구하기 문제와 유사한 문제로, 합이 아닌 곱을 저장하면 된다. 구간 곱을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 1로 채워진 리스트 tree를 만든다. 트리의 리프 노드들에는 순서대로 N개의 수를 입력 받고, for문에서 각 부모 노드에 두 자식 노드의 곱을 저장한다. 이후 for문에서는 a가 1이라면 해당 트리 리프 노드의 수를 변경한 후 함수 update를, a가 2라면 함수 multiply를 호출한다. 함수 update에서는 리프 노드의 부모 노드부터 루트 노드까지 다시 계산하고, 재귀 호출로 루트 노드를 벗어나면 종료한다. 함수 multiply..

아이디어 회의 시간을 정렬하여 회의 시간이 겹치면 회의실 수를 증가시킨다. 풀이 #1 (Python) 회의 시작 시간과 끝나는 시간을 튜플로 오름차순 정렬하여 리스트 meeting에 저장한다. 리스트 time은 회의가 끝나는 시간들을 최소 힙의 형태로 저장하며, 처음에는 첫 회의가 끝나는 시간을 저장한다. for문에서는 두 번째 회의부터 시작 시간과 끝나는 시간을 각각 s와 e로, 가장 빨리 끝나는 이전 회의 시간을 t로 둔다. e를 우선 time에 추가한 후 s와 t를 비교해 회의 시간이 겹치면 t를 다시 추가하고, 그렇지 않으면 t는 time에서 제거한다. import sys, heapq input = sys.stdin.readline def solution(): N = int(input()) mee..