dp

누적합을 적응하기 위해도전한 문제! 아무 생각 없이 풀었을 때는 50점 나왔는데,공책에 적으면서 푸니까 맞았다. 집중하는 것이 중요한 것 같다! 문제 https://www.acmicpc.net/problem/16139  풀이 알고리즘 설계 [접근 방법] : 누적합 + dp알파벳이 주어지고, 처음과 시작 구간을 매번 입력받을 때마다 조회한다면 20000*20000이 되어 시간초과가 발생한다.그래서 질문이 주어졌을 때 반복문을 실행하지 않는 방법을 고민했다.시작구간과 끝구간에서 알파벳이 누적으로 몇 번 사용되었는지 알면 끝부분 누적 - 시작부분 누적으로 바로 계산이 가능하다.   풀이 과정1.문자열을 입력받는다. 2.알파벳 26개마다 누적합을 계산해야 하므로 dp[26][문자열의 길이+1]의 dp배열을 생성..

끝없는 dp 생활! 이번 문제는 누적합+dp문제다.맨날 똑같은 문제만 풀고새로운 문제는 나몰라라해서다양한 문제를 풀어보고자 골랐다. 문제 https://www.acmicpc.net/problem/19951    풀이 알고리즘 설계 [접근 방법] : 누적합+DP모든 지시를 처음부터 끝까지 계산하면 시간 초과가 발생한다. 그러므로, 처음과 끝만 저장한 후 누적합으로 풀면 O(n)의 속도로 풀 수 있다.처음부터 끝까지 계산해야 하는 k값을 입력받는다. 그리고 처음 시작하는 인덱스 a에 k값을 저장한 후 끝나는 지점, 즉 b+1지점에 -k값을 저장한다.왜냐하면, a부터 끝까지 +k값을 계산한다고 가정하면, b+1지점부터 끝까지는 +k값을 계산하면 안된다. 그러므로 b+1지점부터는 -k값을 해주어야 하기 때문이다..

DP는 코딩테스트의 정석 같은 문제죠? 바로 풀어보겠습니다! 이 문제 저번에도 풀었던 문제로 그 때는 정답을 보았던 것으로 기억하는데, 이 번에는 스스로 풀었습니다 하핫 문제 https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 알고리즘 설계 [접근 방법] : DP 최대 합을 찾기 위해 어디서 시작하든 상관 없었기에 슬라이딩 윈도우를 생각했지만, 배열의 최대 길이가 500,000이기 때문에 시간 초과가 발생할 것이라 생각했다. 그래서 DP로 ..

DP는 연습할 수록 쉬워지고, 안할 수록 말도 안되게 어려워지는 문제인 것 같다. 코딩테스트에 꾸준히 나오고 있으니까 열심히 해야겠다. 문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 설계 알고리즘 설계 [접근 방법] : DP DP 문제 중에서도 점화식의 규칙을 찾아야 하는 문제다. 이게 무슨 문제야..하고 1부터 7자리까지 손으로 세다가 점화식을 발견했다. 1부터 3까지는 초기화로 설정값을 넣어주고, 4부터 n까지 규칙을 적용..

DP를 연습한다고 하는데, 난이도가 높아질수록 정말 어려움을 많이느꼈다. 원리를 제대로 파악하려고 노력하자! 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 설계 알고리즘 설계 [접근 방법] : DP 전형적인 DP문제다. 와인을 연속적으로 3잔을 마실수 없기에, 현재 위치에서 고를 수 있는 선택지는 다음과 같다. `xoo`, `oxo`, `oox`의 경우 중 어떤 것이 가장 많이 먹을 수 있는 방법인지 선택하면 된다. dp배열을 2차원 배열..

DP로 풀었다가 다르게 풀었다가, 왔다갔다 하다가 결국 DP로 푼 문제! 이것도 조건을 제대로 안읽어서 한번에 맞추지는 못했다. 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 설계 알고리즘 설계 [접근 방법] : DP 문제를 처음 봤을 때는 반복문으로 무작정 접근했다. 3으로 나눌 수 있으면 나누고, 2로 나눌 수 있으면 나누고 그 다음에는 1을 빼고 풀었다. 그런데 예시의 10을 보고 아예 접근 방법을 다르게 바꾸었다. 현재 내가 가지고 있는 수에서 나누기 3한 값을 1로 만들기 위해서는 연산을 얼만큼 해야 하는지, 나누기 2한 값을 1로 만들기 위..

무난하게 푼 문제! 그렇게 어렵지는 않았다. 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 설계 알고리즘 설계 [접근방법] : DP 숫자가 주어질 때, 이 숫자가 결국에는 0과 1이 얼마나 있는지 개수를 세어야 하는 문제이다. 숫자의 범위가 40보다 작으니 배열을 생성하여 dp로 가능할 것이라 생각했다. DFS보다 배열로 푸는 것이 훨씬 시간복잡도가 적으니 무난히 통과한 문제다. 풀이 과정 1. 최대 40의 숫자가 입력될 수 있으므로 배열 2개를 41크기로 생성한다. zeroArr은 0이 몇 개 있는지 그 값을 담을 배열이고, one..

문제를 보고 dp인줄은 생각하고 있었는데, 풀이과정이 안떠오르다가 노트에 끄적이니까 문득 떠올라서 푼 문제! 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12980 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 알고리즘 설계 [접근 방법] : DP 사용 이 경우는 dp로 풀었다. 처음에 풀이 방법은 모든 testcase를 맞추었지만, 시간초과와 메모리초과가 발생했다. 그래서 시간 단축과 메모리 단축을 계속 생각했고 2번째 풀이를 생각했다. 첫 번째풀이 : 메모리초과 1. 배열을 크키 n..