본문 바로가기

문제 풀이41

[S1] 백준 1932 - 정수 삼각형 (Python3) https://www.acmicpc.net/problem/1932해결방법정수 삼각형의 맨 아래층부터 위층으로 올라간다. 각 행의 원소를 순회하면서, 현재 위치의 정수와 현재 위치의 왼쪽 아래 정수와 오른쪽 아래 정수 중 더 큰 값과의 합을 DP table에 저장한다. ( max(왼쪽아래 정수, 오른쪽아래 정수) + 현재위치 정수 )풀이👀주어진 정수 삼각형에서 아래층부터 위층으로 올라가며 각 행의 원소를 순회한다.각 행의 원소를 순회하면서 현재 위치의 정수에 다음 행(아래층)의 왼쪽 대각선 정수와 오른쪽 대각선 정수 중 더 큰 값을 더해가며 최대 합을 계산한다.모든 행을 순회하면서 이를 맨 위층까지 반복한다.최종적으로 맨 위층의 최대 합을 반환한다.코드🐱‍👓n = int(input())triangle.. 2024. 4. 27.
[G3] 백준 11779 - 최소비용 구하기 2 (Python3) https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 문제 n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다. 입력 첫.. 2023. 12. 16.
[G4] 백준 1504 - 특정한 최단 경로 (Python3) https://www.acmicpc.net/problem/1504 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘.. 2023. 12. 16.
[G5] 백준 15486 - 퇴사 2 (Python3) https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 백준 퇴사(14501)와 같은 알고리즘으로 동작하는 문제이며, 이 해결방법으로도 14501번 문제를 통과할 수 있습니다. 해결방법 다이나믹 프로그래밍으로 해결했다. 이 문제는 마지막 날 부터 상담 건을 진행하면서 '이 날 근무하면 벌 수 있는 최대 금여'를 구하면 해결 할 수 있다. 풀이👀 문제에서 제공하는 예제로 풀이를 진행해보겠습니다. 1일(index:.. 2023. 11. 19.
[S3] 백준 2579 - 계단 오르기 (Python3) 2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 해결방법 다이나믹 프로그래밍(이하 dp) 문제이므로 점화식을 세워서 해결했다. 풀이👀 $a_n$번째 계단에 오르려면 $a_{n-3}$ > $a_{n-1}$ 순으로 오르거나, $a_{n-2}$에서 바로 오르는 경우가 있다. 두 경우 중에서 더 큰 값을 만드는 경우로 $a_n$을 오르는게 이 문제 풀이의 핵심이다. dp 문제는 개인적으로 dp table을 활용해 푸는 경우가 쉽게 풀리기 때문에 dp 라는 이름의 list를 만들었.. 2023. 10. 30.
[이것이 코딩 테스트다] 개미 전사 - 다이나믹 프로그래밍 '이것이 코딩 테스트다' 책에 수록 되어 있는 실전 문제이다. 문제의 자세한 내용은 책을 참고하도록 하자. 책에서 나오는 점화식은 문제 설명을 해주며 결국 아래와 같은 점화식을 만든다. $$a_i = max(a_{i-1}, a_{i-2}+k_i)$$ 하지만 나는 다른 방법으로 점화식을 찾았다. 하지만 이 점화식이 옳은 점화식인지 확인이 어렵다는 것이다. $$d_i = k_i + max(d_{i-2}, d_{i-3}), (i>3)$$ *단, $d_1 = k_1$, $d_2 = k_2$, $d_3 = k_3 + d_1$ 이다. N = int(input()) K = list(map(int, input().split())) dp = [0] * N dp[:2] = K[:2] ans = 0 for i in rang.. 2023. 9. 30.
[G5] 백준 9251 - LCS (python3) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해결방법 2차원 배열의 캐시값을 만들어 해결했다. - 백준 사이트의 [예제 입력 1] A C A Y K P [0, 0, 0, 0, 0, 0, 0] C [0, 0, 1, 1, 1, 1, 1] A [0, 1, 1, 2, 2, 2, 2] P [0, 1, 1, 2, 2, 2, 3] C [0, 1, 2, 2, 2, 2, 3] A [0, 1, 2, 3, 3, 3,.. 2023. 8. 20.
[G5] 백준 5582 - 공통 부분 문자열 (python3) https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 해결방법 LCS(Longest Common Subsequence, 최장 공통 부분 수열)에서 아이디어를 빌려왔다. 풀이👀 A B R A C A D A B R A E [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] C [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] A [1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1] D [0, 0, 0, 0, 0, 0.. 2023. 8. 19.

티스토리툴바