Algorithm (24) 썸네일형 리스트형 순열과 조합 순열 $ _nP_r : \frac{n!}{(n-r)!} $ 서로 다른 원소를 가진 집합에서 대상들을 선택하여 순서 있게 배열하는 것 설계 단순히 $ _nP_r $ 을 구하고 싶다면 위의 공식을 이용해서 코드를 짜면 된다. 다만 유의할 점은 팩토리얼은 n이 조금만 커져도 수가 매우 커지기 때문에 위의 식 그대로 보다는 정리된 식을 사용하는 것이 효율적이다. long long permutation (int n, int r) { long long result = 1; for (int i = n; i > n-r; i--) { result *= i; } return result; } 혹은 재귀로 나타낼 수도 있다. long long permutation (int n, int r) { if (r == 0) retu.. Palindrome (회문) palindrome (회문) 회문 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다. Ex) TENET, 기러기, 수박이박수 가장 직관적인 방법은 가장 첫글자와 마지막글자, 두번째 글자와 마지막에서 두번째 글자를 서로 다 비교해 보는 것이다. string s; bool palindrome (string s) { int N = s.length()-1; for (int i = 0; i #a#b#d#c#c#d# 각 자리 사이사이에 같은 문자(#)를 넣어 홀수개의 스트링 길이로 만들어주면 된다. 구현 #include #include #include #.. Dynamic Programming Dynamic Programming 다이나믹 프로그래밍은 특정 알고리즘이 아닌 디자인 패러다임입니다. 우리가 알고 있는 이러한 디자인 패러다임은 분할 정복, 백트레킹 등이 있습니다. 최적화 문제: optimal value를 찾는 솔루션, 최대화 최소화 문제 우리는 최적의 선택을 모른다. 따라서 우리는 미리 계산한 하위 문제의 비용을 기반으로 하위 문제를 모두 시도한다. 우리가 내리는 선택에 따라 해결해야 할 하위 문제가 결정된다. 최적화 예시 최단거리 문제: 포항에서 서울까지가는 길은 많습니다. 최단 경로, 가장 경치 좋은 경로, 가장 빠른 경로를 계산하려고합니다. 잡 스케줄링: 여러 프로세서에서 작업 세트를 예약하는 방법에는 여러 가지가 있습니다. 프로세서의 다양한 기능과 작업의 다양한 리소스 요구 사.. [STL] Map STL map map은 key, value 페어로 이루어진 자료 구조입니다. Key에 대한 중복이 없습니다. 레드블랙 트리(Red-Black Tree 이하 RB Tree) 기반으로 되어있기 때문에 모든 데이터는 정렬되어 저장됩니다. 빠른 검색 속도를 가집니다. ( $ O(\log(N)) $ ) 인덱스가 따로 존재하지 않기 때문에 iterator를 사용합니다. 선언 map : key와 value를 pair 형태로 선언합니다. Method begin(): beginning iterator를 반환 end(): end iterator를 반환 insert(make_pair(key,value): 맵에 원소를 pair 형태로 추가 erase(key): 맵에서 key(키값)에 해당하는 원소 삭제 clear(): 맵의 .. [DP] Knapsack problem Knapsack Problem 도둑이 박물관에 침입했습니다. 멋진 그림, 조각품, 보석이 사방에 있습니다. 도둑은 이러한 물건의 가치를 잘 알고 있으며, 각각 이 진귀한 물건들이 시장에서 수백 또는 수천 달러에 거래 되는 것도 잘 알고 있습니다. 그러나 도둑은 현장에 배낭 하나만 가져 왔고, 가방의 수용량 만큼만 가지고 나갈 수 있습니다. 도둑은 가치를 극대화하기 위해 어떤 품목을 가져 가야합니까? 문제에는 두가지 버전이 있습니다. 1. Fraction knapsack problem 2. 0-1 knapsack problem 차이점은 보물을 가루로 만들어 일부만 취할 수 있는지 없는지 여부입니다. 1번의 경우에는 그리디 알고리즘으로 간단하게 해결이 가능합니다. 각 항목에 대해 파운드당 가치를 계산합니다... 최대공약수, 최소공배수, 소인수분해 1. 소인수분해 소수를 모두 구해서 나눠보는 것 보단 2부터 차례대로 나눠 나머지를 확인하는 것이 더 효율적이다. 왜냐하면 결국 2, 3, 5 등의 소수로 나눠떨어지지 않는다면 그들의 배수인 4, 6, 10.. 등으로도 나눠떨어지지 않을 것이기 때문에 항상 나누는 수가 소수일 때 먼저 나눠떨어지는 효과를 갖기 때문이다. 예를 들어, 24라는 수를 소인수분해하려면 우선 2로 나눠본다. 24 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 12를 다시 2로 나눈다. 12 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 6을 다시 2로 나눈다. 6 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 3을 다시 2로 나눈다. 3 % 2 = 1 나눠떨어지지 않으므로 3으로 다시 나눈다. 3 % 3 = 0 .. [DP] Multiply Chain Matrix Algorithm Multiply Chain Matrix Algorithm MCM algorithm이란? 두 개 이상의 행렬을 곱할 때, 곱하기 연산을 최소로 할 수 있게 적절히 계산 순서를 바꿔주는 문제이다. 행렬의 곱셈은 다음과 같이 결합법칙이 성립된다. A x B x C = (A x B) x C = A x (B x C) 하지만 행렬을 곱하는 순서에 따라 곱하는 횟수가 달라지게 된다. 예를 들어, A = 20 x 1, B = 1 x 30, C = 30 x 10, D = 10 x 10 의 크기를 가진 행렬들이 있다고 가정하자 A x B x C x D의 값을 구하려면 적절히 괄호를 쳐서 아래와 같은 경우의 수를 만들 수 있다. ((A x B) x C ) x D) = (20 x 1 x 30) + (20 x 30 x 10) .. [DP] LCS (Longest Common Subsequence) Substring vs Subsequence substring: 연속되고 진행 순서도 맞는 부분 문자열 subsequence: 연속적이지는 않지만 진행 순서는 맞는 부분 문자열 ex) Iamhungry substring: "mhun" subsequence: "mugy" LCS의 길이 구하기 예시로 설명하는게 편하기 때문에 예시를 하나 들어보겠다. 문자열 ACAYKP와 CAPCAK가 있다고 가정해보자. ACAYKP 를 기준 string으로, CAPCAK를 비교 String으로 두자. 그렇다면, 아래의 표와 같은 모양이 생성된다. 첫 번째로 할일은 문자열 맨 앞에 0을 추가해 첫번째 행과 열을 모두 0으로 만드는 것이다. 이유는 나중에 LCS를 찾을 때 0이 되면 반복문을 종료하기 위해서이다. 여기가 (0,.. 이전 1 2 3 다음