알고리즘

파도반 수열[백준 9461] - python

import sys input = sys.stdin.readline def BOJ9461() : T = int(input()) dp = [0] * 102 dp[0] = 1 dp[1] = 1 dp[2] = 1 for i in range(3, 102) : dp[i] = dp[i-3] + dp[i-2] for _ in range(T) : n = int(input()) print(dp[n-1]) BOJ9461() 접근방법 1. 점화식만 찾아내면 문제는 끝난다.(dp 문제들의 핵심인것 같다) 2. 문제에서 다행히 예시를 잘 보여주어서 점화식 찾기가 어렵지 않았다. https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫..

01타일 [백준 1904] - python

정답코드 import sys input = sys.stdin.readline def BOJ1904() : dp = [0] * 1000001 dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 dp[4] = 5 n = int(input()) for i in range(5, n+1) : dp[i] = (dp[i-2] + dp[i-1]) % 15746 print(dp[n]) BOJ1904() 접근 방법 1. 점화식만 떠올리면 끝이다. 2. 나머지 연산을 까먹지 않고 적용하자! https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이..

파이프 옮기기 1 [백준 17070] - python

import sys input = sys.stdin.readline def BOJ17070() : N = int(input()) graph = [] for _ in range(N) : graph.append(list(map(int, input().split()))) answer = [[[0] * N for _ in range(N)] for _ in range(N)] answer[0][0][1] = 1 for x in range(0, N) : for y in range(2, N) : # 가로, 세로 if graph[x][y] == 0 : answer[0][x][y] = answer[0][x][y-1] + answer[2][x][y-1] answer[1][x][y] = answer[1][x-1][y] + a..

가장 긴 증가하는 부분 수열 5[백준 14003] - python

접근 방법 : https://dkrnfls.tistory.com/114 가장 긴 증가하는 부분 수열 4 [백준 14002] - python import sys from bisect import bisect_left input = sys.stdin.readline def BOJ14002(): N = int(input()) A = list(map(int, input().split())) dist = [-1000000001] index = [0] * (N + 1) for i in range(l.. dkrnfls.tistory.com 이 문제에서의 접근방법과 같다!! 장애물 이였던 것 : 0. 값의 범위를 살펴보자 -10억 부터 10억 까지이다. 1. 거리 배열의 맨처음 초기값을 0으로 넣어주면 안된다. -10..

연구소[백준14502] - python

정답 코드 import sys import copy from collections import deque from itertools import combinations input = sys.stdin.readline directions = [[1,0], [-1,0], [0,1], [0,-1]] def bfsAndCountZero(array, viruses) : height = len(array) width = len(array[0]) visited = [[0] * width for _ in range(height)] zero_count = 0 queue = deque() for virus in viruses : queue.append(virus) while queue : curr_x, curr_y = q..

LCS2 [백준 9252] - python

def BOJ9252(): first = input() second = input() array = [[[0, '']] * (len(second) + 1) for _ in range(len(first) + 1)] l = [] for i in range(1, len(first) + 1): for j in range(1, len(second) + 1): if first[i-1] == second[j-1]: array[i][j] = [array[i-1][j-1][0] + 1, array[i-1][j-1][1] + first[i-1]] else: if array[i-1][j][0] > array[i][j-1][0] : array[i][j] = [array[i-1][j][0], array[i-1][j][1]] e..

사다리 [백준 2022] - python

def get_c(x, y, width) : h1 = (x**2 - width**2)**0.5 h2 = (y**2 - width**2)**0.5 c = h1 * h2 / (h1 + h2) return c def BOJ2022() : x, y, c = map(float, input().split()) start, end = 0, min(x,y) res = 0 while (end - start) > 0.000001 : width = (start + end) / 2 res = width if get_c(x, y, width) >= c : # c를 구했는데 기존의 c보다 같거나 크면 w값을 키워주어서 h1, h2의 값을 작게 해주어야 한다. start = width else : end = width print(..

후위 표기식 2[백준 1935] - python

import string def BOJ1935() : n = int(input()) quest = input() numbers = {} for i in string.ascii_uppercase[:n] : numbers[i] = float(input()) stack = [] ord = {'+': 1, '-': 1, '*': 2, '/': 2} for s in list(quest) : if s in ord : second = stack.pop() first = stack.pop() temp = 0 if s == '+' : temp = first + second elif s == '-' : temp = first - second elif s == '*': temp = first * second elif s =..

다각형의 면적 [백준 2166] - python

import sys import math input = sys.stdin.readline def BOJ2166() : N = int(input()) x_points = [] y_points = [] for _ in range(N) : x, y = map(int, input().split()) x_points.append(x) y_points.append(y) result = 0 for i in range(N) : if i == N-1 : result += x_points[i] * y_points[0] else : result += x_points[i] * y_points[i+1] for i in range(N): if i == N-1 : result -= x_points[0] * y_points[i] e..

가장 긴 증가하는 부분 수열 4 [백준 14002] - python

import sys from bisect import bisect_left input = sys.stdin.readline def BOJ14002(): N = int(input()) A = list(map(int, input().split())) dist = [-1000000001] index = [0] * (N + 1) for i in range(len(A)): num = A[i] if dist[-1] < num: dist.append(num) index[i] = len(dist) - 1 else: index[i] = bisect_left(dist, num) dist[index[i]] = num max_length = len(dist) - 1 print(max_length) answer = [] for..