알고리즘
알고리즘은 문제를 해결하기 위한 절차나 방법을 의미하는 단어로 페르시아의 수학자인 알-콰리즈미의 이름에서 유래되었다고 한다.
정확한 의미는 알고리즘은 어떠한 행동을 하기 위해 만들어진 명령어들의 유한 집합 이라고도 한다.
컴퓨터 프로그램은 정교한 알고리즘의 집합으로 수학 또는 컴퓨터 과학에서 말하는 알고리즘은 반복되는 문제의 풀기위한 작은 진행 절차를 의미하고 있기도 하다.
의사 코드
간단하게 설명하자면 프로그램 코드를 작성하기 전 작성자가 알고 있는 일상 언어를 통해서 프로그램의 작동 논리를 단순하게
풀어쓰는 것을 의미한다. 의사 코드를 통해 먼저 논리적으로 풀고 코드를 작성한다면 개발 시간에 있어서 유용한 효과를 볼 수 있다.
의사 코드의 장점으로는
- 시간 단축: 방대한 코드를 작성하는 경우 만들다 보면 구체적이고 세세한 로직을 찾는데 시간이 걸리겠지만 의사 코드를 통해서 찾아야 하는 시간을 단축시킨다면 실제 개발 시간에 있어서 단축시킬 수 있다
- 디버깅 이점: 코드 작성 완료 시 테스트를 하고 나면 오류가 발생할 경우에 디버깅을 통해 오류를 추적해야 하는데 이럴 때 의사 코드를 통해서 문제가 난 지점의 목적을 알고 그 부분에만 신경을 써서 디버깅을 할 수 있다.
- 협업: 동료 개발자나 또는 비개발자 동료의 경우에도 코드를 해석하는데 시간이 걸리거나 해석할 수 없는 경우에도 의사 코드를 통해서 해당 로직에 대한 의미를 전달시킬 수 있다.
시간 복잡도 [ Time Complexity ]
알고리즘의 소요 시간을 정확하게 평가하기는 어렵기 때문에 시간 증가의 패턴을 대략적으로 나타낸 시간 복잡도의 개념이 등장했다.
시간 복잡도를 통해서 효율적인 프로그래밍을 할 수 있는데 보통 시간 복잡도는 빅-오 표기법을 사용한다고 할 수 있다.
Big - O 표기법
- Big - O : 점근적 하한선 -> 같거나 좋지 않다. (최악)
- Big - Ω(오메가) : 점근적 상한선 -> 아무리 나빠도 기존 함수보단 같거나 좋다. (최선)
- Big - θ(세타) : 점근적 상한 과 하향의 교집합 -> 아무리 좋거나 나빠도 기본 함수 범위 안에 존재 (평균)
빅오 표기법을 통하여 최대 이 시간까지도 걸릴 수 있을 것이다를 고려해서 그에 맞는 대응방법을 효과적으로 대응할 수 있는
장점을 가지고 있다.
O(1) [ Constant complexity ]
연산 횟수에 비해 시간이 얼마만큼 소유되는 가를 표기하는 방법 입력값이 증가해도 시간이 늘어나지는 않는다 즉 입력값의 크기에
상관없이 즉시 출력 값을 얻을 수 있다는 의미기도 하다
public int Big_O_1(String[] arr, int index) {
return arr[index];
}
String[] arr = new int[]{A, B, C, D, E};
int index = 1;
String results = Big_O_1(arr, index);
System.out.println(results); // B" 입력값이 아무리 커도 바로 즉시 출력값을 얻을 수 있다. "
O(n) [ Linear complexity ]
입력값이 증가함에 따라 시간도 동일한 비율로 같이 증가하는 것을 의미한다. 입력값이 1이 증가한다면 시간도 1이 증가된다고 할 수 있다.
코드에 따라 "2n" "20n" "2000n" 등이 있을 수 있지만 빅 오 표기법에 있어서는 모두 O(n) 표기법으로 통일한다는 점을 알아두자.
public void Big_O_n(int n) {
for(int i = 0; i < n; i++) {
// 테스트 실행 결과 약 1초
}
}
public void Big_O_n_2(int n) {
for(int i = 0; i < n * 2; i++) { // 주어진 값이 다름
// 테스트 실행 결과 약 1초
}
}" 입력값이 커지면 커질수록 계수의 의미가 점점 퇴색되기 때문에 그래서 n으로 통일해서 표시한다. "
O(log n) [ Logarithmic complexity ]
O(1) 다음으로 빠른 시간 복잡도를 가진 케이스인데 우리가 흔히 알고 있는 BST(Binary Search Tree)와 같은 로직이다.
매번 데이터를 찾기 위해 데이터를 절반으로 줄이면서 탐색해서 찾아낸다.
O(log n^2) [ Quadratic complexity ]
입력값의 증가에 따라 그 시간이 n의 제곱수의 비율로 증가되는 케이스다. 예시로 1에 1초가 걸리던 로직이 5를 주면 25초가 걸린다면 해당 케이스라고 보면 된다.
public void Big_O_quadratic(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
// 테스트 실행 결과 약 1초
}
}
}
public void Big_O_quadratic2(int n) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
// 테스트 실행 결과 약 1초
}
}
}
}" O(n)처럼 O(log n^2)도 3승 또는 5승이던 표기적으로 O(log n^2)라고 표시한다 "
O(log 2^n) [ Exponential complexity ]
가장 느린 시간 복잡도를 가지고 있는데 보통은 잘 사용하지 않는다 주로 사용하는 알고리즘은 재귀로 구현된 피보나치가 대표적이다.
public int fibonacci(int n) {
if(n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci (n - 2);
}
탐욕 알고리즘 [ Greedy ]
탐욕스러운, 욕심 많은 이란 뜻을 가진 이 알고리즘은 당장 진행 중인 상황에 있어서 최적의 상황만 쫒아서 최종 해답을 얻는 방법이다.
- 선택 절차 : 현재 상황에서 최적의 해답을 탐색하고 선택한다.
- 적절성 검사 : 선택된 풀이가 문제의 조건을 만족하는지 검사
- 해답 검사 : 원래 문제가 해결되었는지 검사하고 해결되지 않았으면 돌아가 다시 과정을 반복
탐욕 알고리즘은 문제를 해결하는 과정 매 순간마다 최적의 해답을 찾으며 이를 통해서 최종 문제 해결에 도달하는 해결 방식이라 할 수 있는데 다만 그렇게 하기 위해서는 두 가지의 조건을 만족하는 특정 상황이 아니면 알고리즘의 최적의 해를 보장하지 못한다는 점이 있다.
- 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않게 한다.
- 최적 부분 구조: 문제의 대한 최종 해결 방식은 부분 문제에 대한 최적 문제 해결방법으로 구성
이를 통해서 해당 알고리즘은 언제나 최적의 결과를 달성하는 것은 아니지만 최대한 해결에 대한 근삿값을 빠르게 도출할 수 있는
장점을 가지고 있다는 걸 알 수 있는데 이 장점으로 탐욕 알고리즘은 또한 근사 알고리즘으로 사용하기도 한다.
완전 탐색 알고리즘 [ Brute-Force Algorithm ]
모든 경우의 수를 시도하는 방법인 완전 탐색 알고리즘은 컴퓨터의 성능에 의존해 해결에 중점을 두어 문제를 해결하는 알고리즘이다.
공간 또는 시간 복잡도의 요소를 고려하지 않는 최악의 결과가 나오더라도 해결 방법을 찾으려고 할때 사용한다고 할 수 있다.
- 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
- 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때
위에서 거론했다 싶이 단점으로는 아주 많은 자원을 필요로 하는 매우 비효율적인 알고리즘이기 때문에 특정 경우에는 다른 알고리즘을 사용하는게 권장된다.
순차 검색 알고리즘 [ Sequential Search ]
특정한 값을 찾기위해 인덱스 0부터 마지막 인덱스까지 순차적으로 검색해서 찾는 알고리즘.
public boolean SequentialSearch(int[] arr, int findKey) {
// 찾으려는 키를 받아서 배열 내부에 있는지 체크 메서드
int n = arr.length; // 배열 크기를 지정
boolean result = false; // 기본적으로는 false
for(int i = 0; i < n; i++) {
if(arr[i] == findKey) { // 받아 온 키가 있는지 순차비교
result = true; // 있으면 true로 설정
}
}
return result;
}
문열 매칭 알고리즘 [ Brute-Force String Matching ]
길이가 n인 전채 문자열과 길이가 m인 문자열 패턴을 포함하고 있는지 검색하는 알고리즘
public boolean BruteForceStringMatch(int[] arr, int[] patternArr) {
int n = arr.length; // 전체 문자열 크기
int m = patternArr.length; // 문자열 패턴 크기
for (int i = 0; i < n - m; i++) { // 전체 문자열 크기에서 패턴 문자열을 뺀 만큼만 순회
int j = 0; // 패턴 문자열 크기 비교
while (j < m && patternArr[j] == arr[i + j]) {
// j가 m보다 작고 해당 위치에 패턴과 문자위치가 같은지 체크
j = j + 1; // 같으면 +1
}
if (j == m) { // 패턴 크기랑 탐색된 문자열 크기가 같으면
return true; // 포함 한걸로 인정
}
}
return false;
}
선택 정렬 알고리즘 [ 선택 정렬 알고리즘 ]
전체 배열을 검색해서 현재 요소랑 비교하고 컬렉션의 완전한 정렬까지 오름차순 또는 내림차순에 따라 교환하고 정렬하는 알고리즘
public int[] SelectionSort(int[] arr) {
// 주어진 배열을 Selection Sort로 오름차순 정렬합니다.
// 입력: 정렬 가능한 요소의 배열 A
// 출력: 오름차순으로 정렬된 배열
for (int i = 0; i < arr.length - 1; i++) {
// 배열의 0번째 인덱스부터 마지막인덱스까지 반복합니다.
// 현재 값 위치에 가장 작은 값을 넣을 것입니다.
int min = i;
// 현재 인덱스를 최소값의 인덱스를 나타내는 변수에 할당합니다.
for (int j = i + 1; j < arr.length; j++) {
// 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소과 비교하는 반복문을 구성합니다.
if (arr[j] < arr[min]) {
// j인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
min = j;
// j 인덱스를 최소를 나타내는 인덱스로 할당합니다.
}
}
// 반복문이 끝났을 때(모든 비교가 끝났을때)
// min에는 최소값의 인덱스가 들어있습니다.
// i값과 최소값을 바꿔서 할당합니다.
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
// 모든 반복문이 끝나면 정렬된 배열을 반환합니다.
return arr;
}