분류 전체보기

프로그래머스 보행자천국 c++ // dp, 경우의수는 dp를 의심하라.

https://school.programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 의사코드 (별:내위치) 4가지 경우의 수가 나온다. 이전 map의 상황에 따라 조건문을 분기한다 2. 전체코드 #include using namespace std; int MOD = 20170805; int d[504][504][2]; //좌표, 0-> 1아래 // 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요. int solution(int m, int n, vector ..

프로그래머스 소수찾기 c++ // 순열 3P1+3P2+3P3 하는방법, 소수판별함수, dfs

https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 순열 3P1+3P2+3P3 하는방법 do{ string s=""; for(int i=0;i

프로그래머스 미로탈출명령어 c++ // dfs 가지치기 방법, dfs중복방문 방법, dfs 시간복잡도 계산방법

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. dfs중복방문 방법 그냥 visit처리안하고 depth==k일때 리턴하면 된다. 2. dfs 시간복잡도 계산방법 dfs(0) :dfs(상) dfs(하) 좌 우 dfs1번당 자식4개 생김 깊이:k ex)k==2일때, 자식==16(4^2) 복잡도 : 4*4*4*4*4(깊이만큼) == 4^k승 3. dfs 가지치기 방법 1. 사전순으로 dy,dx정함 -> 첫답이 최적해임 -> 첫답을 찾았으면 f..

백준 2565 전깃줄 c++ // dp, LIS(최장부분증가수열) 풀이

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. LIS(최장부분증가수열) 풀이 ex) 수열 / dp값 /해당경우의수 3 / 1 / 3 5 / 2 / 3 5 1 / 1 /1 6 / 3 /3 5 6 4 / 2 /3 4 또는 1 4 일반화 : 앞에서 자기보다 작은게있다 -> 그 dp값 중 최대값 +1 행동영역 : dp문제를 LIS 문제로 해결할수 있을지 시험해보자 2. 의사코드 1. first에 대해 정렬후 2. second에 대해 최장부분증가수열 중..

백준 2470 두용액 c++ // 투포인터는 st,en중 누구를 움직일지 결정하라

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 의사코드 1.1 st,en중 누구를 움직일지 결정하라 if (sum1 커져야함->음수를 줄임 -> st++ else e--; //합이양수 -> 작아져야함 -> 양수를 줄임 -> e++ 1.2 변수 테이블을 정의하라 //ret : 현재까지 값중 0에 가장가까운 합 2. 전체코드 #include using namespace st..

백준 2748 피보나치수2 c++ // 탑다운 dp 형식

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include using namespace std; long long dp[91], n; long long fibo(long long idx) { //기저사례 if (idx == 0 || idx == 1) return idx; //메모 long long& ret = dp[idx]; if (ret) return ret; //값이 있으면 바로리턴 //로직 retu..

백준 2225 합분해 c++ // dp 규칙찾는 방법

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. dp 규칙찾는 방법 1.1 표를그린다 1.2 규칙을세우고(뒤에만 숫자추가하기) 경우의수를 센다. 1.3. 그 숫자가 어디서 왔는지 규칙을 찾고 화살표로 표시한다 1.4. 규칙을 찾았으면 dp 테이블로 옮기고 숫자의 이동을 표시한다. 1.5. 점화식을 세운다(dp[j]=dp[j]+dp[j-1]) 2. 전체코드 #include using namespace std; int n, k; int dp[204]; int divd = 1000000000; int main() { ios_base::sync_with_stdio(0); ..

백준 2294 동전2 c++ // dp 동전논리 정리, 규칙성발견 dp테이블 형식

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 0. 규칙성발견 dp 테이블 형식 dp : target 후보들.. ex) dp : 0 1 2 3 4 5 ... 15 (target) 1 5 7(동전들) dp[i][j] : i원 추가시 j원을 만드는 최소 동전갯수 i원들을 추가해나가면서 table을 완성시킨다 => 규칙성발견 1. 동전논리 정리 (j-coin)의 이유 5원일때) dp[12]=d[7]+1 dp[7]의 ..