에라토스테네스의 체 - 소수구하기 // 해당 수를 제외하고 배수를 모두 지운다
아나그램 - 같은 단어로 배열만 바꾼것 [해시 + 슬라이딩윈도우 ]
팰린드롬 - 앞으로해도 뒤로해도 같은 단어 [ 문자열(StringBuilder.reverse) + replaceAll ]
최대매출 - [ SlidingWindow ] 창문 형태로 밀어내기 창문의 첫번째 값을 빼고 마지막값을 더한다 반복
배열 합치기, 공통원소 구하기 - [ twopointer ] p1,p2 혹은 lt,rt로 두가지 포인트를 잡아서 진행한다.
후위식연산 - 스택으로 넣어서 진행 먼저들어간 숫자 lt, 나중에 들어간숫자 rt로 연산
피보나치수열 - [ Array ] (i-1) + i 값은 i+2 값과 일치한다.
K번째큰수 - 중복제거가 필요할땐 HashMap이 아닌 TreeSet을 사용한다.
스택문제 - 괄호 연산 등 리포
큐문제 - 라우터문제 피포
선택정렬 - 첫번째수를 반복문으로 다음 수들과 비교하면서 제일 작은수를 첫번째 인덱스에 넣음. -> 한바퀴 돌았을때 제일 작은수가 맨앞 인덱스로 이동
버블정렬 - 첫번째수와 바로 다음수를 비교하여 큰수를 뒤로 밀음 -> 한바퀴 돌았을때 제일 큰수가 맨뒤 인덱스로 이동
삽입정렬 - i가 0이아닌 1부터 시작하며 i번째수를 tmp에 넣고 i보다 작은 인덱스들에 있는 수와 비교하여 작으면 i번째수를 i-1번째로 이동하고 tmp를 i번째에 넣음
이분탐색 - 반복문이 시간초과할때 대체할 수 있으며, 0부터 N까지 반복하는게 아니며, lt,rt,mid를 설정하여 mid값과 비교하여 크거나 작음에따라 lt,rt의 범위를 이동시켜 절반씩 줄여나간다.
재귀함수 - 본인을 호출하는 함수이며, 메서드 첫부분에 if문을 만들어서 끝나는 조건을 넣고 else일때 재귀 로직을 타게한다.
트리 - 이진트리 유형.
그래프(DFS , BFS) - 깊이 탐색 / 넓이 탐색이며, 깊이탐색은 전위,중위,후위탐색을 기억하고 넓이탐색은 레벨을 기억할것. ex)최단거리
==========================================================================================================================================================================================
그리디알고리즘 - 단순히 가장 좋은것을 고름 / 최적의 해는 보장하지 못하는 경우가 많기때문에, 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야한다.
거스름돈 / 1이 될때 등의 문제가 있음.
구현 - 요구사항대로 풀이를 생각하여 소스코드로 옮기는 문제를 뜻한다. 대체적으로 알고리즘은 간단한테 코드가 지나치게 길다거나, 문자열 스플릿이나 소수점자리 관련 조건들이 있다.
적절한 라이브러리를 찾아야한다.
시뮬레이션 및 완전탐색 문제가 있으며, 여기서는 2차원 배열에 방향벡터가 자주 활용된다.
스택 - 스택은 마지막에 넣은값이 먼저 나온다.
큐 - 큐는 처음에 넣은값이 먼저 나온다.
재귀함수(Recursive Function) - DFS 구현시에 필요하며, 자기 자신 호출하는 함수를 뜻한다, 사용시에는 if절에 종료 조건을 작성하고 매개변수를 바꿔가며 본인을 계속하여 호출한다.
팩토리얼 / 유클리드 호제법(최대공약수) / 모든 재귀함수는 반복문으로 구현가능하다. - 상황에따라 유리하거나 불리할 수 있다.
그래프(DFS) - 깊이 우선탐색이라고 부르며, 스택 혹은 재귀함수를 이용한다.
1. 시작 노드를 스택에 넣고 방문처리한다.
2. 스택의 최상단에 방문하지 않은 인접한 노드가 있으면 그 노드를 스택에 넣고 방문 처리한다, 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더이상 수행할 수 없을때까지 반복한다.
그래프(BFS) - 너비 우선탐색이라고 부르며, 가까운 노드부터 우선적으로 탐색하는 알고리즘이다, 큐를 이용한다.
1. 시작 노드를 큐에 넣고 방문처리한다.
2. 큐에서 노드를 꺼낸뒤 해당 노드의 인접노드중에서 방문하지 않은 노드를 모두 큐에 넣고 방문처리한다.
3. 더이상 수행할 수 없을때까지 반복한다.
정렬 -
1. 선택정렬 - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨앞에 있는 데이터와 바꾸는것 을 반복한다.
동작원리 - 전체 데이터중 제일 작은 데이터를 맨앞의 데이터와 바꾸어 정렬해준다.
- 정렬되지않은 남은 데이터중 제일 작은 데이터를 두번째 데이터와 바꾸어준다.
- 해당 과정을 반복한다.
[N2]
// 선택정렬
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 0; i < n; i++) {
int idx = i;
for (int j = i + 1; j < n; j++) {
if (arr[idx] > arr[j]) {
idx = j;
}
}
int tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
}
for (int i = 0; i < n; i++) {
System.out.println(arr[i] + " ");
}
}
2. 삽입정렬
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
- 선택정렬보다 효율적이다.
동작원리 - 첫번째 데이터는 정렬이 되어있다고 판단하고, 두번째 데이터가 첫번째 데이터의 왼쪽으로 들어갈지 오른쪽으로 들어갈지 판단한다.
- 그다음 데이터도 앞의 데이터들과 하나씩 비교하여 왼쪽으로 갈지 오른쪽으로 갈지 판단한다.
[N2]
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j-1]) {
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
else break;
}
}
for (int i = 0; i < n; i++) {
System.out.println(arr[i] + " ");
}
}
3. 퀵 정렬
- 기준 데이터를 설정하고 그 기준보다 큰데이터와 작은데이터의 위치를 바꾸는 방법이다.
- 가장 많이 사용되는 정렬알고리즘이며, 병합정렬과 더불어 정렬라이브러리의 근간이 된다.
- 가장 기본적인 퀵정렬은 첫번째 데이터를 피벗으로 정한다.
동작원리
- 첫번째 데이터를 피벗으로 정한뒤 왼쪽에서부터 피벗보다 큰 데이터를 선택하고,
오른쪽에서부터 피벗보다 작은데이터를 선택하여 두 데이터의 위치를 서로 변경한다.
- 위의 과정을 두개의 포인터가 교차되기전까지 위의 과정을 반복하며, 위치가 엇갈릴경우 피벗과 '작은데이터'의 위치를 변경한다.
평균 - [NlogN] 한쪽으로 원소가 편향된경우에는 최악의 경우 [N2]이 될수도있다.
4. 계수 정렬
- 특정한 조건이 부합할때만 사용할수 있으나, 매우빠른 정렬알고리즘 중 하나이다.
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 사용가능하다.
- 데이터의 개수 N , 데이터의 최대값 K 일때 최악의 경우에도 수행시간 [O(N+K)]를 보장한다.
동작원리
- 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.
- 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
- 각 원소의 카운트를 구한뒤에 리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력한다
이진탐색 (binarySearch)
정렬되어 있는 리스트에서 탐색범위를 절반씩 줄여가며 데이터를 탐색하는 방법
시작점,끝점,중간점을 이용하여 탐색범위를 설정한다
동작원리
- 정렬된 리스트에 시작점[lt] , 끝점[rt]를 지정하고 rt의 절반값[소수점이라면 버림수행]에 mid를 설정하고
찾으려는 값보다 mid가 크면 끝점을 mid-1로 줄이고 mid가 작으면 시작점을 mid+1로 늘린다, 해당 작업을 반복한다.
[logN]
파라메트릭 서치 (Parametric Search)
최적화문제를 결정문제로 바꾸어서 해결하는 기법이다.[예/아니오]
파라메트릭 서치 문제는 이진탐색을 이용하여 해결할 수 있다. [참고 떡볶이 떡 문제]
다이나믹 프로그래밍 [DP]
- 탑다운과 바텀업 방식으로 구성된다.
- 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상시키는 방법이다.
- 이미 계산된 결과[작은 문제]는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록한다.
[예를들어 5팩토리얼계산후 6팩토리얼을 계산한다면 전부 재귀를 돌리는게 아닌 메모리에서 5팩토리얼 값을 가져와서 추가로 한번만 더 연산해준다.]
동적계획법이라고도 불린다.
조건-
1. 최적부분구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌수 있어야한다.
2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결한다.
하향식[탑다운 방식](재귀함수이용)
- 메모이제이션(Memoization) 한번 계산한 결과를 메모리 공간에 저장하는 기법이다, 값을 기록해놓는다는 점에서 캐싱이라고도 한다.
전형적인 형태는 상향식[바텀업 방식]이다.
- 결과저장용 리스트는 보통 DP테이블이라고 부른다.
다이나믹 프로그래밍과 분할 정복의 차이
- 분할정복의 예시로는 퀵정렬을 들 수 있는데, 퀵정렬의 경우 피벗이 정렬된 후에는 그 피벗을 다시 처리한다던가 호출하지않는다.
다이나믹프로그래밍 문제에 접근하려면, 먼저 그리디,구현,완전탐색등으로 문제가 해결이 가능한지 판단하고 불가하다면, 재귀함수등의 방법으로 프로그램을 작성한뒤에 개선하는 방법이 있다.
'알고리즘' 카테고리의 다른 글
| 자바에서 배열 Reverse 하는 2가지 방법 (1) | 2023.11.14 |
|---|
