간타 Dev

재귀함수
재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다.
반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하며 그 반대도 가능하다.
재귀함수를 작성할 때는 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때 까지 함수 호출 이후의
명령문이 수행되지 않는다는 사실과 종료조건이 꼭 포함되어야한다는 부분을 인지하고 작성하면
무한루프를 방지할 수 있다.

재귀함수 예제
public class PlusFunction {
public static void main(String[] args)  {
HelloWorld(5); // HelloWorld 출력 메서드 호출
}

// HelloWorld 출력 메서드 선언
public static void HelloWorld(int n)
{
// n이 0인 경우 return
if(n == 0)
return;

System.out.println("HelloWorld"); // HelloWorld 출력
HelloWorld(n-1); // 재귀함수 시작
}
}

n이 0이 될 때 메소드를 종료하고, 함수를 호출 할 때마다 n을 1씩 빼서 재귀함수를 종료함

브루트포스 알고리즘
- 모든 경우의 수를 완전 탐색으로 구하는 알고리즘이다.

브루트포스 알고리즘의 방법으론
for문을 이용한 탐색, 재귀를 이용한 탐색
DFS&BFS 탐색 등이 있다.

전체를 탐색하는 알고리즘인 브루트포스는 좋은 알고리즘 방식이 아니다.
예를들어 1000억개의 자료를 검색할때에는 1000억개를 다 찾아봐야하기때문이다.

때문에 실제 알고리즘문제를 풀어나갈때에는 그 문제가 브루트포스로 가능한지 확인 후에 다른 알고리즘을 적용하여 해결해나아가야한다.

DFS & BFS 탐색 

DFS(깊이우선탐색)
-자기 자신을 호출하는 순환 알고리즘의 형태를 지닙니다. (재귀 or 스택)
- 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.
(검사하지 않을 경우 무한루프 빠질 위험 증가)
- 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사
- 모든 노드를 방문하고자 할 때, 이 방법을 사용
- BFS에 비해서 속도는 느리지만 더 간단하게 사용 가능.

BFS(너비우선탐색)
-BFS는 재귀적으로 동작하지 않습니다.
-이 알고리즘 또한, 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다
(검사하지 않을 경우 무한루프에 빠질 위험 증가 )
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
DFS의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
BFS의 경우 - A와 가까운 관계부터 탐색한다.

정수론
- 각종 수의 성질을 대상으로 하는 수학의 한 분야

백준알고리즘을 푸는 도중, 정수론과 조합론에 관한 내용이 있어 찾아보았다.
프로그래밍에서 정수론은
1. 유클리드 호제법(최대공약수, 최소공배수)
2. 에라토스테네스의 체를 사용한 소수 찾기 및 소인수 분해
3. 거듭제곱과 모듈러 연산 등이 있다.
사실 더 있지만.. 알고리즘을 다 풀어보고 시간이 남지않는 이상은 더 찾아보지는 않을 듯 하다.

시간복잡도, 공간복잡도

시간복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데
연산들이 몇 번 이루어지는지를 숫자로 표기 한다. 
여기서 연산이란 산술, 대입, 비교, 이동을 말한다.
연산의 실행 횟수는 보편적으로 그 값이 변하지 않는 상수가 아니라 입력한 데이터의 개수를 나타내는 n에따라 변하게 된다. 연산의 개수를 입력한 데이터의 개수 n의 함수로 나타낸것을 시간복잡도 라고 말하며, 수식으로 T(n)이라고 표기한다.

공간복잡도는 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다.
총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며 수식으로는 S(P) = c + Sp(n)으로 표기.

여기서 고정 공간은 입력과 출력의 횟소누 크기에 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.
가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구가 되는 추가 공간을 말한다.
(동적으로 필요한 공간)

시간복잡도는 "얼마나 빠르게 실행되느냐" 이고,
공간복잡도는 "얼마나 많은 자원이 필요한가?" 이다.
좋은 알고리즘이란 시간과 자원의사용의 양이 적어야 하지만,
시간과 공간은 반비례적인 경향이 있기 때문에, 알고리즘의 척도는 시간 복잡도를 위주로 판단한다.

정렬 정리

