* Scanner와 BufferedReader 사용 방법

* BufferedReader 와 Scanner의 차이

이러한 차이점을 가지고, 속도가 중요한 Algorithm 문제 풀이 시에는 되도록 BufferedReader를 사용하는 것이 바람직하다.

* Dynamic Programming(동적 계획법)

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

큰 문제를 작은 문제로 나누는 방식은 Divide and Conquer(분할 정복) 방식과 비슷하지만 차이점이 있다.

분할 정복의 경우 결과가 한번만 사용되고, 분할하여 작은 문제를 푸는 것이 성능을 향상시키지만,

동적 계획법의 경우 결과가 여러번 사용되고, 결과를 재사용하여 성능을 향상시킨다.

DP의 핵심은 점화식을 어떻게 세우는지와 DP에 어떤 값을 메모이제이션 할 것인지를 정하는 것이다.

메모이제이션이란 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다.

* Dynamic Programing 문제를 푸는 방법

- Top-Down (재귀 사용)

큰 문제를 작은 문제로 나누어 결과값을 가지고 큰 문제를 푼다.

메모이제이션 작업을 필수로 진행해야 한다.

- Bottom-Up (For문 사용)

작은 문제를 풀어 결과값을 가지고 큰 문제를 푼다.

Dynamic Programing은 피보나치가 대표적인 예로 사용된다.

백준 1003 :: 피보나치 함수

* Binary Search(이분 탐색)

이분 탐색은 정렬되어 있는 배열에서 값을 어떤 값(x)을 찾을때 사용할 수 있는 알고리즘이다.

기본 방법은, 정렬되어 있는 left와 right를 지정하여 배열의 중간 값(mid)을 구한다.

mid와 x를 비교했을 때, x가 더 크다면 left 값을 mid+1로 설정한다. (mid값 보다 오른쪽 검색)

mid와 x를 비교했을 때, mid가 더 크다면 right 값을 mid-1로 설정한다. (mid값 보다 왼쪽 검색)

위 과정을 반복하여 만족하는 값을 찾는 탐색 방식이다.

* 시간 복잡도

처음부터 끝까지 원하는 값을 찾을 때까지 탐색을 계속하는 순차 탐색은 Worst Case일 때 O(n)이라는 Time Complexity를 보여준다. 

10만개의 데이터가 있다면 무려 10만번을 탐색해야 하는 것이다. 

그러나, Binary Search는 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, Worst Case일 때에도 탐색의 횟수가 log2n 이 되므로 10만개의 데이터가 있다고 하더라도 약 16번 정도로 탐색을 끝낼 수 있다. 

즉, 이분 탐색의 시간 복잡도는 O(logn)이다.

* 분할 정복(Divide and Conquer)

분할 정복이란 문제를 소문제로 변경하여 소문제를 해결하여 큰 문제를 해결하는 방식이다.

1. 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다.

2. 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.

3. 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을 구한다.

* 분할 정복의 특징

장점 : 큰 문제를 비교적 작은 문제로 변환하고, 재귀로 구현하기 때문에 코드가 비교적 간단한다.

단점 : 재귀를 사용하기 때문에 StackOverflow가 발생할 수 있다.

* 예시

백준 1629 :: 곱셈 풀이

* Bitmast(비트마스크)

정수의 이진수 표현을 자료 구조로 쓰는 기법

특징 : 0과 1을 사용하여 선택/미선택을 판별할 수 있음

장점 : 간결한 코드, 빠른 연산 속도, 적은 메모리 사용

단점 : 순서가 필요한 경우 or 선택/미선택으로 해결되지 않는 문제의 경우 사용 불가

* Bit 연산자

- AND 연산 (기호 : a & b ) : 둘 다 1인 경우에만 결과가 1이 된다.

  ex) 111 & 101 = 101

  ex) 101 & 100 = 100

- OR 연산 (기호 : a | b ) : 둘중에 하나만 값이 1 이면 결과는 1 이 된다.

  ex) 101 | 100 = 101

  ex) 011 | 100 = 111

- XOR 연산 (기호 : a ^ b ) : 둘이 같은 값 (11 or 00) 이면 0 이 되고, 둘이 다른 값 (10 or 01) 이면 1 이 된다.

  ex) 101 | 111 = 010

  ex) 1011 | 0100 = 1111

