본문 바로가기

dp23

[Python] 소프티어 : 징검다리 https://softeer.ai/practice/info.do?idx=1&eid=390 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 기본적인 DP 문제이다. 이번 DP 리스트에서는 i번째 징검다리까지의 최댓값을 넣어주면 된다. 따라서, 이번 징검다리를 건널 때 현재 값과 이전 값에서 1 추가한 값과 비교해 주면 된다. ✔️ 느낀 점 기본적인 DP 문제이다! 문제 설명이 딱히 친절하지 않아서 어떻게 할까 고민하다가 쓱 풀었는데 맞았다. 💻 코드 import sys ; input = sys.stdin.readline n = int(input()) stones = list(map(int, input().split())) DP = [1] * n for i .. 2023. 3. 5.
[Python] 백준 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 💡 문제 풀이 동적 프로그래밍과 위상정렬을 합친 문제이다. 위상정렬을 통해서 해당 노드까지 가는 길을 파악하고 DP로 최적화한다. 이해를 위해서 문제에서 제공된 첫 예제로 이해해 보자. 1부터 4까지 가기 위해서는 1 → 2, 3 → 4로 가야 한다. DP[i]에서 저장되는 값은 정점 i까지 도달했을 때의 최댓값이다. 4로 가는 길은 2가지이지만, 각 경로에 대한 비용을 따져서 최댓값으로만 .. 2023. 3. 3.
[Python] 백준 1520번 : 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 💡 문제 풀이 그래프 탐색(DFS)에 DP를 곁들인 문제이다. 그냥 DFS로 구현하면 시간초과가 발생한다. 그래서 이미 지나온 길에 대해서는 이전에 방문한 결과를 바로 전달해 주는 방식으로 중간에 순회하는 시간을 줄일 수 있다. ✔️ 느낀 점 그냥 DFS 문제인 줄 알았지만 DP가 곁들인거 보고 큰코다쳤다. 💻 코드 import sys input = sys.stdin.readline dx = [.. 2023. 2. 26.
[Python] 프로그래머스 : 기지국 설치 https://school.programmers.co.kr/learn/courses/30/lessons/12979 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 DP 관련 문제이다. 기지국의 최대 전파 범위는 도달 거리의 × 2 + 1 만큼이다. 기지국을 기준으로 좌우로 범위가 나뉘는데 시작 지점부터 기지국 왼쪽 도달 범위까지 거리에서 최대 전파 범위를 나눠서 올림 처리해주면 필요한 최소 개수를 셀 수 있다. 이 방법은 단순히 최소 개수만 구해주면되기 때문에 가능하다. ✔️ 느낀 점 이런 류의 문제가 너무나도 약해서 다른 문제들도 많이 풀어.. 2022. 10. 9.
[Python] 백준 1577번 : 도로의 개수 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 💡 문제 풀이 DP 문제이다. 이 문제는 메모리의 크기는 작긴 하지만 n, m의 100까지므로 배열을 사용해도 괜찮다. 최단거리로만 이동하기 때문에 항상 아래 혹은 오른쪽으로만 이동한다는 점이 포인트이다. 주어진 (a,b), (c,d)에 대해서 어떤 점이 못 가는 점인지 판단하기 까다롭다는 생각에 방향에 따라 이동 가능 여부를 따지려고 4차원 배열까지 가고 마지막 배열에 boole.. 2022. 7. 26.
[Python] 백준 2096번 : 내려가기 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 💡 문제 풀이 DP 문제이다. 메모리의 크기가 매우 작으므로 입력 값을 받는 동시에 최댓값과 최솟값을 따져준다. ✔️ 느낀 점 단순히 2차원 배열로 구현할 수 있다. 크게 어렵진 않지만 메모리 크기 때문에 조금 생각을 바꿀 필요가 있는 문제이다. 조금 바꾸는게 너무 어려웠다.. 💻 코드 import sys input = sys.stdin.readline n = int(input()) DP_max = [0] * .. 2022. 7. 22.

티스토리툴바