[백준][Python] 17175번 피보나치는 지겨웡~ - 코팩
·
백준/다이내믹 프로그래밍
https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 풀이 피보나치의 함수가 얼마나 호출되는지에 대한 계산을 요구한다. 그래서 dp테이블을 만들어서 n이 0~2까지의 함수 호출 횟수를 넣어준 뒤 다이나믹 프로그래밍을 통해서 n이 원하는 답을 구해주었습니다. 코드 # 17175번 피보나치는 지겨웡~ n = int(input()) dp = [1,1,3] for i in range(3, n+1): dp.append((dp[i-1] + dp[i-2] + 1..
[백준][Python] 7579번 앱 - 코팩
·
백준/다이내믹 프로그래밍
https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 배낭 알고리즘을 이용해서 풀어줄 수 있는 문제이다. solved.ac 기준으로 class5를 달성하기 위해서 거쳐가야하는 문제 중 하나이다. 참고로 배낭 알고리즘은 Dp 알고리즘이기에 이 문제를 풀기 이전에 간단한 Dp문제를 풀고 오기를 바란다. 이 문제는 새로운 B앱을 활성화하기 위해 M메모리만큼 비활성화해야하는 앱들의 집합의 cost 최솟값을 찾는 문제이다. 따라서 기존의 배낭 알고리즘 문제에서..
[백준][Python] 12865번 평범한 배낭 - 코팩
·
백준/다이내믹 프로그래밍
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 배낭 알고리즘이라 불리는 다이내믹 프로그래밍 알고리즘의 일종. 1행과 1열의 원소값들은 0값으로 고정해준다. 행은 배낭의 무게를 뜻하고, 열은 물건의 번호를 뜻한다. i번째 물건을 가방 안에 넣을 수 없는 경우 -> 이전까지 최댓값을 저장해준다. i번째 물건을 가방 안에 넣을 수 있다면 -> dp에서 i번째 물건과 같이 넣을 ..
[백준][Python] 6593번 상범 빌딩 - 코팩
·
백준/DFS&BFS
https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 BFS 알고리즘을 사용해서 문제를 풀어주었습니다. 3차원 리스트이기에 주의해서 짜주시면 됩니다. 코드 # 6593번 상범 빌딩 import sys from collections import deque dxyzs = ((0,0,1), (0,0,-1), (1,0,0), (-1,0,0), (0,1,0), (0,-1,0)) while True: L, R, C = map(int, sys.stdin.read..
[백준][Python] 1253번 좋다 - 코팩
·
백준/투 포인터
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 두 수의 합을 이용하기에 투 포인터 알고리즘인 것을 알 수 있다. for문으로 리스트 안에 특정 숫자를 뽑아주고 뽑은 특정 숫자를 제외한 숫자들의 합으로 뽑은 특정 숫자를 표현할 수 있으면 좋다(GOOD) 개수 1 추가. 코드 # 1253번 좋다 n = int(input()) li = sorted(list(map(int, input().split()))) ans = 0 # 두 수의 합을 표현해줄 숫자를 순차적으로 뽑아준..
[백준][Python] 11653번 소인수분해 - 코팩
·
백준/구현
https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 소인수분해를 구현해주는 문제이다. 나누는 값을 1씩 추가해서 더 이상 나눌 수 없을 때까지 나눠준다. 코드 # 11653번 소인수분해 n = int(input()) ans = [] def calc(c_n): for i in range(2, c_n): if n % i == 0: c_n = c_n // i ans.append(i) break return c_n if n != 1: while True: t = calc(n) if n == t: ans.append(n) break n = t print("\n".join..
[백준][Python] 14921번 용액 합성하기 - 코팩
·
백준/투 포인터
https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 풀이 투 포인터 알고리즘을 이미 학습한 사람이라면 문제없이 풀 수 있을 것이다. 투포인터 알고리즘 블로그 글: https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열에서 특정 조건을 충족하는 요소를 찾거나 연속된 서브 배열..
[백준][Python] 3649번 로봇 프로젝트 - 코팩
·
백준/투 포인터
https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 풀이 주어진 레고들 중 두 개의 길이 합이 구멍 크기와 같을 수 있는지 확인하는 문제이기에 투포인터 알고리즘을 적용했다. 코드 # 3649번 로봇 프로젝트 import sys while 1: try: x = int(input()) x *= 10000000 # 단위가 센티미터이기에 나노미터로 통일. r = int(input()) lego = [int(sys.stdin.rea..
개발자 성현