alpaca Labs 님의 블로그

import sysinput = sys.stdin.readlinedef lis_length(arr): n = len(arr) dp = [1] * n for i in range(1, n): for j in range(i): if arr[i] > arr[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)# 입력 처리n = int(input())number = list(map(int, input().split()))# 최장 증가 부분수열의 길이를 계산maxcount = lis_length(number)print(maxcount)https://www.acmicpc.net/problem/11053문..

https://www.acmicpc.net/problem/30804문제은하는 긴 막대에 N$N$개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1$1$부터 9$9$까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,SN$S_1, S_2, \cdots, S_N$번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a$a$개, 뒤에서 b$b$개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b$S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_..

https://www.acmicpc.net/problem/21736문제2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 도연이가 다니는 대학의 캠퍼스는 N×M$N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 (x$x$, y$y$)에 있다면 이동할 수 있는 곳은 (x+1$x+1$, y$y$), (x$x$, y+1$y+1$), (x−1$x-1$, y$y$), (x$x$, y−1$y-1$)이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람..

https://www.acmicpc.net/problem/11403문제가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.출력총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.예제 입력 1 복사..

https://www.acmicpc.net/problem/7662문제이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자..

https://www.acmicpc.net/problem/11279문제널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.출력입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열..

https://www.acmicpc.net/problem/6064문제최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 로 표현되고, 11번째 해는 로 표현된다. 은 13번째..

https://www.acmicpc.net/problem/10826피보나치 구현이다.import sysinput = sys.stdin.readlinefibo = [0,1]n = int(input())for i in range(2,n+1): fibo.append(fibo[i-1] + fibo[i-2])print(fibo[n])

https://www.acmicpc.net/problem/9655 문제돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.입력첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)출력상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. dp 관련 문제는 일단 규칙을 찾아야 하는 것이기 때문에 규칙을 찾기위해 계산해 보았다.1개이면 sk 승2개이면 cy 승3개 sk 승4개 cy 승5개 sk 승6개 cy 승7개 sk 승8..

https://www.acmicpc.net/problem/2747간단한 dp 문제이다.n = int(input())fibo = [0,1]if n == 0: print(0)elif n == 1: print(1)else: for i in range(2,n+1): fibo.append(fibo[i-2] + fibo[i-1]) print(fibo[n])