BAEKJOON #9461) 파도반 수열 | DP | Python 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 💡 점화식 $f(n) = f(n - 3) + f(n - 2)$ 💡 코드(python) import sys input = sys.stdin.readline def padovan(n): dp = [1] * (n + 1) dp[0] = 0 for idx in range(3, n + 1): dp[idx] = dp[idx-3] + dp[idx-2] return dp[n] if __name__ == "__main__": cnt = int(input()) for _ in rang.. BAEKJOON #11726) 2xn 타일링 | DP | Python 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 0️⃣ 초기화 이 문제를 풀기 위해서는 2x1 타일링 방법 개수와 2x2 타일링 방법 개수를 초기화하고 시작합니다. 2x1을 타일링하는 방법은 아래의 방법으로 1개 입니다. 2x2를 타일링하는 방법은 아래 방법으로 2개 입니다. 1️⃣ 2x3 타일 생각해보기 초기화 한 후, 2x3 타일링은 2x1타일링에 1x2타일 2개를 붙이고, 2x2타일링에 2x1타일 1개를 붙이면 됩니다. 2️⃣ 2x4 타일 생각해보기 2x4 타일 또한 앞의 방법처럼 2x2 타일에 1x2 타일 2개를 붙이고, 2.. BAEKJOON #1916) 최소비용 구하기 | Python 다익스트라 최단 경로 알고리즘을 구현하는 기본적인 문제입니다. 아래 글에서 자세한 설명을 보실 수 있습니다:) 🚗 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 어떤 한 지점에서 다른 한 지점까지의 최단 경로를 찾아야 하는 문제의 경우, 각 지점은 그래프의 노드로, 지점 간 거리 eunbin00.tistory.com # boj_1916.py # https://www.acmicpc.net/problem/1916 import sys import heapq INF = int(1e9) n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) distance =[INF] * (n + 1) graph = [[].. BAEKJOON #1655) 가운데를 말해요(Python) 숫자를 입력받을 때마다 중앙값(숫자의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수)을 찾아서 출력하는 문제이다. 처음에는 숫자를 입력받을 때마다 배열에 넣고 정렬하여 홀수면 n/2번째 인덱스를, 짝수면 (n-1)/2번째 인덱스를 출력하면 된다고 생각하여 정렬 알고리즘을 구현하여 제출했다. 뚜둥-! 퀵소트로 정렬하면 시간 초과가 나고, 병합정렬(merge sort)을 이용하면 메모리 초과가 난다😇 정렬 알고리즘을 이용하여 풀 수는 없다. 조금 찾아보니 힙을 사용하여 중앙값을 찾는 방법을 이용하면 된다고 한다. Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap .. BAEKJOON #11279) 최대 힙 (Python) 1927번과 마찬가지로 힙을 구현만 하면 해결되는 문제이지만, 파이썬에는 이미 구현되어있는 heapq 라이브러리가 있기 때문에, 함수(heapq.heappush(heap, value), heapq.heappop(value))를 사용만 해준다. import heapq from sys import stdin n = int(stdin.readline()) heap = list() for _ in range(n): input_num = int(stdin.readline()) if input_num == 0: if heap: print(heapq.heappop(heap)[1]) else: print(0) else: heapq.heappush(heap, [-input_num, input_num]) 다만, heapq.. BAEKJOON #1927) 최소 힙 (Python) 문제 이름처럼 힙을 구현만 하는 되는 문제라서, 힙을 구현해야겠다고 생각했는데, 파이썬에는 이미 힙을 만들 수 있는 라이브러리가 있었다. 역시 파이썬..,.👍 heapq라는 라이브러리를 import하여 문제가 요구하는대로 사용해주면 끝이다. 📌 힙(heap)이란? Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Com eunbin00.tistory.com 📌 정답 코드(Python) import heapq from sys import stdin n = int(stdin.readline()) .. BAEKJOON #11718) 그대로 출력하기| C, Python 백준 11718번: 그대로 출력하기 입력받은 대로 그대로 출력하면 되는 문제이다. 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net C #include intmain(void) { char a; while (scanf("%c", &a) != -1) printf("%c", a); return 0; } char형 변수를 선언하고 character 하나하나 입력받는다. scanf 함수에서 에러가 나지 않는 이상 계속 받은 char를 출력한다. Python while True: try: print(in.. BAEKJOON #9663) N-QUEEN (C) 알고리즘 분류: 브루트포스 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 9663) N-Queen 알고리즘 분류: 브루트포스 #include #include int is_valid(int idx, int val, int *puzzle) { int i = 0; while (i < idx) { if (puzzle[i] == val) { return (0); } if (val - puzzle[i] == idx - i || val - puzzle[i] == i - idx) { return (0); } i++; } return.. BAEKJOON #1463) 1로 만들기 | 다이나믹 프로그래밍 | python 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 📌 다이나믹 프로그래밍 [Algorithm] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자 💡 다이나믹 프로그래밍 (Dynamic Programming, DP) 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 그런데 어떤 문제는 메모리 공간을 약간만 더 사용 eunbin00.tistory.com 1이 될 때까지 주어진 연산을 최소로 사용하는 '1로 만들기' 문제는 다이나믹 프로그래밍 알고리즘을 활용하는 대표적인 유형이다. 이 문제가 다이나믹 프로그래밍 알고리즘을 사용하여 풀 수.. BAEKJOON #12865) 평범한 배낭🎒 | knapsack | dynamic programming 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🎒 백준 12865번 평범한 배낭 문제는 다이나믹 프로그래밍의 대표적인 문제 유형인 knapsack(배낭) 문제이다. [Algorithm] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자 💡 다이나믹 프로그래밍 (Dynamic Programming, DP) 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.. BAEKJOON #1026) 보물 알고리즘 분류: 그리디 알고리즘 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 💡 풀이 n = int(input()) lst_a = list(map(int, input().split())) lst_b = list(map(int, input().split())) lst_a.sort() lst_b.sort(reverse=True) result = 0 for a, b in zip(lst_a, lst_b): result += a*b print(result) 가장 작은 S를 만드는 방법은 큰 B의 원소가 크면.. BAEKJOON #2231) 분해합 (python) 알고리즘 분류: 브루트 포스 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 💡 풀이 n = int(input()) result = 0 for i in range(1, n + 1): a = list(map(int, str(i))) s = i + sum(a) if (s == n): result = i break print(result) 이전 1 2 3 4 다음