1. 버블정렬
버블정렬은 서로 인접해있는 요소 간의 대소 비교를 통하여 정렬한다.
버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다.
시간복잡도가 최고, 평균 최악 모두 O(N^2)이며 공간복잡도는 하나의 배열만 사용하므로 O(n)을 가진다.
동작방식은 인접한 두 요소간의 대소 비교를 진행한다.

2. 삽입정렬

삽입 정렬은 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다.
동작 방식은 두 번째 index부터 시작한다. 그 이유는 첫 번째 index는 비교할 원소가 없기 때문이다.
알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 왼쪽 맨 index까지 탐색하지 않아도 된다는 장점이 있다. 모두 정렬되어 있는 Optimal한 경우 
모든 원소가 한 번씩만 비교되므로 O(n)의 시간 복잡도를 가진다. 또한 공간 복잡도는, 하나의 배열에서 정렬이 이루어지므로 O(n)이다.

3. 선택 정렬

선택 정렬은 배열에서 최소값을 반복저으로 찾아 정렬하는 알고리즘이다.
시간복잡도는 최선,평균,최악 모두 O(N^2)에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다.
동작방식 3단계로 구성된다. 첫 번째는 주어진 배열에서 최소 값을 찾은 후, 최소값을 맨 앞에 값과 바꾼다. 바꿔준 값을 제외한 나머지 원소를 앞의 방벙으로 바꿔준다.

4. 퀵 정렬

퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다. 파이썬이나 자바 언어 자체에 내장되어 있는 알고리즘도 퀵 정렬을 기반으로 한다.

퀵 정렬에는 피봇이라는 개념이 사용된다. 피봇은 한마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다.
최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 첫번째 값이나 중앙 값을 선택한다.

5. 병합 정렬

병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.
퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다. 하지만 차이점은 퀵 정렬이 피봇 선택 이후 피봇 기준으로 대소를 비교하는 반면,
병합정렬은 배열을 원소가 하나만 남을때 까지 계속 이분할 한 다음, 대소 관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합한다.

6. 힙 정렬

힙을 알기전에 이진트리를 알아야하므로, 조금 정리해 보았다.

이진 트리란 컴퓨터 안에서 데이터를 표현할 때 데이터를 각 노드에 담은 뒤에 노드를 두 개씩 이어붙이는 구조를 말한다. 이때 트리 구조에 맞게 부모 노드에서 자식 노드로 가지가 뻗히는데,
이진 트리는 모든 노드의 자식노드가 2개 이하인 노드를 뜻한다.
완전 이진 트리는 데이터가 루트 노드부터 시작하여 자식 노드가 왼쪽 자식, 오른쪽 자식노드로 차근차근 뻗어가는 구조이다. 완전 이진 트리는 이진 트리의 노드가 중간에 비어있지 않고 빽빽히 가득 찬 구조를 말한다.

힙이란 트리 기반의 자료구조로서, 두 개의 노드를 가진 완전 이진 트리를 의미한다. 따라서 힙 정렬이란 완전 이진 트리를 기반으로 하는 정렬 알고리즘이다.
힙의 분류는 크게 최대 힙과 최소 힙 두 가지로 나뉜다. 최대 힙은 내림차순 정렬, 최소 힙은 오름차순 정렬에 사용한다.

최대힙의 경우 부모 노드가 항상 자식노드 보다 크다는 특징을 가진다. 반대로 최소힙의 경우 부모 노드가 항상 자식노드 보다 작다는 특징을 가진다. 이러한 힙에서 
오해할 수 있는 특징은 힙은 정렬된 구조가 아니다. 부모 자식 간의 대소 관계에서만 나타내며 좌우 관계는 나타내지 않기 때문이다. 예를 들어 최소 힙에서 대부분 
왼쪽 노드가 오른쪽 노드보다 작지만 4의 자식 노드인 7과 5는 왼쪽이 오른쪽보다 크다.

힙은 완전 이진 트리기 때문에 적절히 중간 레벨의 노드를 추출하면 중앙 값에 가까운 값을 근사치로 빠르게 추출할 수 있다는 장점을 갖고 있다. 때문에 힙은 배열에
순서대로 표현하기 적합하다. 또한 균형을 유지하려는 특징 때문에 힙은 우선순위 큐, 다익스트라, 힙 정렬, 프림 알고리즘에 사용된다. 

