코딩테스트/알고리즘6

• 

  [C++ 알고리즘] 다이나믹프로그래밍2 - 배낭문제(Knapsack Problem) 배낭문제(Knapsack Problem) 다이나믹 프로그래밍의 대표적인 예시문제이다. 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 아래와 같은 형식으로 주어진다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제를 요약하자면 아래와 .. 코딩테스트/알고리즘 2022. 1. 4.

• [C++] 벡터 탐색 1. 벡터 내에 존재하는지 여부 탐색 (binary_search) 이 경우에는 이진탐색을 사용하는것이 빠르다. 단 이진탐색을 사용하려면 정렬이 되어있어야 한다. 에 정의되어있다. 아래와 같이 사용한다. binary_search(시작범위, 끝범위, 찾을 값); 예제 코드 #include #include #include using namespace std; int main() { int num; cin >> num; vector vec = { 1,3,5,7,9 }; //존재시 1, 그렇지 않으면 0 리턴 if (binary_search(vec.begin(), vec.end(), num)) { cout num; vector vec = { 1,3,5,7,9 }; int idx = find(vec.begin(),.. 코딩테스트/알고리즘 2021. 9. 7.

• 

  [C++] 숫자 자릿수 더하기 19-> 1+ 9 = 10 이런식으로 자릿수를 구해주는 코드이다. #include using namespace std; int seperateAndPlus(int x) { int res = 0; while (x != 0) { res = res + x % 10; x /= 10; } return res; } int main() { int num; cin >> num; cout 코딩테스트/알고리즘 2021. 9. 7.

• 

  [C++ 알고리즘] 분할정복(Divide and conquer) 개념 분할정복 알고리즘은 주어진 문제를 둘 이상의 부분문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 이를 병합해 문제를 해결하는 알고리즘이다. 종만북의 표현을 빌리자면 각개 격파 라고 간단히 설명할 수 있다. 바로 예제를 보도록 하자. 예제 1 : 수열의 합 1부터 N까지의 값을 구해야 한다고 가정하자. 이를 단순 재귀함수로 구현하면 아래와 같을 것이다. #include using namespace std; int recursiveSum(int N) { if (N == 1) { return N; } else { return recursiveSum(N - 1) + N; } } int main() { int A; cin >> A; cout > A; cout 코딩테스트/알고리즘 2021. 8. 28.

• 

  [C++ 알고리즘] 그리디(탐욕법,Greedy Algorithm) 개념 그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다. 실제 그리디 알고리즘을 검색하면 아래와 같이 나온다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 일반적으로 생각했을 때 눈앞의 이익만을 쫓는 것이 최적의 선택이라고는 할 수 없다. 가령 아래와 같은 상황이 있다고 생각해보자. 예제 1 각 그림의 적힌 숫자는 문제를 푸는데 걸리는 시간이고 우리는 가장 빠른 시간안에 level1, level2, level3문제를 하나씩 해결하려 한다. 이때 문제를 푸는 시간을 최소화 하려면 어떻게 해야 .. 코딩테스트/알고리즘 2021. 8. 8.

• 

  [C++ 알고리즘] 동적 계획법(Dynamic Programming) 개념 동적계획법의 정의는 아래와 같다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산하는 방식. 정의만 가지고는 이해하기 쉽지 않다. 뒤에서 설명하겠지만, 결론적으로 말하자면 배열을 만들어 값들을 저장하고, 후에 그것들을 가지고 답을 구하는 방법이다. 동적 계획법을 이용해 문제를 풀려고 한다면 먼저 점화식을 세워야 한다. 점화식이라는 것은 어떤 수열의 일반항을 이전의 항들을 이용해 정의한 식이다. 고등학교 때 배웠던 수열의 일반항을 구하듯이 n번째 항을 구하는 방법을 식으로 나타낸다고 생각하면 쉽다. 예를 들어 흔히들 아는 피보나치 수열의 점화식은 아래와 같다. 이제 이 식을 가지고 코드로 작성을 해 보도록 하자. 일반적으로 재귀함수를.. 코딩테스트/알고리즘 2021. 7. 31.