본문 바로가기

Algorithm/baekjoon65

[파이썬]baekjoon 20551: Sort 마스터 배지훈의 후계자 https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 정렬 알고리즘을 이용하여, 문제를 풀면 된다. 어떤 정렬인지는 상관없으나, 본인은 이진탐색을 이용하여 풀었음. a는 같은 숫자가 여러개가 있을 수 있으며, 같은 숫자가 많다면 가장 작은 index를 출력해야 함을 주의! import sys input = sys.stdin.readline n, m =list(map(int,input().split())) a = [int(inp.. 2023. 1. 14.
[파이썬]baekjoon 1068: 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제에서 바라는 건 unionfind 같은 종속을 확인하며 찾아가는 알고리즘을 원하는거 같은데.. 문제에서 주어진 tree가 복잡하지 않기때문에 단순히 dfs로 풀이가 가능하다! def dfs(d): arr[d] = -2 for i in range(n): if d == arr[i]: dfs(i) n = int(input()) arr = list(map(int,input().split())) .. 2023. 1. 13.
[파이썬]baekjoon 2579: 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net dp문제 점화식을 구하는게 어려움 n = int(input()) arr = [int(input()) for _ in range(n)] # dp란 리스트는 해당위치 최댓값을 뜻함 dp = [0]*n if len(arr) 2023. 1. 12.
[파이썬]baekjoon 9095: 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net dp문제 이문제의 키는 점화식을 구하는 것인데, 손으로 그리면서 문제를 따라가다 보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 이란 반복성을 찾을 수 있다! t = int(input()) for tc in range(t): n = int(input()) if n >= 4: arr = [0]*(n+1) arr[1] = 1 arr[2] = 2 arr[3] = 4 else: arr = [0,1,2,4] if n>=4: for i in range(4, n+1): arr[i] = .. 2023. 1. 11.
[파이썬]baekjoon 1463: 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net dp문제 import sys input = sys.stdin.readline N = int(input()) dp = [[0, 0] for _ in range(4)] for i in range(2, N + 1): min_lst = [] if not i % 3: dp[0].append(i // 3) min_lst.append(dp[3][i // 3]) else: dp[0].append(-1) if not i % 2: dp[1].append(i // 2) min_lst.append(dp[3][i // 2]) else.. 2023. 1. 10.
[파이썬]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.

티스토리툴바