흙금이네 블로그

아이디어 동적 계획법으로 피보나치 수를 구해 나간다. 풀이 #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..

아이디어 전깃줄이 교차하지 않으려면 전깃줄들이 연결된 A의 위치 값이 증가할 때 B의 위치 값도 증가해야 한다. 따라서 전깃줄들을 A의 위치 값 기준으로 오름차순으로 정렬하고, B의 위치 값이 증가하는 가장 긴 수열의 길이를 구한다. 풀이 전깃줄이 연결된 A의 위치 값과 B의 위치 값을 튜플로 리스트 line에 저장하고, line을 오름차순 정렬한다. 1로 채워진 N 크기의 리스트 dp를 생성하고, dp에 증가하는 수열의 가장 긴 길이를 저장해 나간다. j 번째 전깃줄이 연결된 B의 위치 값이 i 번째 전깃줄이 연결된 B의 위치 값보다 크고, dp[i]+1와 비교해 dp[j]를 갱신한다. 마지막에 전체 전깃줄 개수 N에서 가장 긴 증가하는 수열의 길이 max(dp)를 뺀 값을 출력한다. import sy..

아이디어 세그먼트 트리로 특정 범위에서의 최솟값을 저장해두고 찾는 범위에 대해 빠르게 처리한다. 풀이 2357번 최솟값과 최댓값 문제에서 최솟값만 고려하여 풀 수 있다. N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 tree를 만든다. tree의 리프 노드들에 N개의 수를 입력 받고, for문에서 tree의 부모 노드들을 두 자식 노드 중 더 작은 값으로 저장한다. 값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다. M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값을 출력한다. 함수 find에서는 리프 노드에서부터 차례로 부모 노드로 올라가며 최솟값을 res에 저장한다. s%2 == 1 또는 e%2 == 0..

아이디어 거리가 먼 두 센서는 각각 다른 집중국과 통신하도록 한다. 풀이 #1 (Python) 오름차순 정렬된 센서 좌표를 리스트 sensor에 입력 받고, 센서 간 거리를 오름차순 정렬하여 리스트 D에 저장한다. N-1개의 센서 간 거리 중 가장 큰 값을 K-1개 제외할 수 있으므로 거리가 짧은 순으로 N-K개 값의 합을 출력한다. def solution(): N = int(input()) K = int(input()) sensor = sorted(map(int, input().split())) D = sorted([sensor[i+1]-sensor[i] for i in range(N-1)]) print(sum(D[:N-K])) solution() 풀이 #2 (JavaScript) 풀이 #1과 마찬가지..

아이디어 세그먼트 트리로 특정 범위에서의 최솟값과 최댓값을 저장해두고 찾는 범위에 대해 빠르게 처리한다. 풀이 N보다 큰 2의 거듭제곱 중 가장 작은 값의 두 배 크기로 0으로 채워진 리스트 min_tree를 만든다. min_tree의 리프 노드들에 N개의 수를 입력 받고, min_tree를 복제하여 max_tree로 저장한다. for문에서 min_tree와 max_tree의 부모 노드들을 각각 두 자식 노드 중 더 작은 값과 더 큰 값으로 저장해 나간다. min_tree에서 값이 0인 자식 노드가 포함되어 있는 경우 부모 노드에 0이 아닌 자식 노드의 값을 저장한다. M개의 a, b 쌍을 입력 받아 함수 find를 호출하여 반환된 최솟값과 최댓값을 언패킹하여 출력한다. 함수 find에서는 리프 노드에서..