프레소님의 블로그

문제 링크https://www.acmicpc.net/problem/1339사용 알고리즘그리디풀이단어들에 등장하는 알파벳에 각각 숫자를 대입해서 반환된 값의 합의 최대를 구하는 문제이다. 이를 구하기 위해서는 등장하는 각 알파벳 별로 모든 단어에서 해당 알파벳이 위치한 자리가 큰 순서대로 숫자를 할당해주면 된다. 예제입력2GCFACDEB 위의 예제에서 등장하는 알파벳은 (A, B, C, D, E, F, G)이다. 알파벳이 등장하는 자리에 따라 가중치를 더 크게 주어야 하기 때문에 모든 단어들에 0을 패딩해 자리수를 맞춰주자.index01234S[0]00GCFS[1]ACDEB 이와 같은 상태에서 자리수별로 가중치를 주게 된다면 아래 표와 같이 되고, 가중치가 높은 순서대로 숫자를 할당해주면 된다.알파벳가중치..

문제 링크https://www.acmicpc.net/problem/2602사용 알고리즘DP풀이천사 or 악마, 현재 밟고 있는 위치, 현재 문자열이 두루마리의 몇 번째 문자열인지를 저장할 DP 배열을 만들어준다. 우선 DP 배열을 초기화하기 위해 두루마리의 맨 처음 문자열을 밟아준다.s, devil, angel = input(), input(), input()dp = [[[0] * len(s) for _ in range(len(devil))] for _ in range(2)]for now in range(len(devil)): if devil[now] == s[0]: dp[0][now][0] = 1 if angel[now] == s[0]: dp[1][now][0] = 1 그 후, 돌다리의 각 ..

문제 링크https://www.acmicpc.net/problem/17845사용 알고리즘DP풀이자주 접할 수 있는 DP 문제이다. 공부 시간에 따른 최대 중요도를 저장하는 DP 배열을 만든 뒤,각 과목별로 `max(현재 최대 중요도, 현재 공부 시간 - 해당 과목의 필요한 공부 시간 + 해당 과목을 공부했을 때 얻을 수 있는 중요도)`를 구하면 된다. 이 때 과목별로 현재 시간에 따른 중요도를 갱신하는 과정에서 `t ~ n + 1`로 반복하면 동일한 중요도가 더해질 수 있기 때문에 뒤에서부터(`n ~ t - 1`) 반복하는 것으로 해결할 수 있다.코드import sys, os, io, atexitinput = lambda: sys.stdin.readline().rstrip('\r\n')stdout = i..

문제 링크https://www.acmicpc.net/problem/1563사용 알고리즘DP풀이여러 방법으로 시도하다 도저히 풀리지 않아 다른 사람의 풀이를 보고 푼 문제이다.나는 출석, 지각, 결석에 따른 경우의 수를 저장하는 배열을 사용하려 했지만 구현 시 현재 출석했을 때 결석의 수를 초기화할 수 없기 때문에 잘못된 방식으로 접근했다. 이 문제를 해결하기 위해 만들어야 할 DP 배열은 i번째 날에 지각, 결석한 횟수에 따른 경우의 수를 저장하는 배열이다.▶︎ `dp[학기의 날짜 수(= n + 1)][가능한 지각 횟수(= 2)][가능한 결석 횟수(= 3)]` 위와 같은 DP 배열을 만들면 현재 날짜의 지각, 결석 횟수에 따른 경우의 수를 저장할 수 있다.현재 날짜의 지각, 결석 횟수에 따라 아래와 같은..

문제 링크https://www.acmicpc.net/problem/2229사용 알고리즘DP풀이문제를 풀어서 설명하면 연속된 학생들끼리 묶어서 조를 구성할 경우, 각 조들의 잘 짜여진 정도의 합의 최댓값을 구하는 문제이다. 따라서, 각 학생별로 해당 학생까지 각 조들의 잘 짜여진 정도의 합의 최댓값을 저장하는 dp 배열이 필요하다.▶︎ `dp[i] = dp[i]까지 각 조들의 잘 짜여진 정도의 합의 최댓값` 그리고 i번 학생까지 조가 잘 짜여진 정도의 합을 알기 위해선,기존에 구했던 0 ~ i번 학생(j라고 가정)에서의 조가 잘 짜여진 정도의 합에`max(i번 학생의 점수, j번 학생의 점수) - min(i번 학생의 점수, j번 학생의 점수)`를 더했을 때 최대가 되는 값을 구하면 된다.코드import s..

문제 링크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를 상속받는 클래스를 사용해서 매개변수를 관리(타입 체킹, 포함 여부 등) 할 수 있..