고양이 두 잔

목차 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 풀이 동전의 종류가 특별하지 않고 일반적인 경우 특정 금액을 만드는 동전의 최소 개수를 구하는 문제이다..

목차 문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10}인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}이고, 길이는 3이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 $Ai$가 주어진다. (1 ≤ $Ai$ ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 풀이 가장 어쩌고 수열의 다른 버전이다. 주어진 수열의 감소하는 부분 수열 중 가장 긴 부분수열의 길이를 출력하는 문제. 바로 알고리즘을 푸는 단계를 순서대로 정리하면 다음과 같다. dp리스..

목차 [Python]복붙으로 끝내는 셀레늄 크롤링(1) [Python]복붙으로 끝내는 셀레늄 크롤링(2) 지난 글에서 우리는 크롤링과 셀레늄에 대한 간단한 소개와 그 예를 들어보았다. 그중 셀레늄 소개에서 웹 드라이버를 마치 사용자가 다루듯 할 수 있다는 부분이 있었는데, 이 글에선 그 기능을 간단하게나마 구현해보려고 한다. keyword_naver_tab_2.py 먼저 지난 글에서 가져왔던 네이버 연관검색어를 검색에서부터 시작해 가져오는 로직을 작성하려고 한다. 지난 글에서와는 다른 방식으로 CSS 셀렉터를 찾아서 시작해보자. 먼저 네이버 모바일 홈페이지에 접근한다. https://m.naver.com/ 네이버 모바일 메인 네이버 모바일 메인에서 다양한 정보와 유용한 컨텐츠를 만나 보세요 m.naver..

목차 FastAPI + SQLAlchemy + Pydantic을 이용한 게시판 만들기 [FastAPI]FastAPI 튜토리얼 [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(1) 회원가입 및 로그인 구현(JWT) [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(1.5) 디테일 수정 [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(2-1)Feed CRUD - Model, Service [FastAPI]SQLAlchemy + Pydantic을 이용한 게시판 만들기-(2-2)Feed CRUD - Routes, main.py [FastAPI]SQLAlchemy + Pydantic을 이용한 게시판 만들기-(3)S3 버..

목차 문제 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. $(1 ≤ A_i ≤ 1,000)$ 출력 첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다. 풀이 이 문제는 쓰여있는 대로 주어진 수열의 증가하는 부분수열 중 합이 최대인 경우를 찾는 것이다. 예를 들어 ..

목차 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한 가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 계속해서 수열의 규칙을 찾아 동적계획법으로 푸는 문제이다. 11726번 문제는 아예 피보나치수열과 그 규칙이 같아 생략하기로 했다. 이번 문제도 N을 1씩 증가시키며 규칙을 찾으면 간단한데, 우선 수열을 늘어놓으면 다음과 같다. 1, 1, 3, 5, 11, 21, ... 이를 굳이 수식으로 나타내자면 다음과 같이 쓸 수 있을 것이다. $$a_{n} = 2 * a_{n-2} + ..

목차 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 지난 문제에서 두 가지 값의 조합으로 최솟값을 만들었던 것에 비해, 이번 문제에서는 세 가지 연산을 이용해 최솟값을 찾는다. 먼저 0으로 초기화한 (N + 1) 크기의 dp리스트를 만들고 2부터 시작해 N까지 반복문을 돌며 리스트를 채워나간다. 여기서 2부터 시작..

목차 FastAPI + SQLAlchemy + Pydantic을 이용한 게시판 만들기 [FastAPI]FastAPI 튜토리얼 [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(1) 회원가입 및 로그인 구현(JWT) [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(1.5) 디테일 수정 [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(2-1)Feed CRUD - Model, Service [FastAPI]SQLAlchemy + Pydantic을 이용한 게시판 만들기-(2-2)Feed CRUD - Routes, main.py [FastAPI]SQLAlchemy + Pydantic을 이용한 게시판 만들기-(3)S3 버..

목차 FastAPI + SQLAlchemy + Pydantic을 이용한 게시판 만들기 [FastAPI]FastAPI 튜토리얼 [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(1) 회원가입 및 로그인 구현(JWT) [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(1.5) 디테일 수정 [FastAPI]SQLAlchemy + Pydantic를 이용한 게시판 만들기-(2-1)Feed CRUD - Model, Service [FastAPI]SQLAlchemy + Pydantic을 이용한 게시판 만들기-(2-2)Feed CRUD - Routes, main.py [FastAPI]SQLAlchemy + Pydantic을 이용한 게시판 만들기-(3)S3 버..

목차 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 풀이 문제가 길지만 규칙을 찾으면 간단하다. 동적계획법을 위한 dp리스트를 만든다고 가정하면 dp[1] = 1 dp[2] = 2 dp[3] = 4 dp[4] = 7 ....