본문 바로가기

전체 글932

분할 및 정복(Divide and Conquer) 전략 알고리즘 분할 정복(Divide and Conquer)은 컴퓨터 과학에서 매우 중요한 알고리즘 설계 원칙 중 하나입니다. 이 전략은 큰 문제를 더 작고 관리하기 쉬운 하위 문제들로 나눈 뒤, 각 하위 문제를 개별적으로 해결하고 그 결과를 모아 전체 문제를 해결하는 방식입니다. 예를 들어, 수학에서 최대공약수(GCD)를 구하는 문제를 생각해보겠습니다. 이 문제를 분할 정복 전략으로 해결할 수 있습니다. 먼저, 두 수 a와 b가 주어졌을 때, a가 b보다 작거나 같으면 b가 최대공약수가 됩니다. 그렇지 않으면, a와 b의 중간값인 m을 찾아서, a를 m으로 나눈 몫 q1과 b를 m으로 나눈 몫 q2를 구합니다. 그리고 나서, q1과 q2의 최대공약수를 구하면 됩니다. 이 과정을 재귀적으로 반복하면 결국 두 수의 .. 2024. 11. 21.

보간 검색(Interpolation Search) 사전식 검색이라고도 하며 찾고자 하는 데이터가 있음직한 부분을 검색하는 방법이다. 보간 방법에 따라 검색 효율성이 달라지며 키 값의 분포가 일정할 때 주로 사용되는 방법이다. 보간 검색은 이진 검색과 유사하나 리스트의 가운데를 분할하지 않고 불균등하게 검색할 위치를 선택한다. 이진 검색과 마찬가지로 보간 검색을 사용하려면 데이터를 미리 정렬해야 한다.보간 검색에서 키 값을 찾는 공식은 아래와 같다. C언어]void Interpolation_Search(int Array[], int n, int key){ //int Array[] : 검색될 값들이 정렬되어있는 배열 변수 //int n : 검색될 값들이 들어 있는 방수 변수 //int key : 실제 검색될 값이 있는 들어있는 변수 int f.. 2024. 11. 20.

C언어 186제] 2022년 한양대학교 ERICA 캠퍼스 Zero One Algorithm Contest A번 ZOAC 5 출처 : 반크_세계유산 경복궁 문제]2022년 12월, 다섯 번째로 개최된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 매번 새로운 방식으로 문자열을 보여주던 성우는 이번 대회에서는 평범하게 앞 글자부터 하나씩 보여주기로 했다. 성우는 문자를 입력하기 위해 키보드로 손을 뻗은 순간, 실수로 마시던 소주를 키보드에 쏟아버리고 말았다... 알코올에 취한 키보드는 어떤 자판을 한 번만 눌러도 N번 누른 것처럼 인식을 하게 되어버렸다! 소중한 키보드를 고치기 위해 고장 접수를 하는 성우는 N을 정확하게 알아야 한다. 눈물이 앞을 가려 모니터를 제대로 볼 수 없는 성우를 위해 대신 N을 구해주도록 하자! 입력 첫째 줄에 성우가 고장 난 키보드로 입력한 문자열이 주어진다. 문자열의 길.. 2024. 11. 19.

C언어 185제] 손익분기점 출처 : 반크_세계유산 경복궁 문제]월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고.. 2024. 11. 19.

