조용하지않는개발Blog

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제 자체는 어렵지 않은 문제였다. 하지만 어떻게 풀면 시간초과도 날수있으니 조금 생각하며 풀어봐야하는 문제였다. 먼저 왼쪽끝에서 오른쪽 끝으로 움직이면서 큰 값만을 이동 시키면 되는 문제이다. 이를 담을 DP를 만들어 주면 된다. 나는 이를 추가한다는 느낌이 들어 stack이라고 정의하고 넣으면서 진행했다. 결과적으로 오른쪽 아래에 도착하게..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제를 통해서 겹치는 구간을 없애기만 하면 되는 문제이다. 다시 말해서 최장 증가 부분 수열(LIS)로 문제를 풀면 된다. 다음에 관련해서 알고리즘을 작성해놓아야 좋을듯하다. 두가지 방식으로 풀었는데 dp와 이분탐색으로 문제를 해결하였다. import sys input = sys.stdin.readline n = int(input()) n_list = [] for..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 문제 자체가 짧지만 단순하게 풀면 어렵고 다이나믹 프로그래밍으로 풀면 그나마 쉽게 풀 수 있는 문제이다. 처음에 풀 때, 반복문, 재귀를 이용해야하나 고민했는데 그러면 너무 많은 시간이 걸릴 것 같아서 포기했다. 그래서 dp로 10001이 담긴 리스트를 생성하고 가치가 낮은 동전을 넣고 그다음으로 가치 높은 동전을 넣어가면서 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 처음에 문제를 보고 단순하게 큰 값부터 계산하고 주변을 0으로 두면서 풀면 될까? 라는 생각을 가졌지만 여러 계산을 해보니 그렇게 풀면 발생하는 오류들이 많이 있어서 이것은 dp로 풀어야하는 문제라는 것을 파악하였다. 두개의 스티커를 1부터 차례대로 계산을 하면서 증가시키면 되는 문제였다. 1 2 3 4 5 1 50 30+10=40 max(30,100..

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 1개 샀을때 부터 n개를 살때까지 최소가 되는 값을 찾기위해서는 dp 형식으로 최소값을 찾는 것이 효율적이다. 예시 4번을 예로 들어서 풀어보면 10 5 10 11 12 13 30 35 40 45 47 맨 처음 1개를 살때 최소로 사는 방법은 5 하나밖에 없다. dp에는 1번째에는 5가 쌓일것이고 다음 2개를 살때 최소를 구해보면 10원으로 2개를 사거나 최소인 1..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 문제를 보았을때 알수있는 힌트 오른쪽, 아래로만 움직이는 문제이며 웅덩이가 있는 곳은 지나가지 않는 문제이다. dfs,bfs로 풀면 아마 시간 초과가 날 확률이 높을것이다. 이것은 dp로 풀어야한다. 시작하는 위치에서 오른쪽 왼쪽으로 이동시킬수있는 갯수를 추가하는 형식으로 진행하면 쉽게 풀 수 있는 문제이다. def solution(m, n, p..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=414 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 dp 문제라고 생각하고 접근하였다. p의 로봇의 위치는 dp에 True로 변경하고 k만큼 왼쪽에서 오른쪽으로 dp가 False인 경우에 dp를 True로 바꾸면서 count를 1씩 증가시키면 끝이 나는 문제이다. input= sys.stdin.readline n,k= map(int,input().split()) dp = [False]*n n_list = list(input().strip()) # print(n_list) for i in range(len(n_lis..

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 문제를 보았을때 알수있는 힌트 bfs나 dfs를 통해 백트래킹해서 문제를 푼다면 시간 초과가 날수 있는 문제이다. triangle 과 같은 리스트의 dp를 만들고 이전의 값의 더하면서 최대값이 되는 값을 유지하며 진행하면 쉽게 풀리는 문제이다. 예를 들어 1행의 7을 2행의 3과 8에 넣어 2행 dp에 [10,15]를 가지게 한다. 다음으로 2행의에서 3행으로 갈수있는 방법으로 2행의 1번째는 3행의 1,2번째를 갈수있고[18,11..

https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 문제를 보았을때 알수있는 힌트 이러한 정사각형 문제는 많이 풀어봐야지 감이 잡힐것같다. 40분 가량 봐도 답이 나오지 않아서 다른 사람들의 푸는 방식을 통해 힌트를 얻고 풀었다. 2가지 조건을 두고 문제를 푼다. 1. i+1,j+1이 0이면 넘어가고 1인 경우 2번의 조건을 수행한다. 2. i,j와 i+1,j와 i,j+1의 값 중 최소 값에 1을 더하여 i+1,j+1에 넣는다. 이것을 반복하여 나온 board의 최대값을 제곱하면 끝나는 문제이다. ..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 이해하면 좀 쉽게 풀리는 문제인데. dp 문제로 길게 증가하는 dp1와 감소하는 dp2두개를 만들어서 그 둘을 합치고 겹치는 구간 1을 빼면 쉽게 풀리는 문제이다. dp2를 구하기 위해서 list를 역순으로 뒤집어서 쉽게 계산했다. 나온 결과를 다시 reverse 시키고 dp1과 더하면 끝이 난다. import sys input= sys.stdin.readline n= in..