연잎의 develog

[C++] 순열(Permutation) 조합(Combination) 알고리즘 :: 개발 블로그 (tistory.com) [C++] 순열(Permutation) 조합(Combination) 알고리즘 백준에서 완전 탐색 문제를 풀다가 항상 조합과 순열을 만들 때 헷갈려서 아예 시간을 내어 정리하였다. 이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다. 이후 나오는 hongchan.tistory.com 브루트 포스 문제를 풀다보면 거의 순열 or 조합 의 연장선인 경우가 많다! 오늘은 c++ 로 순열과 조합을 어떤식으로 구현할 수 있는지 정리해보려고 한다. 1) 순열 (nPr) 서로 다른 n개 중 순서를 고려하여 서로 다른 r 개를 뽑는 경우. (순서O, 중복X) 중복을 막기위해 ch..

14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net [문제] [해결전략] nn을 설정하고 그때의 profit값을 활용해 최대 수익을 갱신해준다. [풀이] #include #include using namespace std; typedef pair ci; int max_profit=-1; //최대수익 void consult(int n,int profit,int day, vector consulting) { //총 일수, 수익,현재 날짜, 상담 정보 if (day > n) //n일차를 넘어서면 { max_profit = max(max_profit, profit); // 최대 수익 갱신. return; } if ..

17626번: Four Squares (acmicpc.net) 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net [문제] 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램 [해결전략] 1. 재귀탐색 제곱수들을 배열에 저장해놓고, 1 3 9 16 25 36 49 64 재귀함수이용(최대 depth = 4)해서 4개의 정수를 뽑자. 그런데 n의 범위를 살펴보니 1 ≤ n ≤ 50,000 이고 제곱급취하면 225니까 1~ 4개의 정수를 뽑는 경우의수는 ..

18511번: 큰 수 구성하기 (acmicpc.net) 18511번: 큰 수 구성하기 첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 www.acmicpc.net [문제] [해결전략] 1. 집합 K의 원소로 만들수 있는 모든 숫자를 만들고 n보다 작을때에만 갱신시킨다. -> 중복 순열. 재귀함수 활용. (C++) 중복 순열(Repeated Permutation) 구현하기 - 평생 공부 블로그 : Today I Learned‍ 🌙 (ansohxxn.github.io) (C++) 중복 순열(Repeated Permutation) 구현하기 ..