7. 셀 정렬
셀 정렬은 삽입 정렬의 단점을 보완하고자 도입되었다. 삽입 정렬은 주어진 정렬 상태가 역순으로 배열되어 있을수록 비교횟수가 늘어나고, 최선의 경우 O(N)이지만 최악의 경우 O(N^2)이므로 성능 차이가 크다.
셀 정렬은 이러한 시간복잡도를 평균적으로 낮추고자 도입된 알고리즘이다. 셀 정렬에 사용되는 핵심 개년은 interval(간격)이다. interval은 비교할 원소 간의 간격을 의미한다. 셀 정렬에서는 비교 횟수를 줄이기 위해 interval은 큰 값에서
낮은 값으로 낮춰간다. 동작 방식은 배열에서 interval만큼 떨어진 원소들을 부분집합으로 구성한 뒤 삽입 정렬을 진행하는 방식으로 진행된다.
초기 interval 값은 배열 전체 길이의 / 2 이며 한번 정렬 시, interval 값을 2로 계속 나누어 준다. 
만약 배열 length 가 8이라면, 첫번째 interval값은 4이고, 한번 정렬 시 2로 나누어 삽입정렬을 진행한다.

8. 기수 정렬
기수 정렬은 non-comparison 알고리즘으로 원소간의 대소 비교를 하지 않고 정려하는 알고리즘이다. 대신 기수 정렬은 정렬하고자 하는 수의 낮은 자리 수를 차례대로 확인하여 정렬하는 방식이다. 정렬을 위해 총 10개의 queue를 사용한다.
첫번째로, 1의 자리 수를 확인하여 각 원소의 1의 자리에 해당하는 queue에 쌓아준다.
두번째로, 10의 자리 수를 확인하여 각 원소의 10의 자리에 해당하는 queue에 쌓아준다.
n번째로, n의 자리수를 확인하여 각 원소의 n의 자리에 해당하는 queue에 쌓아주고,
이후 queue의 0~9를 순회하며 차례대로 가져온다. 

8. 카운팅 정렬
카운팅 정렬은 non-comparison sort 알고리즘에 해당하는 알고리즘으로 comparison sort에 해당하는 버블, 선택, 힙, 병합, 퀵, 삽입이 기껏해야 평균적으로 O(nlogn)이나 O(n^2)의 시간복잡도를 갖기에 이를 O(n) 수준으로 낮추고자 도입된 알고리즘이다.
카운팅 정렬의 동작은 이름 그대로 배열에 존재하는 원소 별 개수를 세어 정렬하는 방식이다.

1)배열의 존재하는 값의 각 원소의 개수를 세어줄 새로운 배열 count를 만든다.
count의 길이는 원소의 최대값까지를 인덱스로 사용할 수 있도록 원소의 최대값 + 1만큼으로 지정해준다 (0을 포함)
count[i]는 숫자 i가 배열에 몇개 존재하는지에 대한 정보를 담는다.
2) count배열의 원소를 누적합으로 갱신해준다. 이 작업은 arr에 담긴 원소를 바로 정렬된 위치로 삽입하기 위한 사전작업이다.
ex) [0, 1, 1, 2, 2, 3] -> [0 , 1, 2, 4, 6, 9]
3) arr의 길이와 같은 result 배열을 만들어준다. 해당 배열에는 arr의 원소를 정렬된 위치에 삽입할 것이다.
4) arr의 각 원소값을 count의 인덱스로 사용해 값을 가져온 후, 해당 값을 다시 result의 인덱스로 사용해 arr의 원소로 저장해준다.
5) 해당 작업을 마친 후 count[arr[i]]의 값을 1 줄여준다.

카운팅 정렬은 정렬하고자 하는 배열의 최대값이 매우 클 때 메모리를 매우 비효율적으로 쓰게된다는 단점이 있다.
배열에 존재하는 원소의 개수를 기록해주기 위해서 최대값은 count배열을 만들어야하는데
만약 정렬해야하는 배열이 [1, 123011] 라면 단 2개의 숫자를 정렬하기위하여 10만이 넘는 길이의 배열을 만들어줘야하는 일이 생긴다.
이는 메모리차원에서 매우 비효율적이고, 또 인덱스를 통하여 숫자를 세어주는 방식이기 때문에, 배열에 음수가 존재한다면 사용이 불가능하다.