재귀, 브루트포스, BFS, DFS

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

재귀함수 예제
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. 거듭제곱과 모듈러 연산 등이 있다.
사실 더 있지만.. 알고리즘을 다 풀어보고 시간이 남지않는 이상은 더 찾아보지는 않을 듯 하다.