문제 www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 간단하게 딕셔너리 형태로 트리를 구현했다. 예제 입력으로 생성된 트리는 다음의 형태를 보인다. tree = {'A' : ['B', 'C'], 'B' : ['D', '.'], 'C' : ['E', 'F'], 'E' : ['.', '.'], 'F' : ['.', 'G'], 'D' : ['.', '.'], 'G' : ['.', '.']} 순회는 모두 재귀 형식으로 구현했으며, print문의 위치에 주..
문제 www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 n의 범위가 크므로(최대 100,000) O(n)시간 안에 문제를 해결하는 것이 중요하다. 따라서 동적계획법을 적용하여 풀 수 있다. 최적해는 아래의 두 가지 상황을 고려하여 구할 수 있다. 1) 계속해서 더해간다: 이전 연속합에서 현재 정수를 더한다. 2) 초기화한다: 현재 정수부터 연속합을 다시 구한다. 점화식은 dp[n] = max(dp[n-1]+dp[n], dp[n])이 된다. 그림으로 표현하면 다음과 ..
FastAPI에 MySQL을 연결하는 방법에 대해 알아보자. 프로젝트 구조는 다음과 같다. 1) 프로젝트 구조 2) secrets.json git에 비밀번호나 중요정보를 노출시키지 않기 위해 secrets.json에 해당 정보들을 모아둘 생각이다. 꼭 .gitignore파일에 secrets.json을 추가시켜야 한다. user: 유저 이름 password: 비밀번호 host: 호스트 주소 port: 포트번호 database: 스키마 이름 2) database.py MySQL에 연결시키기 위해 sqlalchemy와 pymysql모듈을 설치해준다. $pip install sqlalchemy $pip install pymysql DB_URL은 "mysql+pymysql://[유저이름]:[비밀번호]@[호스트주소..
문제 www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 정점을 탐색하는 건 어렵지 않지만, 경로를 기록하는 것이 까다롭다. 이차원 리스트에 경로를 저장하면 수월하게 해결할 수 있다. DFS/BFS 탐색 시 탐색을 시작하는 정점(start)을 매개변수로 넘겨주고 방문하는 정점마다 경로에 추가하면 된다. 즉, 현재 정점(cur)을 방문하면 path[start][cur] = 1이 된다. 이때 탐색하는 과정에서 사이클이 존재하는지 여부를 확인해줘야 한다. 코드 import sys sys.setrecurs..
문제 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이 아래의 그림을 통해 점화식을 간단하게 표현할 수 있다. f(n)은 n만큼의 너비를 지니는 타일을 채우는 경우의 수이며 g(n)은 f(n)에서 1x1만큼의 타일을 빼고 채우는 경우의 수다. f(n)는 n이 홀수일 때 f(n) = 0이 되고, g(n)은 n이 짝수일 때 g(n) = 0이 된다. 이를 고려하여 base case를 처리한다. 코드 def solve(n): if n % 2 != 0: return 0 for i in range(2, n+1, 2): f[i] = f[i-2] + 2*g[i-1] for j i..
