DS Algorithm

 

DS Algorithm - javatpoint

 

알고리즘이란 무엇인가?

알고리즘 은 특히 컴퓨터에서 계산 또는 기타 문제 해결 작업을 수행하는 데 필요한 프로세스 또는 일련의 규칙입니다.알고리즘의 공식적인 정의는 특정 작업을 수행하기 위해 특정 순서로 수행되는 유한한 명령 집합을 포함한다는 것입니다.

완전한 프로그램이나 코드가 아닙니다. 순서도 또는 의사 코드를 사용하여 비공식 설명으로 나타낼 수 있는 문제의 솔루션(논리)일 뿐입니다.

 

알고리즘의 특성

알고리즘의 특성들은 다음과 같습니다.

 

• 입력: 알고리즘에는 몇 가지 입력 값이 있습니다. 0 또는 일부 입력 값을 알고리즘에 전달할 수 있습니다.
• 출력: 알고리즘이 끝날 때 하나 이상의 출력을 얻습니다.
• Unambiguity: 알고리즘은 모호하지 않아야 합니다. 즉, 알고리즘의 지침은 명확하고 단순해야 합니다.
• 유한성: 알고리즘은 유한성을 가져야 합니다. 여기서 유한성은 알고리즘이 제한된 수의 명령을 포함해야 함을 의미합니다. 즉, 명령은 셀 수 있어야 합니다.
• 효율성: 알고리즘의 각 명령이 전체 프로세스에 영향을 미치므로 알고리즘은 효과적이어야 합니다.
• 언어 독립적: 알고리즘의 명령이 동일한 출력을 가진 모든 언어로 구현될 수 있도록 알고리즘은 언어 독립적이어야 합니다.

 

알고리즘의 데이터 흐름

• 문제: 문제는 실 세계의 문제이거나 프로그램 또는 일련의 지침을 작성해야 하는 실제 문제의 인스턴스일 수 있습니다. 이런 명령어 집합을 알고리즘이라고 합니다.
• 알고리즘: 단계적인 절차를 가진 문제를 위해 알고리즘이 설계됩니다.
• 입력: 알고리즘을 설계한 후 필수적이며 요구되는 입력을 알고리즘에 제공합니다.
• 처리 장치(Processing unit): 입력은 처리 장치에 제공되고 처리 장치는 원하는 출력을 생성 할 것입니다.
• 출력: 출력은 결과 또는 프로그램의 결과입니다.

 

알고리즘이 필요한 이유는 무엇일까?

다음과 같은 이유로 알고리즘이 필요합니다.

 

• • 확장성: 확장성을 이해하는 데 도움을 줍니다. 실제 문제가 큰 경우 문제를 쉽게 분석하기 위해 작은 단계로 축소해야 합니다.
  • 성능: 실제 세계는 더 작은 단계로 쉽게 분해되지 않습니다. 문제를 더 작은 단계로 쉽게 나눌 수 있다면 문제가 실현 가능함을 의미합니다.

 

실 세계 예제를 통해 알고리즘을 이해해 봅시다. 레몬 주스를 만들고 싶다고 가정하면 레몬 주스를 만드는 데 필요한 단계는 다음과 같습니다.

 

1단계: 먼저 레몬을 반으로 자릅니다.

2단계: 레몬을 최대한 짜서 용기에 담아 즙을 냅니다.

3단계: 설탕 2큰술을 넣습니다.

4단계: 설탕이 녹을 때까지 용기를 저어줍니다.

5단계: 설탕이 녹으면 물과 얼음을 조금 넣습니다.

6단계: 주스를 냉장고에 5~분 동안 보관합니다.

7단계: 이제 마실 준비가 되었습니다.

 

위의 실 세계 예로 알고리즘의 정의와 직접 비교할 수 있습니다.

 

2단계 전에 3단계를 수행할 수 없으며 레몬 주스를 만들기 위해 특정 순서를 따라야 합니다.

 

알고리즘은 또한 특정 작업을 수행하기 위해 각각의 모든 명령을 특정 순서로 따라야 한다고 말합니다.

 

이제 프로그래밍에서 알고리즘의 예를 살펴보겠습니다.

우리는 사용자가 입력한 두 개의 숫자를 더하는 알고리즘을 작성할 것입니다.

 

