문제링크:https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 다루는 주제: DP import sys n = int(sys.stdin.readline()) nazzi = [0] * (n + 1) # 리스트 n +1 만큼 만들어두고 ==> nazzi[0] = 0 부터 시작 nazzi[1] = 1 # 1일땐 1 타일 1개 if n > 1: nazzi[2] = 2 # 2일땐 1, 00 2개 # 3일땐 100, 001, 111 3개 # 4일땐 0011, 0000..
문제링크:https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 다루는 주제: DP # 동적 프로그래밍 import sys n = int(sys.stdin.readline()) # n번째 피보나치 수 nazzi = [0, 1] # 리스트 for i in range(2, n + 1): # 리스트에 피보나치 수를 계산하여 저장 nazzi.append(nazzi[i - 1] + nazzi[i - 2]) print(nazz..
문제링크:https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 다루는 주제: DFS # 두개의 -- 가 같은 행에 인접해 있으면 두개는 같은 나무 판자이다 , 두개의 |이 같은 열에 인접해 있으면 같은 나무 판자이다. # dfs 사용해서 다음 노드 확인 후 조건이 맞으면 재귀 import sys n, m = map(int, sys.stdin.readline().split()) # 세로 n 가로 m place = [] for _ in range(n): pla..
문제링크:https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다루는 주제: 다익스트라, 우선순위 큐 # 첫째줄에 N개의 도시 # 둘째줄에 다른 도시로 가는 버스의 개수 M # 셋쨰줄부터 출발 도시 A, 도착 도시 B, 버스 비용 P 정보 입력 # 마지막 줄에 출발 도시 S, 도착 도시 E 입력 # 출발 도시에서 도착 도시로 가는 비용 최소화 최소 비용 출력 # 다익스트라 문제 - 우선순위 큐 사용 - 알아서 최단거..
문제링크:https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 다루는 주제: BFS # N은 도시의 개수 = 노드 개수, M은 도로의 수 = 간선의 개수 1 # 출발하는 도시 X , 최단거리 K # A B는 도시 사이의 단방향 도로 존재 한다는 의미 # 이떄 최단거리 K의 도시가 존재하지 않는다면 -1 출력한다. import sys from collections import d..
문제링크:https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 다루는 주제: DFS # 첫쨰 줄엔 수의 개수 N 과 N-1개수의 연산자 M 입력 # 둘째 줄엔 수열 A 입력 # 셋째줄엔 합이 N-1 인 4개의 정수가 주어지는데 각 + - * / 의 개수가 입력된다. # N개의 수와 N-1의 연산자가 주어졌을떄 만들수있는 식의 최대값과 최소값을 출력하면 된다. # 주의할 점 - 연산자 우선순위를 ..
문제링크:https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 다루는 주제: DFS # N은 정점의 수 N-1은 간선의 수 # 두번쨰 줄은 길이 N의 문자열 A가 주어지는데 0은 실외 1은 실내 # 세번째 줄부터는 트리의 각 정점을 잇는 간선 정보 import sys sys.setrecursionlimit(10 ** 6) N = int(sys.stdin.readline()) # 정점수 A = [0] + list(map(int, s..
문제링크:https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 다루는 주제: DFS import sys sys.setrecursionlimit(10 ** 6) K = int(sys.stdin.readline()) # dfs def dfs(v, color): visit[v] = color # 방문한 v에 색 할당 for i in tree[v]: if visit[i] == 0: # 안가본곳이면 방문 if dfs(i, -color): pass else: ..
