문제 www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 풀이 DFS나 BFS를 이용해서 풀 수 있는 기본적인 그래프 탐색 문제다. 코드 BFS import sys, collections while True: w, h = map(int, sys.stdin.readline().split()) if w == 0 and h == 0: break g, lands, visited = [], [], [[0 for _ in range(w)] for _ in range(..
문제 www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 간단한 문제다. DFS 탐색이나 조합을 이용해서 풀 수 있다. 코드 from itertools import combinations import sys while True: input = [int(x) for x in sys.stdin.readline().split()] k = input[0] if k == 0: break input = input[1:] combis = list(combin..
1. FastAPI란? 파이썬 3.6+를 기반으로 빠르게 API 서버를 구축할 수 있게 하는 새로운 웹 프레임워크이다. Django에 비해 가벼우면서도 빠른 속도를 자랑한다. 2. 주요 특징 NodeJS 및 Go와 비슷한 성능, 현존하는 파이썬 웹 프레임워크 중 가장 빠르다. 개발 속도가 빠르다 버그가 적다. 직관적이다 간편하다. 코드 중복을 최소화한다. 견고하다, 대화형 자동 설명서를 사용해서 실행 가능한 코드를 구축할 수 있다. 개방형 API 표준(OpenAPI&JSON)을 기반으로 한다. Django나 Flask 등 기존 파이썬 웹 프레임워크에 비해 레퍼런스는 적지만, 공식문서가 아주 잘 되어있다. 앞으로 FastAPI를 이용해 프로젝트를 진행할 생각이고 관련된 내용을 블로그에 업로드할 예정이다. ..
문제 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 이 문제는 두 가지의 작은 문제로 분할하여 생각해볼 수 있다. 1) 벽을 어떻게 세울 것인가? 2) 어떻게 탐색을 할 것인가? BFS/DFS문제를 어느 정도 접해본 사람이라면 2)는 문제가 되지 않을 것이다. 그러나 문제는 바로 1)이다. 이 문제의 경우엔 n, m의 범위가 작기 때문에 브루트 포스를 이용하면 된다. 재귀를 이용하는 방법도 있지만, 시간을 줄이기 위해 처음 입력을 받을 때부터 빈 칸(0)의 좌표를..
문제 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 n개의 카드를 갖기 위해 지불해야 하는 금액 DP[n]은 DP[n-k] + DP[k]으로 표현할 수 있다. 예를 들어 n=5이면 다음과 같다. DP[5] = max(DP[5], DP[4] + DP[1], DP[3] + DP[2]) 즉, 점화식은 그대로 DP[n] = DP[k] + DP[n-k]가 되며 이를 위해 DP[n]엔 모두 P[n]로 초기화했다. 코드 import sys n = int(input()) ..
