[백준 파이썬] 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 문제 가방과 물건의 정보가 주어지고 물건을 선택했을 때 가장 가치가 높은 경우의 수를 출력하는 문제이다 아이디어 DP로 풀면 되겠다고 생각했지만 아이디어가 떠오르지 않아 찾아보니 냅색 알고리즘이라는게 있었다. 냅색 알고리즘에 의하면 물건과 가치를 저장하는 2차원 배열을 생성한 뒤 배열을 탐색하며 가치를 저장해 배열의 마지막 인덱스..

• format_list_bulleted 알고리즘
• · 2023. 12. 4.
• textsms

[백준 파이썬] 17216 가장 큰 감소 부분 수열

https://www.acmicpc.net/problem/17216 17216번: 가장 큰 감소 부분 수열 수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열 www.acmicpc.net 문제 아이디어 모든 경우를 계산하며, dp값으로 누적하면 되겠다고 생각했다. 풀이 위의 dp값중 가장 큰 값을 출력하면 정답이 된다. 코드 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) dp = arr[:] for i..

• format_list_bulleted 알고리즘
• · 2023. 12. 1.
• textsms

[백준 파이썬] 9465 스티커

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 아이디어 가장 많은 스티커를 선택하기 위해서는 지그재그형식으로 스티커를 뽑을 때 가장 많이 뽑게된다. 하지만 모든 스티커를 반드시 지그재그로 뽑았을 시 최대값이 되는것이 아니므로 다음 스티커를 뽑을 때 2가지 경우의수가 생긴다. 1. 똑같이 지그재그로 뽑을경우. 2. 한 스티커를 건너뛰고 다른 행의 스티커를 뽑을경우 해당 경우의 수들을 dp로 계산하면 되겠다고 생각했다. 풀이 i..

• format_list_bulleted 알고리즘
• · 2023. 11. 29.
• textsms

[백준 파이썬] 13549 숨바꼭질 3

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 이동을 하여 한 지점에 도착할 때 가장 빠른 시간을 구하는 문제이다. 아이디어 앞으로 가는경우, 뒤로가는 경우, 순간이동하는 경우를 너비 우선탐색으로 하나씩 탐색하면 되겠다고 생각했다. 따라서 BFS를 정의하여 문제에 적용하였다. 풀이 def BFS(start): queue = deque() queue.append(start) visited[start] = 0 while queue: target = queue.pople..

• format_list_bulleted 알고리즘
• · 2023. 11. 17.
• textsms

[백준 파이썬] 1991 트리순회

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 트리를 전위, 중위, 후위 순회한 값을 구하는 문제이다. 아이디어 이진 트리는 각각 root와 자식이 존재하는 트리이다. 따라서 key-value를 이용할 수 있겠다고 생각했다. root를 key로 자식을 value로 입력받으면 root에 따른 자식을 쉽게 구할 수 있기 때문이다. 풀이 tree = {} for i in range(N): root, left, right = map(str, input().split()) tree[root] = ..

• format_list_bulleted 알고리즘
• · 2023. 11. 15.
• textsms

[백준 파이썬] 11660 구간 합 구하기5

11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 배열이 주어진 후 한 지점부터 특정 지점까지의 합을 구하는 문제이다. 아이디어 (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 이라는 조건이 있기 때문에 무턱대고 반복문을 이용해 합을 구하면 시간초과가 난다. 따라서 구간합을 이용해서 효율적으로 계산해야한다. x1,y1 부터 x2,y2까지의 구간합은 다음과 위와 같이 구할 수 있다. 따라서 모든 구간에서의 누적합을 구해놓은 후 필요한 영역의 구간합을 ..

• format_list_bulleted 알고리즘
• · 2023. 11. 13.
• textsms