24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 처음 시도한 코드 n = int(input()) f1, f2 = 0, 0 # 각 함수의 실행 횟수 def fib(n): global f1 if n == 1 or n == 2: f1 += 1 return 1 else: return fib(n-1) + fib(n-2) f = [0] * (n+1) # DP 테이블 초기화 def fibonacci(n): f[1] = 1 f[2] = 1 global f2 for i in range(3, n+1): f[i] =..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 코드 from collections import deque import sys input = sys.stdin.readline m, n = map(int, input().split()) # 가로, 세로 graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) # 익은 토마토의 위치 queue에 추가 queue = deque() for i in range(n): for ..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline # dfs 정의 def dfs(x, y): # 상하좌우 dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] # 네 방향 탐색 for i in range(4): nx = x + dx[i] ny = y + dy[i] # 범위 안에 있고 1이면(=배추이면) 지나간것을 -1로 표시하고 주변 탐색 if (0

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 처음 시도한 코드 math = input().split('-') # '-' 기준 분리 hap = [] for i in math: if i.isdigit(): # 숫자이면 정수로 바꿔 hap에 저장 hap.append(int(i)) else: # 문자열이면 eval 메소드로 식 계산 hap.append(eval(i)) result = hap[0] for i in hap[1:]: # hap의 1번 이후 값들을 순차적으로 result에서 빼줌 result -= ..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제에서 연결 요소의 개수를 구하라고 했지만, 연결 요소의 뜻을 몰라서 헤매고 있었다. 하지만 주어진 예제 입력을 직접 손으로 그려보니 연결 요소가 무엇인지 알 수 있었다! 1번 예제 같은 경우는 직접 그래프를 그려보면 다음과 같은 모양으로 그려진다. 125 / 34 형태로, 2개의 그래프이자 2개의 영역으로 나눠진 것으로 볼 수 있다. 2번 예제 같은 경우는 직접 그래프를 그려보면 다음과 같은 모양으..

2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 코드 n = int(input()) # 좌석 수 seat = input() # 좌석 정보 couple = seat.count('LL') # 커플석의 개수 if couple