본문 바로가기

문제 풀이/백준37

[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.
[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.
[G4] 백준 1253 - 좋다 (python3) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 해결방법 투 포인터를 이용해서 문제를 해결할 수 있다. 풀이👀 이번 문제에서 투 포인터를 활용하기 위해선, 반드시 입력되는 배열이 정렬되어야 한다. 왜냐하면 투 포인터의 head와 tail 인덱스로 어떤 값이 나올지 예측해야 하기 때문이다. 만약 target과 비교했을 때, 값이 작으면 head를 +1 해주고, 반대로 작으면 tail을 -1 해주는 식으로 말이다. 곰곰이 생각해보면 이 로직은 이분탐색의 로직과 같다. (이분탐.. 2023. 7. 14.
[G4] 백준 1753 - 최단경로 (Python3) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해결방법 다익스트라 알고리즘을 활용하여 풀었다. 풀이👀 나는 그래프를 python의 dictionary로 표현했다. 그래서 입력받은 간선의 정보들을 모두 graph에 담았다. * 하지만 이렇게 되면 쓸모없는 데이터까지 받아오게 된다. "서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다." 라는 문제 조건이 있기 때문이다. 모든 정보를 담.. 2023. 2. 20.
[G4] 백준 11404 - 플로이드 (Python3) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해결방법 플로이드-워셜 알고리즘을 이용해 풀이했다. 풀이👀 이번 입력은 [출발-도착-비용]이 들어오는데, 출발과 도착 정보가 동일한 입력도 포함된다. 그래서 이런 경우를 대비해주어야 한다. 이 문제는 모든 경로로 이동하는 최소비용 정보를 (출력하라고)요구하고 있다. 그러므로 출발과 도착 정보가 동일하게 주어질 땐 기존 입력값과 비교해서 더 작은 값을 반영해서 이 문제를 풀면 된다. 코드🐱‍👓 IN.. 2023. 1. 31.
[G5] 백준 1916 - 최소비용 구하기 (Python3) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해결방법 다익스트라 알고리즘을 이용한다. 풀이👀 입력에서 버스 이동에 대한 정보를 제공해주고 있다. 순서대로 [출발점, 도착점, (출발->도착)비용] 이다. 각 지점에서는 연결 된 다른 점들로 이동할 수 있다. 이 이동에서 비용이 발생한다. 그런데 이동을 하면서 출발점과 도착점이 같지만 중간에 우회하는 경로를 달리하여 그 비용(결과)를 저렴하게 할 수 있다. 하지.. 2023. 1. 30.

티스토리툴바