다음은 사용자가 입력한 두 개의 숫자를 추가하는 데 필요한 단계입니다.

 

1단계: 시작

2단계: 세 개의 변수 a, b 및 sum을 선언합니다.

3단계: a와 b의 값을 입력합니다.

4단계: a와 b의 값을 더하고 결과를 합계 변수에 저장합니다(예: sum=a+b).

5단계: 합계 인쇄

6단계: 중지

 

알고리즘의 인자들

알고리즘을 설계할 때 고려해야 할 인자들은 다음과 같습니다.

 

• 모듈성: 어떤 문제가 주어지고 그 문제를 알고리즘의 기본 정의인 작은 모듈 또는 작은 단계로 나눌 수 있다면 이 기능이 알고리즘에 맞게 완벽하게 설계되었음을 의미합니다.
• 정확성: 알고리즘의 정확성은 주어진 입력이 원하는 출력을 생성할 때 정의되며, 이는 알고리즘이 알고리즘으로 설계되었음을 의미합니다. 이 알고리즘 분석은 올바르게 수행되었습니다.
• 유지 보수성: 여기서 유지 보수성은 알고리즘을 재정의할 때 알고리즘에서 큰 변경이 수행되지 않도록 알고리즘을 매우 단순한 구조화된 방식으로 설계해야 함을 의미합니다.
• 기능성: 실제 문제를 해결하기 위해 다양한 논리적 단계가 고려되어야 합니다.
• 견고성: 견고성은 알고리즘이 문제를 명확하게 정의할 수 있는 방법을 의미합니다.
• 사용자 친화성: 알고리즘이 사용자에게 친숙하지 않으면 디자이너가 프로그래머에게 설명할 수 없습니다.
• 단순성: 알고리즘이 단순하면 이해하기 쉽습니다.
• 확장성: 다른 알고리즘 설계자나 프로그래머가 자신의 알고리즘을 사용하려면 확장 가능해야 합니다.

 

알고리즘의 중요성

1. 이론적 중요성: 실제 문제가 주어지고 문제를 작은 모듈로 나눌 때. 문제를 분석하려면 모든 이론적 측면을 알아야 합니다.
2. 실용적 중요성: 실제 구현 없이는 이론을 완성할 수 없다는 것을 알고 있습니다. 따라서 알고리즘의 중요성은 이론적인 측면과 실제적인 측면을 모두 고려해야 할 수 있습니다.

 

알고리즘의 문제

다음은 알고리즘을 설계하는 동안 발생하는 문제입니다.

 

• 알고리즘 설계 방법: 알고리즘은 단계별 절차이므로 알고리즘을 설계하려면 몇 가지 단계를 따라야 합니다.
• 알고리즘 효율성을 분석하는 방법

 

알고리즘의 접근

다음은 알고리즘 설계의 이론적 및 실제적 중요성을 모두 고려하여 사용되는 접근 방식입니다.

 

• Brute force 알고리즘:

일반적인 논리 구조를 적용하여 알고리즘을 설계합니다.

이 방법은 필요한 솔루션을 제공하기 위해 모든 가능성을 검색하는 철저한 검색 알고리즘(exhaustive search algorithm)이라고도 합니다.

이러한 알고리즘에는 두 가지 유형이 있습니다.

• • 최적화: 문제의 모든 솔루션을 찾은 다음 최상의 솔루션을 꺼내거나 최상의 솔루션의 값을 알게 되면 해당 최상의 솔루션을 종료 할 것입니다.
  • 희생: 최상의 솔루션을 찾자마자 중단 할 것입니다.

 

• 분할 정복:

이는 바로 알고리즘의 구현입니다. 이를 통해 단계별 변형으로 알고리즘을 설계할 수 있습니다.

알고리즘을 분해하여 다양한 방법으로 문제를 해결합니다.

이를 통해 문제를 여러 가지 방법으로 분류할 수 있으며 유효한 입력에 대해 유효한 출력이 생성됩니다.

이 유효한 출력은 다른 함수로 전달됩니다.

 

• 그리디 알고리즘(Greedy algorithm):

최상의 솔루션을 얻기 위해 각 반복에서 최적의 선택을 하는 알고리즘 패러다임입니다.