이진 검색(Binary Search) 검색 대상 자료가 먼저 정렬되어있어야 하며, 어떤 항목들을 두 부류로 나누어 그 가운데 조건을 만족하지 않는 부분은 버리고 최저와 최고 인덱스를 갱신하여 나머지 부분에 이분법을 반복하여 적용하면서, 원하는 검색값이 있는 항을 찾아내는 방법. C언어]void Binary_Search(int Array[],int n, int key){ //int Array[] : 검색될 값들이 정렬되어있는 배열 변수 //int n : 검색될 값들이 들어 있는 방수 변수 //int key : 실제 검색될 값이 있는 들어있는 변수 int low,high,mid;//이분검색을 하기위한 변수 low=1; high=n; while(1) { mid=(low+high)/2; if(.. 2024. 11. 19.

C++ 124제] 어서와! C++은 처음이지! CHAPTER 10. PROGRAMMING EXERCISE 5. p435 출처 : 반크_반크 20년 백서 참고풀이]#define _CRT_SECURE_NO_WARNINGS #include using namespace std; class Time { private: int hours; int minutes; public: Time() :hours(0), minutes(0) {} Time(int h, int m) :hours(h), minutes(m) {} void displayTime() { cout } Time& operator++() { ++minutes; return *this; } void ProcessTime() { if (minutes > 59) {.. 2024. 11. 18.

C++ 123제] 어서와! C++은 처음이지! CHAPTER 10. PROGRAMMING EXERCISE 4. p434 출처 : 반크_반크 20년 백서 참고풀이]#define _CRT_SECURE_NO_WARNINGS #include using namespace std; class Box { private: double length; double width; double height; static int count; public: Box(int l = 0, int w = 0, int h = 0) :length(l), width(w), height(h) {} double getVolume(void) { return length * width * height; } void printBox(Box box); }; int Box::count = 0; void Box::p.. 2024. 11. 18.

C++ 122제] 어서와! C++은 처음이지! CHAPTER 10. PROGRAMMING EXERCISE 3. p434 출처 : 반크_반크 20년 백서 참고풀이]#define _CRT_SECURE_NO_WARNINGS #include using namespace std; class Box { private: double length; double width; double height; public: Box(int l = 0, int w = 0, int h = 0) :length(l), width(w), height(h) {} double getVolume(void) { return length * width * height; } void Print(); bool operator { return (length w.. 2024. 11. 18.

C++ 121제] 어서와! C++은 처음이지! CHAPTER 10. PROGRAMMING EXERCISE 2. p433 출처 : 반크_반크 20년 백서 참고풀이]#define _CRT_SECURE_NO_WARNINGS #include using namespace std; class Box { private: double length; double width; double height; public: Box(int l = 0, int w = 0, int h = 0) :length(l), width(w), height(h) {} double getVolume(void) { return length * width * height; } void Print(); bool operator== (Box& box2) { return (length == box2.. 2024. 11. 18.

C++ 120제] 어서와! C++은 처음이지! CHAPTER 10. PROGRAMMING EXERCISE 1. p433 출처 : 반크_반크 20년 백서 참고풀이]#define _CRT_SECURE_NO_WARNINGS #include using namespace std; class Box { private: double length; double width; double height; public: Box(int l=0, int w=0, int h=0):length(l), width(w), height(h){} double getVolume(void) { return length * width * height; } void Print(); Box operator +(const Box& box2); }; void Box::Print() { cout cou.. 2024. 11. 17.

C++ 119제] 어서와! C++은 처음이지! CHAPTER 09. PROGRAMMING EXERCISE 6. p395 출처 : 반크_반크 20년 백서 참고풀이]#define _CRT_SECURE_NO_WARNINGS #include using namespace std; class Game { private: string S; static int count; public: Game(string S) { count++; this -> S = S; Show(); } void Show() { cout S } ~Game() { count--; } }; int Game::count = 0; int main() { //첫번째 플레이어 객체를 생성한다. Game g1("One"); //두번째 플레이어 객체를 생성한다. .. 2024. 11. 16.

C언어 184제] 2005년 1월 USACO Contest Silver 3번 거리의 합 출처 : 반크_세계유산 경복궁 문제]수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오. 즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다. 입력 첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다. 출력 첫째 줄에 답을 출력한다. 예제 입력 1 5 1 5 3 2 4 예제 출력 1 40 출처 : 백준_2399번 참고풀이]#include #include //malloc(), free() int main() { int i,j;//인덱스 또는 반복변수 .. 2024. 11. 15.

이전 1 2 3 4 ··· 78 다음

티스토리툴바