티스토리챌린지18 유클리드 호제법 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않으나(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다). 정수론을 배우게 된다면 가장 먼저 나올 확률이 높은 공식이다. 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 최대공약수(GCD)란? - 두 수의 공통된 "약수 중에서 가장 큰 수"를 의미합니다. 최소공배수(LMC)란? .. 2024. 11. 27. 암호화/복호화 1. 개요암호기술은 중요한 정보를 읽기 어려운 값으로 변환하여 제 3자가 볼 수 없도록 하는 기술입니다. 암호기술의 안전성은 수학적인 원리에 기반하며, 보안에 있어서 중요한 정보를 직접적으로 보호하는 원천기술 입니다. 암호기술을 통해 보호하고자 하는 원본 데이터를 평문(plaintext)라고 하며, 평문에 암호기술을 적용한 것을 암호문(ciphertext)라고 합니다. 이렇게, 평문에 암호기술을 적용하여 암호문으로 변환하는 과정을 암호화라고 하며, 다시 평문으로 복원하는 과정을 복호화라고 합니다. 암호화하기 위해서는 암호 키(key)가 필요하며, 키가 있어야만 암호문을 복호화할 수 있습니다. 그렇게 때문에 암호 키는 비밀(secret)로 유지되어야 하며 제3자가 알 수 없어야 합니다. 암호기술을 이용하.. 2024. 11. 26. C언어 189제] 2010/2011 COCI 크로아티아 정보학 공개 경쟁 #2 1번 달팽이는 올라가고 싶다. 출처 : 반크_세계유산 경복궁 문제]땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B 출력 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 예제 입력 1 2 1 5 예제 출력 1 4예제 입력 2 5 1 6 예제 출력 2 2예제 입력 3 100 99 1000000000 예제 출력 3 999999901 출처 : 백준_2869번 참고풀이1].. 2024. 11. 25. 모달(Modal) 사람이 기계와 상호 작용하며 입출력에 사용하는 정보의 유형. 모달(modal)은 언어학, 음악 등 다양한 분야에서 ‘형태’나 ‘유형’의 의미로 사용한다. 예를 들어 음악 분야에서 모달은 특정 음계를 중심으로 음악을 구성하는 방식을 말한다. 언어학에서는 화자의 주관적인 태도와 판단을 표현하며 미묘한 뉘앙스를 전달하는 문법적 요소를 의미한다. 컴퓨팅 분야에서 모달은 사람이 기계와 상호 작용하며 입출력에 사용하는 정보의 유형이다. 예를 들어 키보드, 마우스, 터치스크린, 마이크, 스피커, 카메라, 모니터 등과 같은 장치에서 입출력에 사용하는 텍스트, 음향, 이미지 등의 유형이 모달이다. 사용자가 애플리케이션 또는 웹사이트를 사용할 때 나타나는 대화 상자(dialog box) 또는 팝업 창과 같은 UI 요소를 .. 2024. 11. 24. C++ 125제] 어서와! C++은 처음이지! CHAPTER 11. PROGRAMMING EXERCISE 1. 1) p475 출처 : 반크_반크 20년 백서 ● 위의 프로그램을 컴파일할 수 있도록 생성자, 접근자, 설정자 등의 함수를 추가하라.참고풀이]#define _CRT_SECURE_NO_WARNINGS #include using namespace std; class Point { int x, y; public: Point(int px = 0, int py = 0) { x = px; y = py; } //생성자 함수 int getX() { return x; } //접근자 int getY() { return y; } void setX(int px) { x = px; } //설정자 void setY(int py) { y = py; } ~Point() {} //소멸자 .. 2024. 11. 23. DP(Dynamic Programming, 동적 계획법) Dynamic Programming(동적 계획법)은 1950년대에 리차드 벨만(Richard Bellman)이 알고리즘 최적화를 위해 제안한 전략입니다. 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결합니다. 분할정복 알고리즘은 문제를 독립적인 부분 문제로 분할하고, 부분 문제들을 재귀적으로 해결한 후, 그 결과들을 결합하여 원래의 문제를 해결하는데 반에 DP는 부분 문제들이 서로 독립적이지 않을 때, 즉, 부분 문제들이 다시 자신의 부분 문제를 공유할 때 적용할 수 있습니다. 분할정복 알고리즘은 공유되는 부분 문제들을 반복적으로 해결 함으로써 필요이상의 더 많은 일을 하게 됩니다. 이러한 분할정복 알고리즘의 문제점을 DP는 모든 부분 문제들을 단 한번만 풀고, 그 해를 테이블에 저장함으로써 .. 2024. 11. 22. 분할 및 정복(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. 이진 검색(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++ 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. 이전 1 2 다음 반응형
