https://www.acmicpc.net/problem/4150 4150번: 피보나치 수 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력 www.acmicpc.net 풀이 1 피보나치 수를 점화식을 사용해서 문제를 풀어준다. # 4150번 피보나치 수 n = int(input()) # dp 생성 fibo = [0, 1] for i in range(2, n+1): fibo.append(fibo[i-1] + fibo[i-2]) print(fibo[n]) 출력결과 풀이 2(시간초과) 재귀함수 사용하게되며 시간초과 일..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 풀이 A의 정렬을 내림차순으로 만들어준 뒤 A의 앞부터 끝까지 B의 최댓값과 곱해주는 방법을 이용한다. B의 최댓값은 한번 뽑으면 pop을 통해 지워준다. # 1026번 보물 import sys input = sys.stdin.readline n = int(input()) a_li = list(map(int, input().split())) b_li = list(map(int, input(..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 사용해서 풀어주었다. 블로그 글 참고. https://sunghyun98.tistory.com/66 [알고리즘] 플로이드 워셜 최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 sunghyun98.tistory...

최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 구하는 다익스트라 알고리즘과 플로이드 워셜은 다르다. 다익스트라 알고리즘은 1차원 리스트를 이용하지만 플로이드 워셜 알고리즘은 2차원 리스트를 사용한다. 또한 다익스트라는 방문하지않은 노드 중에서 최단경로를 찾지만 플로이드 워셜은 방문하지않았는지 했는지 관심이 없다. 플로이드 워셜의 점화식 노드의 개수가 N일 때 N번 만큼 2차원 리스트를 갱신하다. 1~N번까지의 노드를 한번씩 K로 정해준 뒤 K를 제외한 N-1개의 노드 중에서 서로 다른 노드 A, B를 고른다. K를 거쳐가는 A-K 경로와 K-B 경로의 가중치를 더해서 기..

enumerate( )은 파이썬의 내장함수이다. enumerate는 이터레이터를 지연 계산 제너레이터로 감싸준다. iterator의 원소값과 루프 인덱스 쌍으로 튜플형식으로 되돌려준다. 만일 우리가 리스트의 원소와 인덱스 값을 같이 출력 할때는 어떻게 표현할까? 보통 리스트의 인덱스 값과 리스트의 원소값을 같이 출력할 때 range(리스트의 길이)를 사용한다. >>> color = ['파랑', '노랑', '초록', '검정'] >>> for i in range(len(color)): print(f'리스트 color의 {i}번째 인덱스의 원소는 {color[i]}이다.') 리스트 color의 0번째 인덱스의 원소는 파랑이다. 리스트 color의 1번째 인덱스의 원소는 노랑이다. 리스트 color의 2번째 인..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 숨바꼭질 문제 시리즈의 4편이다. 다른점이 있다면 거쳐온 경로를 출력해야한다는것이다. move 리스트를 만들어서 새로운 점으로 도달하기전에 거쳐온 점을 저장해서 for문으로 출력해준다. 대신 값은 시작점부터 출력해야하기에 reveres를 해주었다. # 13913 숨바꼭질 from collections import deque def bfs(): queue = ..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 음수간선이 포함되었기에 벨만 포드 알고리즘을 사용한다. 만일 n번의 시도에서도 최단경로간 갱신된다면 음수간선이 존재한다. # 1865번 웜홀 import sys input = sys.stdin.readline INF = int(1e9) def bf(): distance = [INF] * (n+1) # 시작 노드에 대해서 초기화 distance[1] = 0 # 전체 n번의 라운드(..

https://www.acmicpc.net/problem/2563 2563번: 색종이 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 풀이 2차원배열로 구현한 도화지 위에 색칠을 해준 뒤 색이 칠해진 칸을 전부 다 더해주면 답이 나온다. # 2653번 색종이 n = int(input()) # 도화지 구현 graph = [[0]*101 for _ in range(101)] for _ in range(n): a, b = map(int, input().split()) for i in range(a, a+10): for j in range(b, ..