본문 바로가기

프로그램/알고리즘25

콜라츠 수열(콜라츠 추측) 콜라츠 추측(Collatz conjecture)은 1937년에 처음으로 이 추측을 제기한 로타르 콜라츠의 이름을 딴 것으로 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불린다. 콜라츠 추측은 임의의 자연수가 다음 조작을 거쳐 항상 1이 된다는 추측이다. 1. 짝수라면 2로 나눈다. 2. 홀수라면 3을 곱하고 1을 더한다. 3. 1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다. 예를 들어, 6에서 시작한다면, 차례로 6, 3, 10, 5, 16, 8, 4, 2, 1 이 된다. 또, 27에서 시작하면 무려 111번을 거쳐야 1이 된다. 77번째에 이르면 9232를 정점으로 도달하다가 급격히 감소하여 34단계를 더 지나면 1이 된다. 이 추측은 컴퓨터로 2^68까지 .. 2024. 12. 17.

백트래킹(Backtracking, 되추적) 모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘 방식으로 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 모든 경우의 수를 고려해야 하는 문제라면 일반적으로 DFS가 편리하다. 그러나 DFS를 절대 쓰면 안 되는 경우가 있는데, 트리의 깊이가 무한대가 될 때이다. 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. 물론 중복검사를 막기 위한 장치를 넣을 수도 있지만, 그럴 바에는 BFS가 편하다. 또 분기점 없이 길이만 죽어라 긴 길이.. 2024. 12. 3.

유클리드 호제법 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않으나(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다). 정수론을 배우게 된다면 가장 먼저 나올 확률이 높은 공식이다. 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 최대공약수(GCD)란? - 두 수의 공통된 "약수 중에서 가장 큰 수"를 의미합니다. 최소공배수(LMC)란? .. 2024. 11. 27.

암호화/복호화 1. 개요암호기술은 중요한 정보를 읽기 어려운 값으로 변환하여 제 3자가 볼 수 없도록 하는 기술입니다. 암호기술의 안전성은 수학적인 원리에 기반하며, 보안에 있어서 중요한 정보를 직접적으로 보호하는 원천기술 입니다. 암호기술을 통해 보호하고자 하는 원본 데이터를 평문(plaintext)라고 하며, 평문에 암호기술을 적용한 것을 암호문(ciphertext)라고 합니다. 이렇게, 평문에 암호기술을 적용하여 암호문으로 변환하는 과정을 암호화라고 하며, 다시 평문으로 복원하는 과정을 복호화라고 합니다. 암호화하기 위해서는 암호 키(key)가 필요하며, 키가 있어야만 암호문을 복호화할 수 있습니다. 그렇게 때문에 암호 키는 비밀(secret)로 유지되어야 하며 제3자가 알 수 없어야 합니다. 암호기술을 이용하.. 2024. 11. 26.

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.

선형 검색(Linear Search) 대상 자료를 순서대로 하나씩 비교해서 원하는 자료를 찾는 검색으로 순차 검색(Sequential Search)라 한다. ※ 선형 검색의 특징• 대상 자료의 범위를 몰라도 검색이 가능하다.• 대상 자료가 정렬되어 있지 않아도 검색이 가능하다.• 검색 속도가 다른 검색에 비해 느리다. C언어]int Sequential_Search(int array[],int n, int k){ //int array[] : 검색될 값들이 있는 배열 변수 //int n : 검색될 값들이 들어 있는 방수 변수 //int k : 실제 검색될 값이 있는 들어있는 변수 int a; //a : 반복횟수 변수 int search;//찾는 값이 있는지 여부를 체크하는 변수 while(1) // { n.. 2024. 11. 15.

퀵 정렬(Quick Sort) 주어진 파일을 특정한 키값보다 작은 값을 갖는 레코드들과 큰 값을 갖는 레코드들로 분리하여, 1개의 파일을 논리적으로 2개의 부 파일로 재배열하고 각각의 부 파일에 대해서 순환적으로 같은 퀵 정렬을 적용해 파일을 정렬하는 방법. C. A. Hore가 고안한 정렬로 첫 번째 데이터를 중간 값으로 설정하고 그 중간 값을 대상으로 왼쪽은 작은 값들을 오른쪽은 큰 값들을 배치하여 대상 자료를 부분적으로 나누어 가면서 되부름 방식으로 반복 분류시켜 정렬하는 방식. 순환프로그램을 수행하기 위해서 보조기억공간으로 스택을 이용한다. 이 정렬 방식은 이미 정렬되어 있는 자료를 정렬할 때는 최악의 경우가 발생한다. C언어]//정수형에 대한 오름차순 퀵정렬을 함수화하면 아래와 같다.void QuickSort(int s, i.. 2024. 11. 12.

셸 정렬(Shell Sort) 셸 정렬은 도널드 셸이 처음으로 제안했습니다. 셸 정렬은 빅데이터보다는 중간 규모(약 6000여개)의 데이터셋에 적합합니다. 주어진 입력 파일을 매개 변수의 값에 따라 여러 개의 부 파일로 나누고, 각 부 파일은 삽입 정렬 기법으로 정렬하는 과정을 되풀이하는 방법. 매개 변수의 값으로 먼저 적절한 값을 선택하고, 이를 점차 감소시켜 가면서 셸 정렬을 수행하면 매개 변수가 ‘1’이 될 때 종료된다. 셸 정렬(Shell Sort)은 바로 인접한 이웃 대신 고정된 거리 마큼 서로 떨어진 데이터 포인트끼리 묶어 이들을 정렬합니다. 첫 번째 패스는 바로 인접한 이웃들이 아닌 고정된 거리만큼 떨어진 두 데이터 포인트를 비교하여 정렬합니다. 두 번째 패스는 네 개의 데이터 포인트로 구성된 하위 리스트를 정렬합나다. .. 2024. 11. 8.

병합 정렬(Merge Sort) 정렬하고자 하는 데이터의 모임을 비슷한 크기의 두 부분으로 반복하여 나눈 뒤, 나누어진 부분 데이터들을 정렬한 다음에 다시 병합하면서 하나의 정렬된 데이터 모임으로 만드는 방법. 1940년에 존 폰 노이만(John von Neumann)이 개발한 병합 정렬(Merge Sort)의 특징은 입력 데이터의 정렬 여부와는 관계가 없이 맵리듀스와 같은 빅데이터 알고리즘 처럼 분할 및 정복 전략을 사용합니다. 병렬 정렬 순서]1. 입력된 리스트를 크기가 같은 두 부분으로 나눈다.2. 나뉜 부분의 크기가 1이 될 때까지 반복해서 나눈다.3. 각 부분을 정렬한 뒤 병합하여 최종적으로 정렬된 리스트를 반환한다. Python]def MergeSort(list): if len(list)>1: mid =.. 2024. 11. 1.

이전 1 2 3 다음

티스토리툴바