흙금이네 블로그

아이디어 각 운동기구의 근손실 정도를 정렬하여 차례로 작은 값과 큰 값의 합 중 가장 큰 값을 출력한다. 풀이 #1 (Python) 근손실 정도를 오름차순 정렬 후 T에 저장하고, N이 홀수인 경우 결과값 res에 가장 큰 값을 pop하여 저장한다. for문에서 순서대로 작은 값과 큰 값의 합을 res와 비교하여 더 큰 경우 결과값을 갱신해 나간다. N = int(input()) T = sorted(map(int, input().split())) res = 0 if N%2: res = T.pop() for i in range(N//2): if T[i]+T[-(i+1)] > res: res = T[i]+T[-(i+1)] print(res) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동..

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

아이디어 양이 가장 많은 에너지 드링크에 나머지 에너지 드링크들을 모두 붓는다. 풀이 #1 (Python) N개의 에너지 드링크 양을 리스트 drink에 저장하고, 이들 합에 그 최댓값을 더하고 2로 나눈 값을 출력한다. N = int(input()) drink = tuple(map(int, input().split())) res = (sum(drink)+max(drink))/2 print(res) 풀이 #2 (JavaScript) 풀이 #1과 마찬가지 방식으로 동작한다. Math.max로 찾은 에너지 드링크 양 최댓값의 절반을 초기값으로 두고, reduce로 에너지 드링크들의 양을 반씩 더한다. const fs = require('fs'); const input = fs.readFileSync('/de..

아이디어 동적 계획법으로 두 문자열의 최장 공통 부분 열을 찾아 나간다. 풀이 두 문자열을 각각 S1, S2에 저장하고, 그 길이를 각각 N1, N2에 저장한다. 인덱스 접근의 편리를 위해 1만큼의 여유를 둬서 빈 문자열로 채워진 N2+1 길이의 리스트 dp를 생성한다. 메모리 절약을 위해 dp를 2차원 리스트로 만들지 않고, 현재 행에 대한 처리는 lcs에 하고 dp를 대체해 나간다. lcs[i+1][j+1]에는 S1의 i 번째 문자, S2의 j 번째 문자의 최장 공통 부분 열을 저장한다. S1, S2의 문자가 같을 때 해당 문자들 이전까지의 최장 공통 부분 열에 해당 문자를 더한 문자열을 저장하고, 그렇지 않으면 현재까지 저장된 부분 열 중 더 긴 부분 열의 문자열을 저장해 나간다. def solut..

아이디어 사전 순으로 가장 앞서는 수열이 되기 위한 규칙을 찾는다. 풀이 #1 (Python) 문어들이 1번과 2번 손을 번갈아 잡는 수열이 사전 순으로 가장 앞선다. 그러나 문어의 수가 홀수인 경우 1번과 2번 손만 사용해서는 원을 만들 수 없으므로 3번 손도 사용한다. 따라서 문어 수를 2로 나눠 소수점 이하를 버린 값만큼 1과 2가 담긴 리스트를 반복하고, 홀수면 3도 추가해 언패킹한다. N = int(input()) print(*[1, 2]*(N//2)+[3]*(N%2)) 문자열로 구현할 수도 있는데, 짝수인 경우 끝에 공백이 생기므로 rstrip 메서드로 공백을 제거한다. print(('1 2 '*(N//2)+'3'*(N%2)).rstrip()) 풀이 #2 (JavaScript) 입력으로 주어지..

아이디어 동적 계획법으로 세 문자열의 최장 공통 부분 열의 길이를 찾아 나간다. 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..