💻 준성 개발 일지

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 # 백준 9251번 문제 - LCS str1 = ' ' + input() str2 = ' ' + input() dp = [[0]*len(str1) for _ in range(len(str2))] for i in range(1, len(str2)): for j in range(1, len(str1)): if str2[i] == str1[j]: ..

문제 https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 # 백준 1011번 문제 - Fly me to the Alpha Centauri t = int(input()) for _ in range(t): x, y = map(int, input().split()) distance = y - x cnt = 0 move = 1 move_plus = 0 # 이동한 거리의 합 while move_plus < ..

문제 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 # 백준 2447번 문제 - 별 찍기 10 n = int(input()) def star(l): if l == 3: return ['***','* *','***'] arr = star(l//3) stars = [] for i in arr: stars.append(i*3) for i in arr: stars.append(i+' '*(l//3)+i) for i i..

문제 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 # 백준 7662번 문제 - 이중 우선순위 큐 import sys import heapq input = sys.stdin.readline test = int(input()) for _ in range(test): max_heap, min_heap = [], [] visit = [0] * 1_000_001 n = int(input()) for i in range(n): cmd = in..

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 # 백준 1520번 문제 - 내리막 길 from collections import deque dx, dy = [0,0,-1,1], [1,-1,0,0] m, n = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(m)] dp = [[-1]*n for _ in range(m)] cnt = 0 def..

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 풀이 # 백준 1991번 - 트리 순회 n = int(input()) tree = {} for _ in range(n): root, left, right = input().split() tree[root] = [left, right] def preorder(root): if root != '.': print(root, end='') preorder(tree[root][0]) # l..

문제 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 # 백준 15654번 문제 - N과 M(5) from itertools import permutations n, m = map(int, input().split()) new_list = list(map(int, input().split())) new_list = sorted(new_list) #순서대로 나오게 정렬 먼저 for numbers in list(permutations..

문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 # 백준 2206번 문제 - 벽 부수고 이동하기 from collections import deque n, m = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input()))) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] def bfs..

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 # 백준 1753번 문제 - 최단경로 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) import heapq n, m = map(int, input().split()) k = int(input()) INF = int(1e9) graph = [[] * (n+1) for _ in r..

문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 # 백준 9663번 문제 - N-Queen import sys input = sys.stdin.readline n = int(input().rstrip()) answer = 0 row = [0] * n def is_promising(x): for i in range(x): if row[x] == row[i] or abs(row[x]-row[i]) == abs(x-i): return False retur..