구현하기 쉽고 실행 시간이 더 빠릅니다.

그러나 최적의 솔루션을 제공하는 경우는 매우 드뭅니다.

 

• 동적 프로그래밍:

중간 결과를 저장하여 알고리즘을 보다 효율적으로 만듭니다.

문제에 대한 최적의 솔루션을 찾기 위해 다섯 가지 단계를 따릅니다:

 

1. 1. 문제를 하위 문제로 분해하여 최적의 솔루션을 찾습니다.
   2. 문제를 세분화한 후 해당 하위 문제에서 최적의 솔루션을 찾습니다.
   3. 하위 문제의 결과를 저장하는 것을 암기(memorization)라고 합니다.
   4. 동일한 하위 문제에 대해 다시 계산할 수 없도록 결과를 재사용합니다.
   5. 마지막으로 복잡한 프로그램의 결과를 계산합니다.

 

• 분기 및 바운드 알고리즘:

분기 및 바운드 알고리즘은 정수 프로그래밍 문제에만 적용될 수 있습니다.

이 접근 방식은 실행 가능한 솔루션의 모든 집합을 더 작은 하위 집합으로 나눕니다.

이러한 하위 집합들은 최상의 솔루션을 찾기 위해 추가로 평가됩니다.

 

• 무작위 알고리즘:

정규 알고리즘에서 본 것처럼 미리 정의된 입력과 필요한 출력이 가집니다.

이런 일부 정의된 입력 및 필수 출력 집합을 가지고 있고 일부 설명된 단계를 따르는 알고리즘을 결정론적 알고리즘이라고 합니다. 무작위 알고리즘에 무작위 변수가 도입되면 어떻게 될까요?

무작위 알고리즘에서는 일부 무작위 비트가 알고리즘에 의해 도입되고 입력에 추가되어 본질적으로 무작위인 출력을 생성합니다.

무작위 알고리즘은 결정론적 알고리즘보다 간단하고 효율적입니다.

 

• 역추적(Backtracking): 

역추적은 문제를 재귀적으로 해결하고 문제의 제약 조건을 충족하지 않는 경우 솔루션을 제거하는 알고리즘 기술입니다.

 

알고리즘의 주요 범주는 다음과 같습니다.

 

• 정렬: 특정 순서로 항목을 정렬하기 위해 개발된 알고리즘입니다.
• 검색: 데이터 구조 내의 항목을 검색하기 위해 개발된 알고리즘입니다.
• 삭제: 데이터 구조에서 기존 요소를 삭제하기 위해 개발된 알고리즘입니다.
• 삽입: 데이터 구조 내에 항목을 삽입하기 위해 개발된 알고리즘입니다.
• 업데이트: 데이터 구조 내의 기존 요소를 업데이트하기 위해 개발된 알고리즘입니다.

 

알고리즘 분석

알고리즘은 두 가지 수준으로 분석할 수 있습니다. 즉, 첫 번째는 알고리즘을 생성하기 전이고 두 번째는 알고리즘을 생성한 후입니다. 다음은 알고리즘의 두 가지 분석입니다.

 

• 선험적 분석:

여기서 선험적 분석은 알고리즘을 구현하기 전에 수행되는 알고리즘의 이론적 분석입니다.

알고리즘을 구현하기 전에 프로세서 속도와 같은 다양한 요소를 고려할 수 있지만 구현 부분에는 영향을 미치지 않습니다.

 

• 사후 분석:

여기서 사후 분석은 알고리즘의 실제 분석입니다.

실용적인 분석은 임의의 프로그래밍 언어를 사용하여 알고리즘을 구현함으로써 달성됩니다.

이 분석은 기본적으로 알고리즘이 얼마나 많은 실행 시간과 공간을 차지하는지 평가합니다.

 

알고리즘 복잡성

알고리즘의 성능은 다음 두 가지 요소로 측정할 수 있습니다.

 

• 시간 복잡도:

알고리즘의 시간 복잡도는 실행을 완료하는 데 필요한 시간입니다. 알고리즘의 시간 복잡도는 Big O 표기법으로 표시됩니다. 여기서 Big O 표기법은 시간복잡도를 나타내는 점근적 표기법 입니다. 

시간 복잡도는 주로 실행을 완료하는 단계 수를 세어 계산합니다.

