분류 전체보기

프로그래머스 최소직사각형 c++ // greedy?

https://school.programmers.co.kr/learn/courses/30/lessons/86491 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문풀과정 분류가 완탐이라길래 가로선택-세로선택 분기로 알고리즘짬 -> 최악 : O(2^1000) -> 불가능 그리디로 풀이를 바꾸었다. 2. 전체코드 #include using namespace std; int n; vector big,small; int solution(vector sizes) { int answer = 0; n=sizes.size(); //큰것들모음 - big //작은것들..

프로그래머스 게임맵 최단거리 c++ // 최단거리는 bfs

https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1.삽질과정 ny>=n, nx>=n nx도 n으로 되있어서 틀렸습니다가 났다... 해결 : nx>=m -> continue; 2.전체코드 #include using namespace std; queue q; int v[104][104]; int y,x,ny,nx; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; int solution(vector maps) { int n=..

백준 1912 연속합 c++ [hard]// dp, 연속합중 최대값 구하는 방법

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 나의틀린풀이 나의틀린풀이 : d[i]=max(d[i-1], d[i-1]+a[2], a[2]_ d[i]=max(포함x, 포함o, 새로운값) 2. 정답코드 2시간고민해도 해결이안되어 정답코드를 보았다..... 일단 외우는게 좋을듯하다. #include using namespace std; long long d[100004], a[100004],n; //d[i]: i자리까지 연속합중 최대값 int main(..

백준 2193 이친수 c++ // dp, overflow 해결방법 long long

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. 문풀과정 int -> overflow(-) long long으로 바꿧더니 통과되었다. 2. 전체코드 #include using namespace std; long long d[94][2], n; //d[i][j] : i자리 이친수의 갯수, j:맨뒤가 j인 이친수의 갯수 int main() { ios_base::sync_with_stdio(0); cin.tie(0); d[1][0] ..

백준 11727 2*n 타일링2 c++ // dp

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1.전체코드 #include using namespace std; long long d[1004],n; //2*i 직사각형을 채우는 방법의 수 //d[i]= //첫째사각형 1*2인 경우 : d[n-2] //첫째사각형 2*1인 경우 : d[n-1] //첫째사각형 2*2인 경우 : d[n-2] int main() { ios_base::sync_with_stdio(0); cin.tie(0); d[1] = 1; d[2] = 3; ci..

백준 1003 피보나치 함수 c++ // dp

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 전체코드 #include using namespace std; int t, n; int d[44][2]; //1.테이블정의 // d[i][0] : fibo(i)에서 0이 출력되는 횟수 // d[i][1] : fibo(i)에서 1이 출력되는 횟수 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n - 1) +..

프로그래머스 43105 정수삼각형 c++ // dp , 인덱스에 주의하자, 일반식을 정확하게 짜는방법

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 일반식을 정확하게 짜는방법 오류 : if(j==i)우측 끝일때 d[i][j]=d[i-1][i] 해결 : if(j==i)우측 끝일때 d[i][j]=d[i-1][i-1] 아래그림에서 d[0위치]=d[8위치]==d[i-1][i-1]이 되어야한다! 2. 전체코드 #include using namespace std; int dp[504][504]; //1. d[i][j] : i높이에서 누적 최대합. ..

백준 12852 1로만들기 2 c++ // dp, 경로복원 하는 방법 pre[i]

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. 경로복원 하는 방법(1) : pre[i] : i는 pre[i]로 가는게 최선이다. pre[3] =1 : 3은 1로 가는게 최선임. 2.바킹독 코드 // Authored by : BaaaaaaaaaaarkingDog // Co-authored by : - // http://boj.kr/da0497aabb26436c9ae613785cb439f7 #include using namespace std; int d[1000005]; //d[i] : i를 1로만드는데 필요한 연산의 최소값 int pre[100..