Algorithm

프로그래머스 연속된부분수열의합 c++ // 정렬된 입력은 이분탐색, 누적합

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 0. 오름차순 정렬조건 -> 이분탐색은 정렬시에만 사용가능하다 -> 이분탐색을 이용해 보자! 1. 누적합배열을 만들고 2. 예외처리 : 누적합에 정답(k)가 있는경우 누적합 정의에따라 [0,해당idx]가 정답후보임 3. 누적합배열을 돌면서, k + v[i]가 존재한다면, [i+1, 찾은idx]가 정답후보임 // +임에 주의, 3 일경우 10을찾아야 10-3 == 7(k) 가 됨 4..

백준 1699 제곱수의 합 c++ // dp 2차원 to 1차원, 수학으로 시간복잡도줄이기

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 0. 시행착오 1. dp[104]로 선언해놓고 for(int i=0~104)로 초기화 -> out of bound... 2. 2중for문 100000 * 100000 으로 해놓고 왜안됨? 뻘짓.. 1. 수학으로 시간복잡도줄이기 문제 : i의 범위 100000 * j의 범위 100000 -> 시초 해결 : i의범위는 root n > n; //dp[i][j] :..

백준 11052 카드구매하기 c++ //dp 관찰방법

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 1.dp 관찰방법 i행에 주머니(동전)을 한개씩 !추가! 하면서 target(N개 카드) 를 채워나간다. 2.의사코드 1. i행에 1번째 주머니, 2번째 주머니를 추가해나가면서 관찰한다. 2. 관찰결과 위쪽(이번에 추가된 주머니 미사용하는경우) 과 d[j-i] + arr[i]( j-i개 카드를 추가하기 위해 이번에 추가된 주머니 사용하는경우)를 비교해야함을 알아낸다. 3.전체코드 #include usin..

백준 1912 연속합 c++ // dp, 규칙발견, ox를 그때그때 선택해버리기

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1 . ox를 그때그때 선택해버리기 1.완탐 : i번째수를 선택함, 안함으로 2^n 탐색해야함 2. 선택한경우 vs 선택안한경우에서 최적인 경우를 그때그떄 선택한다. 3. 이전값 + 현재값() vs 현재값(나부터 연속합 새로시작) 중에 큰값을 선택하면 된다. 2.전체코드 #include using namespace std; long long d[100004], a[100004],n; //d[i]: i자리까지..

백준 11053 LIS c++ // dp, 규칙발견, 일반화

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 의사코드 1. dp[i]를 정의하고 2. 채워나가면서 규칙(점화식)을 발견하라. 2. 전체코드 #include using namespace std; int n,a[1004],dp[1004]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); c..

프로그래머스 2개이하로다른비트 c++ // 비트마스킹, 관찰, 규칙성발견

https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 관찰, 규칙성발견 1. 완탐 -> 너무 빡구현 & 10^15 -> 불가능 2. 관찰을 통한 규칙성발견 1(1) 2(10) 2(10) 3(11) 3(11) 5(101) 4(100) 5(101) 5(101) 6(110) 6(110) 7(111) 에서 최초0을찾고 // num and i ==false -> 최초0의 위치 그곳을 1로바꾸고 // *or1 -> 무조건 1이됨 이전비트를 0으로 바꾸면 ..

백준 1520 내리막길 c++ // top-down dp, dfsDp, 상하좌우탐색 문제점

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. top-down dp 위에서부터구하는 dp를말한다. 재귀로 구현한다. fibo(15)=fibo(14)+fibo(13) ... 2. bottom-up dp 위에서부터구하는 dp를말한다. 반복문으로 구현한다. fibo(3)=fibo(1)+fibo(2) / fibo(4)= ... / fibo(15)= ... 3. 상하좌우탐색 문제점 -> or 아래 or 5시대각선 탐색은 배열을 i,j 한칸씩 탐색하면서..

백준 1890 점프 c++ // dp, 배열순회dp, dp[next] += dp[cur]

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 1. 의사코드 1. dp도 배열한칸씩 탐색하는것이다. 2. pass 조건을 잘 생각하면 된다. 3. dp[i][j]= 어쩌구 가 아닌 // d[next] +=d[cur] 형태로도 짤수가 있다. 2.전체코드 #include using namespace std; typedef long long ll; ll dp[104][104],a[104][104]; //오큰수의 갯수 [길이][시작숫자] ..