예제를 통해 시간 복잡도를 이해해 봅시다.

sum=0;  
// Suppose we have to calculate the sum of n numbers.  
for i=1 to n  
   sum=sum+i;  
// when the loop ends then sum holds the sum of the n numbers  
return sum;  

 

위의 코드에서

루프문의 시간복잡도는 n 이상일 것이고, n의 값이 증가하면 시간복잡도도 함께 증가하게 될 것입니다.

코드의 복잡성, 즉 반환 합계는 그 값이 n의 값에 의존하지 않고 한 단계에서만 결과를 제공하므로 상수 값일 것입니다.

우리는 일반적으로 주어진 입력 크기에 대해 소요되는 최대 시간이므로 최악의 시간 복잡도를 고려합니다.

 

• 공간 복잡도:

알고리즘의 공간 복잡도는 문제를 해결하고 출력을 생성하는 데 필요한 공간의 양입니다.

시간복잡도와 마찬가지로 공간복잡도 역시 big O 표기법으로 표현된다.

 

알고리즘의 경우 다음 목적을 위해 공간이 필요합니다.

 

1. 프로그램 명령어를 저장하기 위해서
2. 상수 값을 저장하기 위해서
3. 변수 값을 저장하기 위해서
4. 함수 호출, 점프 문 등을 추적하기

위해서 입니다.

 

보조 공간(Auxiliary space): 입력 크기를 제외하고 알고리즘에 필요한 추가 공간을 보조 공간이라고 합니다.

공간 복잡도는 공간 즉, 보조 공간과 입력이 사용하는 공간을 모두 고려합니다.

그래서,

Space complexity = Auxiliary space + Input size.
공간 복잡도 = 보조 공간 + 입력 크기.

 

 

알고리즘 유형

알고리즘의 종류는 다음과 같습니다.

• 검색 알고리즘
• 정렬 알고리즘

 

검색 알고리즘

매일 우리는 일상 생활에서 무언가를 검색을 합니다.

이와 유사하게 컴퓨터의 경우에도 방대한 데이터가 컴퓨터에 저장되어 사용자가 어떤 데이터를 요청할 때마다 컴퓨터는 메모리에서 해당 데이터를 검색하여 사용자에게 제공합니다.

배열에서 데이터를 검색하는 데 주로 사용할 수 있는 두 가지 기술이 있습니다.

 

• 선형 검색
• 이진 검색

 

선형 검색

선형 검색은 필요한 요소를 찾을 수 없을 때까지 배열의 처음부터 요소 또는 값 검색을 시작하는 매우 간단한 알고리즘입니다. 검색할 요소를 배열의 모든 요소와 비교하여 일치하는 항목이 발견되면 요소의 인덱스를 반환하고 그렇지 않으면 -1을 반환합니다.

 

이 알고리즘은 정렬되지 않은 리스트로 구현 할 수 있습니다.

 

이진 검색

이진 알고리즘은 요소를 매우 빠르게 검색하는 가장 간단한 알고리즘입니다. 정렬된 목록에서 요소를 검색할 때 사용합니다.

이진 알고리즘을 구현하려면 요소를 순차적으로 또는 정렬된 방식으로 저장해야 합니다.

요소가 임의 방식으로 저장된 경우 이진 검색을 구현할 수 없습니다. 

이 검색은 리스트의 중간 요소를 찾는 데 사용됩니다.

 

정렬 알고리즘

정렬 알고리즘은 배열 또는 지정된 데이터 구조의 요소를 오름차순 또는 내림차순으로 재정렬하는 데 사용됩니다.비교 연산자는 요소의 새 순서를 결정합니다.

 

정렬 알고리즘이 필요한 이유는 무엇일까요?

 

이진 검색 알고리즘은 배열을 특정 순서, 주로 오름차순으로 정렬해야 하므로 이진 검색 알고리즘과 같은 다른 알고리즘의 효율성을 최적화하기 위해 효율적인 정렬 알고리즘이 필요합니다.

사람이 읽을 수 있는 형식인 정렬된 순서로 정보를 생성합니다.

정렬된 목록에서 특정 요소를 검색하는 것이 정렬되지 않은 목록보다 빠릅니다.

 

이상.