본문 바로가기

알고리즘149

[파이썬]baekjoon 2748: 피보나치 수 2 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문제 점화식은 dp[i] = dp[i-1] + dp[i-2] 이고, 이를 활용하여 주어진 n번째의 피보나치 수를 찾을 수 있다! import sys input = sys.stdin.readline n = int(input()) arr = [0,1,1] + [0]*(n-2) if n >=3: for i in range(3,n+1): arr[i] = ar.. 2023. 1. 9.
[파이썬]baekjoon 1309: 동물원 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp문제 이는 3가지 경우로 나눌 수 있는데, 사자를 두지 않을경우와, 왼쪽에 둘 경우, 오른쪽에 둘 경우 이다. 이전 경우에 나온 경우의수를 이용하여 이후에 나올 경우의 수를 계산하는 방법! import sys input = sys.stdin.readline n = int(input()) # 3가지 경우가 있음. 아무것도 두지않거나, 왼쪽에 두거나, 오른쪽에 두거나 arr = [[0]*3 for _ in range(n + 1)] arr[1][0], arr[1][1], arr[1][2] = 1, 1, 1 # 0은 아무것도 두지 않.. 2023. 1. 8.
[파이썬]baekjoon 1303: 전쟁 - 전투 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net bfs문제 W나 B로 시작하는지 확인한 뒤, W집군과 B집군의 값을 찾은 후 출력하면 된다. n,m = list(map(int,input().split())) arr = [list(input()) for _ in range(m)] visit = [[0]*n for _ in range(m)] w = 0 b = 0 def bfs(start): global visit, w, b.. 2023. 1. 7.
[파이썬]baekjoon 1758: 알바생 강호 https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 강호가 최대로 팁을 받을 수 있는 경우를 찾아 최대 팁 가격을 출력한다. 그리디 개념으로 접근하면 쉽게 풀 수 있음! n = int(input()) kang = 0 arr = [int(input()) for _ in range(n)] arr.sort(reverse=True) for i in range(n): order = i+1 tip = arr[i] - (order - 1) i.. 2023. 1. 6.
[파이썬]baekjoon 9342: 염색체 https://www.acmicpc.net/problem/9342 9342번: 염색체 상근이는 생명과학 연구소에서 염색체가 특정한 패턴인지를 확인하는 일을 하고 있다. 염색체는 알파벳 대문자 (A, B, C, ..., Z)로만 이루어진 문자열이다. 상근이는 각 염색체가 다음과 같은 규칙 www.acmicpc.net 단순 구현문제 구현중 0개이거나 1개일시 부분을 잘 확인해서 구현하여야함! t = int(input()) for tc in range(t): arr = list(input()) start = 0 #1케이스 if arr[0] in ["A","B","C","D","E","F"]: if arr[0] !="A": start = 1 else: print("Good") continue #2케이스 if a.. 2022. 12. 29.
[파이썬]baekjoon 1863: 스카이라인 쉬운거 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net stack 개념을 섞어서 푸는 문제. n = int(input()) visited = [0] cnt = 0 for tc in range(n): x, y = list(map(int,input().split())) if y > visited[-1]: cnt += 1 visited.append(y) else: while y < visited[-1]:.. 2022. 12. 28.

티스토리툴바