- NOT 연산 (기호 : ~a ) : 두개의 비트 값에 대한 연산이 아닌 단일 비트값에 대하여 적용하는 연산이다. 각 자릿수를 반대값으로 뒤집는다. 즉, 0 인경우 1로 바꾸고, 1 인 경우 0 으로 바꾼다.

  ex) ~(1011) = 0100

  ex) ~(0011) = 1100

- LEFT SHIFT 연산 (기호 : a << b ) : 값 a 의 모든 각 자릿수의 비트를 좌측으로 b 번 만큼 민다. (우측에는 b개의 0 이 붙는다)

  ex) 1 << 5 = 100000

  ex) 1011 << 2 = 101100

- RIGHT SHIFT 연산 (기호 : a >> b ) : 값 a 의 모든 각 자릿수의 비트를 우측으로 b 번 만큼 민다. (좌측에는 b개의 0 이 붙는다)

  ex) 1101101 >> 2 = 11011

  ex) 110010  >> 5 = 1

* 사용 방법

1의 경우 선택, 0의 경우 미선택이라고 정의했을 때, 8개중 2개를 확인하는 방법

(1 << 0) & 255 != 0    >> 11111111 & 00000001    >> 첫 번째 선택 여부 확인

(1 << 1) & 255 != 0    >> 11111111 & 00000010    >> 두 번째 선택 여부 확인

(1 << 2) & 255 != 0    >> 11111111 & 00000100    >> 세 번째 선택 여부 확인

와 같이 비트연산을 통해 선택 여부를 확인할 수 있다.

* BackTracking

왔던 길을 되추척하는 방법

BackTracking 과 DFS는 비슷하지만 다른 차이점이 있다.

DFS 의 경우 방문한 점을 다시 방문하지 않는다는 특징이 있지만,

BackTracking 의 경우는 방문한 점을 다시 방문할 수 있다.

>> DFS는 순서의 상관 없이 M개중에서 N개를 뽑을 때 사용

>> BackTracking은 M개 중에서 N개를 순서에 따라 뽑을 때 사용

* BackTracking 시간 복잡도 

BackTracking 의 시간 복잡도는 O(2^n) 이다.

N의 범위가 보통 26 이하인 경우 사용 가능하다.

* BackTracking 유의할 점

DFS와 다르게 방문한 점을 다시 방문할 수 있기 때문에, 방문 이후 boolean visied 값을 초기화작업 필수

* BackTracking 작동 방식

Ex) 4개의 선택지가 있고, 선택시 1, 미선택시 0이라고 가정할 때, 작동 순서는 다음과 같다.

마지막 선택지의 경우 이미 다녀온 경우에도 불구하고 앞에 선택지가 변경되면 마지막 선택지를 다시 방문해야 한다.

BackTracking 의 경우 위와 같은 방식으로 진행된다.

이를 Tree 구조로 나타내면 다음과 같다.

* 너비 우선 탐색(BFS, Breadth-First Search)

• 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
• Queue로 구현
• 간선에 가중치가 없는 그래프에서는 방문하는 depth가 최단거리가 된다
• 주로 격자판, 최단거리 구할 때 사용
• while (!q.isEmpty()) -> if (!visited[q.poll()]) -> q.add 순서의 메소드 진행

* 깊이 우선 탐색(DFS, Depth-First Search)

• 재귀로 구현(코드가 간단)
• 자식 노드의 수를 파악하기 편리
• 주로 Tree에서 사용
• dfs 재귀함수에 탈출조건과 재귀내용 작성

* 주요개념

ArrayList의 배열로 구현이 필요

정점의 개수(N)만큼 ArrayList 배열을 만들고, M개의 간선을 N번째 index에 추가

* 소스 코드(백준 1260번 DFS와 BFS)

시간복잡도 -> N범위에 따라서 다르다.

O(nlogN) = 10만~50만 

O(n^2) = 0~5천 

1억에 1초로 생각하면 되지만, 정확한 값은 아니다.

System.out.print    >> 여러번 출력시 오래 걸림

-> 이를 방지하기 위해 StringBuilder 사용

ex)  sb.append(arr[i]).append("\n");

* 참고 라이브러리

Arrays.sort = O(n*logN)     이므로 자주 사용해도 괜찮음

Arrays.fill(채울 1차원배열, 채울 값)