프레소님의 블로그

문제 링크https://www.acmicpc.net/problem/11058사용 알고리즘DP풀이dp 배열의 각 인덱스를 현재 버튼을 i개 눌렀을 때 화면에 출력된 A의 최대 개수로 가정한다.▶︎ `dp[i] = i번 버튼을 눌렀을 때 화면에 출력된 A의 최대 개수` dp 배열의 초기값으로는 단순이 A만 눌렀을 때 화면에 출력된 A의 개수로 설정해두고,각 위치에서 Ctrl-A, Ctrl-C, Ctrl-V를 했을 경우(= `i + 2`) 나올 수 있는 A의 개수로 dp 배열을 갱신해주면 된다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')stdout = io.BytesIO()sys.stdout.write = lam..

문제 링크https://www.acmicpc.net/problem/14267사용 알고리즘DPDFS트리트리에서의 다이나믹 프로그래밍풀이이 문제를 풀기 전에 15681 트리와 쿼리를 먼저 풀어보는 것을 추천한다.이 문제와 유사하면서 트리에서의 다이나믹 프로그래밍에 대해 이해하기 좋은 문제다. 우선, 가장 먼저 할 일은 직속 상사와 부하의 관계를 표현할 tree 구조를 만드는 것이다.관계, 트리에서의 각 노드의 부모, 트리에서의 각 노드의 자손들을 저장할 배열을 만들어준 뒤 입력값을 통해 관계를 설정해주자.n, m = map(int, input().split())connect, node_parent, node_children = [[] for _ in range(n)], [-1] * n, [[] for _ ..

문제 링크https://www.acmicpc.net/problem/2624사용 알고리즘DP풀이3067 Coins과 유사하지만 사용 가능한 동전의 개수가 무한이 아니라는 점에 차이가 있는 문제이다. dp 배열을 만들어야 하는 금액만큼 생성해준 뒤,사용 가능한 모든 동전에 대해서 현재 금액에 도달할 수 있는 경우 해당 동전을 1 ~ 보유 수량만큼 사용했을 경우 도달한 금액에 현재 금액에 도달할 수 있는 경우의 수를 더해준다.예시Input532 31 23 1 초기 상태초기값인 dp[1][0]을 1로 설정해준다.index012345dp[0]000000dp[1]100000 첫번째 동전(Value: 2, Count: 3)과거 상태를 저장하는 dp[0] 리스트에 dp[1]을 복사한 뒤 dp[0][j] 에 도달할 수 ..

문제 링크https://www.acmicpc.net/problem/16500사용 알고리즘DP풀이dp 리스트에 `해당 인덱스까지 words 배열에 존재하는 단어들로 표현할 수 있는가`를 저장한다.초기값인 dp[0]은 1로 두고 s의 인덱스마다 dp[i]가 1일 경우 words 배열에 존재하는 단어들을 체크해서 `s[i:i+len(w)] == w`라면 dp[i+len(w)]를 1로 저장한다. dp[i]까지는 이미 이전에 words 배열에 존재하는 단어들로 만들 수 있음을 확인했기 때문에,우리는 그 후의 s의 부분 문자열에 대해 words 배열에 존재하는 단어들로 s의 부분 문자열과 일치하는 단어들이 있는지 판별해야 하기 때문이다.예시Inputabcefg3abcefgabce 초기 상태index0123456sa..

개요필자는 주로 FastAPI를 사용해서 백엔드 개발을 한다. FastAPI의 자유로움과 성능에 반해 FastAPI를 주로 사용하고 있지만 아직 1.x.x 번대 버전이 출시되지도 않은 만큼 자잘한 버그들이 있는 편이다. 해당 포스트에서는 FastAPI의 버그 중 하나인 매개변수에 별칭(alias) 사용 시 실제 요청에는 해당 매개변수를 포함했음에도 불구하고 매개변수를 찾을 수 없다는 오류를 반환하는 문제에 대해 설명하고자 한다. 버전FastAPI: 0.115.14Pydantic: 2.11.7본론FastAPI는 Pydantic을 기반으로 타입 체크와 타입 힌트를 제공한다. 따라서, 요청에 Pydantic의 BaseModel를 상속받는 클래스를 사용해서 매개변수를 관리(타입 체킹, 포함 여부 등) 할 수 있..

개요웹 개발을 할 때에는 동시성(concurrency)을 신경써야 한다. 예를 들면 간단히 게시글에 좋아요를 누를 수 있는 서비스가 있다고 할 때,사용자 두 명이 "동시에" 좋아요 버튼을 눌렀을 경우 동시성을 무시할 경우 한 사용자의 좋아요만 올라갈 가능성이 발생한다. 이를 경쟁 상태(Race Condition)라고 한다. 이러한 동시성 문제가 발생하지 않도록 하기 위해 데이터베이스의 "락" 등의 방안이 존재한다. 동시성을 무시한 경우, 비관적 락을 사용한 경우, 낙관적 락을 사용한 경우로 나누어 각각 동시에 요청이 들어올 경우 어떤 현상이 발생하는지 정리하고자 한다. 우선 데이터베이스 테이블과 Entity를 만들고 SQLAlchemy의 명시적 매핑(imperatively mapping)을 이용해 Ent..