본문 바로가기

알고리즘

 (158)
BOJ) MooTube https://www.acmicpc.net/problem/15591  정말 기본적인 BFS문제였다.기초에 충실하게 bfs를 작성하고 제출을 눌렀으나 시간초과가 발생했다.import mathfrom collections import dequeimport sysinput = sys.stdin.readlineINF = math.infn, q = map(int, input().split())arr = [[] for _ in range(n+1)]for _ in range(n-1): a, b, c = map(int, input().split()) arr[a].append([b, c]) arr[b].append([a, c])for _ in range(q): k, start = map(int, i..
백준) 합분해 - python https://www.acmicpc.net/problem/2225  이전의 동전 1과 비슷한 문제이다. 우선 2개의 수로 6을 만드는 경우의 수는 어떻게 될까?이를 생각하기에 앞서 정수 1개로 6을 만드는 경우를 생각해보자  당연하게도 0원부터 6원까지의 경우의 수는 모두 1개가 된다. 그럼 동전 2개로는 어떨까3개 또한 다음과 같다.  규칙성이 보이기 시작하는 것이 정상이다. 이런 규칙성은 과연 합당할까? 좀 더 자세히 보자단순 정수로만 표기하면 다음과 같이 규칙성을 찾을 수 없겠지만, 이를 이진법으로 바꾸면 간단하다.  단순히 이전 결과 값에 0 또는 1을 붙임으로써 해당 k 개로 정수 n을 만들 수 있는 경우의 수가 만들어진다 이를 코드로 변환하면 다음과 같다.from itertools import..
BOJ) 동전 1. Python https://www.acmicpc.net/problem/2293    입력 예제로 들어온 값으로 예를 들어보자3 10125 1,2,5의 동전으로 10을 만들 수 있는 경우의 수는 몇 개인가?우리가 생각해보아야할 것은 1의 동전으로 몇 개를 만들 수 있는가.1과 2의 동전으로 몇 개를 만들 수 있는가1과 2와 5의 동전으로 몇 개를 만들 수 있는가여느 dp문제와 헷갈린 점이2원짜리 동전은 1원짜리 동전으로 나눌 수 있으니 이를 이용해 dp를 작성하면 된다 생각했다.하지만 이는 문제를 잘못 쪼갠 것이다.  1원으로 k원을 만들 수 있는 경우의 수,1과 2원으로 k원을 만들 수 있는 경우의 수, 1과 2와 5원으로 k원을 만들 수 있는 경우의 수이런 작은 문제들로 쪼개야한다. 우선 1원으로 0원부터 k원(1..
BOJ)포도주 시식 - python https://www.acmicpc.net/problem/2156 알고리즘 공부를 3달만에 해서 그런지 조금만 생각하면 풀 수있는 dp문제도 애를먹었다. dp라는 배열을 생성하고 이 배열엔 x번째의 인덱스에 0부터 x번째의 마신다/마시지 않는다의 선택지를 골라가며 선택한 가장 큰 값이 저장되어있다. 그럼 x번째에는 어떻게 가장 큰 값이 들어갈까. dp[x]에 가장 큰 값이 들어가기 위해선 세개의 선택지가 존재한다. 현재 포도주(x번째)의 마시고, 직전(x-1)을 마신다.현재 포도주를 마시고, 직전의 것은 건너 뛴다.현재 포도주를 마시지 않는다. 현재 arr[x]가 8이라 가정했을 때,1번 선택지의 경우 다음과 같다. 하지만 여기서 생각해야할 것이, 현재 포도주와 직전의 포도주를 마신다는 것은 전전의 포도..
BOJ) 연속 합 - 파이썬 https://www.acmicpc.net/problem/1912  해당 문제의 알고리즘 분류는 DP가 된다. 우선 가장 먼저 생각해 보아야할 것이 브루트 포스 알고리즘이다. n의 수 만큼 반복하며 각각의 모든 연속된 합 중 최대값을 구하는 방법이다. 하지만 해당 방법으로는 해당 문제의 최대 입력 값을 기준으로 100,000^2 시간 복잡도를 가지며 당연하게 시간초과가 나오고 만다. 그럼 가장 먼저 생각나는 것이 DP이다.DP중 캐싱을 통한 방법으로 풀어보았다.n = int(input())arr = list(map(int, input().split()))for i in range(1, n): arr[i] = max(arr[i], arr[i] + arr[i-1])print(arr) 우선 정답 코드이다..
BOJ) 안녕 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 이 문제 또한 어제 풀었던 냅색 알고리즘 문제이다. import sys input = sys.stdin.readline n = int(input()) arr = [0]+list(map(int, input().split())) happy = [0] + list(map(int, input().split())) dp = [[0 for _ in range(101)] for _ in range(n+1)]..
BOJ) 평범한 배낭 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 오랜만에 알고리즘 문제를 풀다 처음 마주친 "냅색 알고리즘"을 이용해 풀어야하는 문제이다. 그리디 알고리즘을 생각했으나 조금만 생각해보면 그리디는 최적의 해를 구할 수 없게된다. 우선 냅색 알고리즘은 물건을 쪼개어 부분적으로 담을 수 있는 경우를 고려하거나 또는 각 물건을 선택하거나 선택하지 않았을 때를 고려하는 경우 사용할 수 있..
파이선) 어두운 건 무서워 - BOJ (2D Array prefix sum, and 블로그의 방향성) https://www.acmicpc.net/problem/16507 r, c, q = map(int, input().split()) arr = [] for _ in range(r): arr.append(list(map(int, input().split()))) dp = [[0 for _ in range(c+1)] for _ in range(r+1)] # print(dp) for i in range(1, r+1): for j in range(1, c+1): dp[i][j] = -dp[i-1][j-1] + dp[i][j-1] + dp[i-1][j] + arr[i-1][j-1] for _ in range(q): r1, c1, r2, c2 = map(int, input().split()) num = dp[r2]..

티스토리툴바