[백준/브론즈1] 24416번 알고리즘 수업 - 피보나치 수 1 | DP | 파이썬 Python

문제https://www.acmicpc.net/problem/24416오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.피보나치 수 재귀호출 의사 코드는 다음과 같다.fib(n) { if (n = 1 or n = 2) then return 1; # 코드1  else return (fib(n - 1) + fib(n - 2));}피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다..

• format_list_bulleted Baekjoon
• · 2025. 4. 8.
• textsms

[백준/실버2] 1260번 DFS와 BFS | 파이썬 Python

문제https://www.acmicpc.net/problem/1260그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과..

• format_list_bulleted Baekjoon
• · 2025. 4. 7.
• textsms

[백준/실버3] 11659번 구간 합 구하기 4 | 누적 합 | 파이썬 Pytho

문제https://www.acmicpc.net/problem/11659수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 예제 나의 풀이1import sysinput = sys.stdin.readlineN, M = map(int, input().split())nums = list(map(int, input().split()))li = [0]sum = 0for num in..

• format_list_bulleted Baekjoon
• · 2025. 4. 3.
• textsms

[백준/골드5] 4811번 알약 | DP | 파이썬 Python

문제https://www.acmicpc.net/problem/481170세 박종수 할아버지는 매일매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 ..

• format_list_bulleted Baekjoon
• · 2025. 4. 2.
• textsms

[백준/실버3] 24511번 queuestack | 파이썬 Python

문제https://www.acmicpc.net/problem/24511   입력 출력 예제 나의 풀이1 (실패)from collections import dequeN = int(input())A = list(map(int, input().split()))B = deque(map(int, input().split()))M = int(input())C = list(map(int, input().split()))for num in C: x = num for i in range(N): if A[i] == 0: # queue temp = B[i] B[i] = x x = temp print(x, end=" ..

• format_list_bulleted Baekjoon
• · 2025. 3. 26.
• textsms

[백준/실버5] 13909번 창문 닫기 | 파이썬 Python

문제서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다. 입력첫 번째 줄에는 창문의 개수와 사..

• format_list_bulleted Baekjoon
• · 2025. 3. 25.
• textsms

[백준] 11725번 트리의 부모 찾기 | 파이썬 Python

문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 DFS, BFS란?  DFS (Depth-First Search) BFS (Breadth-First Search) 탐색 방식깊이 우선 탐색너비 우선 탐색경로 탐색깊은 곳까지 탐색 후 백트래킹 (뒤로가기)가까운 노드부터 차례로 탐색구현 방식스택(Stack) or 재귀(Recursion)큐(Queue)메모리 사용낮음 (경로 저장 필요 없음)높음..

• format_list_bulleted Baekjoon
• · 2025. 3. 18.
• textsms

[백준] 1644번 소수의 연속합 | 파이썬 Python

문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지)하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 자연수 N이 주어진다. (1 ≤ N..

• format_list_bulleted Baekjoon
• · 2025. 3. 15.
• textsms

[백준] 1806번 부분합 | 파이썬 Python

문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N (10 ≤ N  출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 예제 나의 풀이1N, S = map(int, input().split())nums = sorted(list(map(int, input().split())))start, end = 0, 1mn = N + 1while start S: if length 부분합이 타겟보다 큰지, 작은지, 같은지에 따라 두 포인터를 이동하면서 최소 길이의 수열을 찾는 방..

• format_list_bulleted Baekjoon
• · 2025. 3. 14.
• textsms

[백준] 2470번 두 용액 | 파이썬 Python

문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특..

• format_list_bulleted Baekjoon
• · 2025. 3. 14.
• textsms