[Do it! 알고리즘 코딩 테스트 자바] 그리디 알고리즘, 소수 구하기, 유클리드 호제법, 그래프 [13~18일차]

그리디 알고리즘

- 정의: 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정함

- 핵심 이론: 해 선택 -> 적절성 검사(제약 조건과 맞는지 확인) -> 해 검사 -> 최선의 선택지가 아닌 경우, 다시 해 선택!

 

소수 구하기

1. 에라토스테네츠의 체

- 핵심 이론: 구하고자 하는 소수의 범위만큼 1차원 배열 생성 -> 2부터 시작하며 현재 선택한 숫자가 지워지지 않는 숫자라면 해당 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 제거함(처음으로 선택한 숫자는 지우지 않음)

-> 2를 반복한 후 배열에 남은 수 모두 출력함

 

2. 오일러 피

- 핵심 이론: 구하고자 하는 오일러 피의 범위만큼 배열을 초기화함 -> 2부터 시작해서 현재 배열의 값과 인덱스가 같으면 현재 선택된 숫자의 배수에 해당하는 수를 배열 끝까지 탐색하며 P[i] = P[i] - P[i]/K를 수행(i는 K의 배수) -> 배열 끝까지 앞의 과정을 반복함

 

 

유클리드 호제법

- 정의: 두 수의 최대 공약수를 구하는 알고리즘

- 핵심 이론: 큰 수를 작은 수로 나누는 나머지 연산을 수행함 -> 앞 단계에서의 작은 수와 나머지 연산 결과값으로 나머지 연산을 또 수행함 -> 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택함

 

확장 유클리드 호제법

- 정의: 방정식의 해를 구함 -> ax + by = c

- 핵심이론: c % gcd(a, b) = 0인 경우에만 정수해를 가짐 -> c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가짐

 

그래프의 표현

- 에지 리스트: 에지를 중심으로 그래프를 표현함 -> 출발 노드와 도착 노드, (혹은 가중치도)를 저장하여 에지를 표현함

- 인접 행렬: 2차원 배열로 자료구조로 이용하여 그래프를 표현함

-> 에지 리스트와 달리 노드 중심으로 표현함(노드 5개 -> 5*5 인접 행렬로 표현)

- 인접 리스트: ArrayList로 그래프를 표현함 -> 노드 개수만큼 ArrayList를 선언함

 

유니온 파인드

- 정의: 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해서 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find 연산으로 구성되어 있는 알고리즘

- 핵심 이론: union 연산 = 각 노드가 속한 집합을 1개로 합치는 연산 / find 연산 = 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환