https://www.inflearn.com/course/알고리즘-강좌/dashboard 강좌 내용 공부
201009: 순환 (Recursion) 의 개념과 기본 예제 1
Recursion = 순환함수 = 재귀함수
void func(){
func();
}
: 자기 자신을 참조하는 함수.
public class code01{
public static void main(){
func();
}
void func(){
sysout("hello");
func();
}
}
: 무한루프
Recursion도 무한루프가 아닐 수 있다.
public class code02{
main(){
func(4);
}
}
func(int k){
if(k<=0){
return;
}
else{
sysout("hello");
func(n-1);
}
}
: 결과는 hello 4번 출력
※ [Base Case]
적어도 하나의 Recursion에 빠지지 않는 경우가 필요하다.
※ [Recursive Case]
Recursion을 반복하다 보면 결국 Base Case로 수렴해야 한다.
Code3{
main(){
int result = func(4);
sysout(result);
}
int func(int n){
: 0~n까지 합을 구하기
if(n<=0){
return 0;
: n=0이면 합이 0이다.
}
else{
return n + func(n-1);
: n이 0보다 크다면 0에서 n까지 합은
0에서 n-1까지의 합에 n을 더한것
}
}
}
:
4 + func(3)
: 10 = 1~n까지의 합 3 + func(2)
: 6 2 + func(1)
: 3 1 + func(0)
: 1 0
factorial : n!
0! = 1
n! = n * (n-1)! n>0
public static int factorial (int n){
if(n==0){
return 1;
}else{
return n * factorial(n-1);
}
}
X^0 = 1
X^n = X * X^n-1 if) n>0
※ X는 음이 아닌 정수
public static double power (double x, int n){
if(n==0){
return 1;
}
else{
return X * power(X, n-1);
}
}
fibonacci number
f0 = 0
f1 = 1
fn = fn-1 + fn-2 n<1
public int fibonacci(int n){
if(n<2){
return n;
}
else{
return fibonacci(n-1) + fn(n-2);
}
}
Euclid Method : 최대공약수
public static double gcd(int m, int n){
if(m<n){
int tmp = m;
m = n;
n = tmp;
: m이 더 크도록 swap }
if(m%n == 0){
return n;
: 나누어 떨어지면 n
}
else{
return gcd(n, m%n);
}
}
: m이 n의 배수 = n이 최대공약수
아니면 gcd(m,n) = gcd(n, m%n);
간단하게 표기 가능
gcd(p,q)
p if) q=0
gcd(q, p%q) otherwise
public static int gcd(int p, int q){
if(q==0){
return p;
}
else{
return gcd(q, p%q);
}
}
201011: Recursive Thinking (순환적으로 사고하기)
수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.
문자열의 길이 계산
: 문자열의 길이는 문자열의 길이 +1 이다.
public static int length(String str){
if(str.equals("")){
return 0;
}
else{
return 1+length(str.substring(1));
}
// 원래 내가 받은 str 에서 1을 뺀 것 + 1을 더한 것을 리턴
}
str이 ace일 경우에
return 1 + length("ce");
return 1 + length("e");
return 1 + length("");
이므로 1 + 1 + 1 = 3 이 return된다.
문자열 프린트의 경우에도 str.charAt(0) 사용해서 print 가능하다.
: 굳이 순환을 써 보는 것이다.
문자열을 뒤집어서 프린트 하는 경우에는 str.substring(1) 을 사용해서 print 한다.
: 문자열 프린트의 reverse이다.
2진수 변환해서 출력
public void printInBinary(int n){
if(n<2){
print(n); //0과 1은 그냥 출력
}
else{
printInBinary(n/2); // n을 2로 나눈 몫을 순환
print(n%2); // n을 2로 나눈 나머지를 인쇄
}
}
: 음이 아닌 정수 n을 이진수로 변환하여 인쇄한다.
n을 2로 나눈 몫을 먼저 2진수로 변환하여 인쇄한 후
n을 2로 나눈 나머지를 인쇄한다.
배열의 합 구하기
: data[0]에서 data[n-1]까지의 합을 구하여 반환한다.
int sum(int n, int [] data){
if(n<=0){
return 0;
}
else{
return sum(n-1, data) + data[n-1];
}
}
데이터파일로부터 n개의 정수 읽어오기
: Scanner in이 참조하는 파일로부터 n개의 정수를 입력받아
배열 data의 data[0] ... data[n-1]에 저장한다.
모든 순환함수는 반복문(iteration)으로 변경 가능
그 역도 성립함. = 모든 반복문은 recursion으로 표현 가능함
순환 함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함
하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 엑티베이션 프레임 생성 등)
201011: Designing Recursion (순환 알고리즘의 설계)
어떤 방식으로 순환 알고리즘 설계를 하는지
- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
- 모든 case는 결국 base case로 수렴해야 함
: 안 그러면 무한 루프
암시적 (implicit) 매개변수를
명시적 (explicit) 매개변수로 바꾸어라.
: 명시적으로 초기값까지 지정하는 것이 중요하다 (결론)
순차 탐색
int search (int [] data, int n, int target){
for(int i = 0; i< n; i++){
if(data [i] == target){
return i;
}
return -1;
}
}
: data[0] 부터 data[n-1] 까지 target을 검색하는 것인데,
검색 구간의 시작 인덱스가 명시적으로 지정이 안 되어 있어서 0부터 시작을 하는 것이므로
암시적 매개변수이다.
int search(int [] data, int begin, int end, int target){
if(begin > end){
return -1;
}
else if(target == items[begin]){
return begin;
} else{
return search(data, begin+1, end, target);
}
}
: 이런 식으로 교체하면 begin 과 end 사이에서 target을 검색하므로
검색 구간 시작점을 explicit(명시적)으로 지정한다.
이 함수를 search(data, 0, n-1, target)으로 호출시에는
반복문으로 짠 위 소스와 완전 동일한 일을 한다.
int search(int [] data, int begin, int end, int target){
if(begin > end){
return -1;
}
else{
int middle = (begin + end)/2;
if(data[middle] == target){
return middle;
}
int index = search(data, begin, middle-1, target);
if(index != -1){
return index;
}else{
return search(data, middle+1, end, target);
}
}
}
: 다른 버전은 이런 식으로 middle을 만들어서 중간값을 target으로 먼저 찾아보고 나서
아니면 뒤쪽에서 찾고 앞쪽에서 찾고 하는 방식으로 검색 하는 방식도 있음
이거 binary search 같이 찾는 건 아님.
매개변수의 명시화 : 최대값 찾기
int findMax(int [] data, int begin, int end){
if(begin==end){
return data[begin];
}else{
return Math.max(data[begin], findMax(data, begin+1, end));
}
}
: begin이 end보다 작거나 같을 때로 가정하고,
Math.max 함수 사용해서 최대값을 찾는다.
이거는 data 개수 0개일 경우에는 못 돌림.
앞 예제와 같이 middle 양식 사용해서
1) begin, middle 값과
2) middle, end 값 사용해서 돌리는 방식도 있음.
Binary search의 경우에는 데이터가 크기순으로 정렬된 상태에서 사용 가능.
이것도 예제는 middle 사용하는 개념으로 작성한다.
이건 크기순으로 정렬되었으니, 작으면/크면 조건으로
1) 앞 , 중간-1 값과
2) 중간+1 , 끝 값으로 순환 시킨다.
201011: Maze (미로찾기)
n x n 크기의 배열 형태의 미로를 지정하여 n-1, n-1 위치의 출구까지 이동 할 수 있는 코드를 짜야 한다.
wall이 있고 (이동 불가)
pathway (이동 가능) 가 있다.
현재 위치에서 출구까지 가는 경로가 있으려면
1) 현재 위치가 출구이거나, 혹은
2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나
: 현재 위치에서 이웃한 셀들 중 하나에서 출구까지 가는 경로를 찾는다.
Decision Problem (답이 yes or no 인 문제)
boolean findpath(x,y){
if(x, y) is the exit
return true;
else
for each neighbouring cell (x', y') or x,y) do
if(x', y') is on the pathway
if findpath(x', y')
return true;
return false;
}
: 현재 위치가 출구면 끝
아니면 인접한 4개의 cell 중 출구까지 가는 게 있으면, (4개 아닐 수 있음)
각각에 대해서 만약에 인접한 cell이 pathway면, true를 리턴한다.
아니면 false를 리턴하긴 하는데,
기본적으로 고려해야 할 부분이 [무한루프]인데,
이거는 인접한 셀이 다시 원래인 x, y로 돌아갈 수 있기 때문이다.
x', y'의 인접한 셀은 x, y이기 때문이다.
boolean findpath(x,y){
if(x, y) is the exit
return true;
else
for each neighbouring cell (x', y') or x,y) do
if(x', y') is on the pathway and not visited
if findpath(x', y')
return true;
return false;
}
: 이렇게 방문하지 않았던 곳이라는 전제 조건을 추가해야 한다.
boolean findpath(x,y)
if(x,y) is either on the wall or a visited cell
return false;
else if(x,y) is the exit
return true;
else
mark (x,y) as a visited cell;
for each neighbouring cell (x', y') of (x,y) do
if findpath(x', y')
return true;
return false;
: 이렇게 나중에 방문된 셀인지 뭔지 체크하지 않고,
recursion을 호출한 다음에 안에 들어와서 체크하는 방식도 있음
public class Maze{
private static int N=8;
private static int [][] maze = {
{0,0,0,0,0,0,0,1}, {0,1,1,0,1,1,0,1},
{0,0,0,1,0,0,0,1},
{0,1,0,0,1,1,0,0},
{0,1,1,1,0,0,1,1},
{0,1,0,0,0,1,0,1},
{0,0,0,1,0,0,0,1},
{0,1,1,1,0,1,0,0}
}
private static final int PATHWAY_COLOUR = 0; //white
private static final int WALL_COLOUR = 1; //blue
private static final int BLOCKED_COLOUR = 2; //red private static final int PATH_COLOUR= 3; //green
}
: PATH_COLOUR: visited이며, 아직 출구로 가는 경로가 될 가능성이 있는 cell
BLOCKED_COLOUR: visited이며, 출구까지의 경로상에 있지 않음이 밝혀진 cell
: 일단 녹색으로 칠하고, 아닌게 판명나면 빨간색으로 칠한다.
public static boolean findMazePath(int x, int y){
if(x<0 || y<0 || x>=N || y>=N){
//미로의 범위가 아닐 경우
return false;
}else if(maze[x][y] != PATHWAY_COLOUR){
return false;
}else if(x==N-1 && y==N-1){
maze[x][y] = PATH_COLOUR;
return true;
}else{
maze[x][y] = PATH_COLOUR;
if(findMazePath(x-1, y) || findMazePath(x, y+1)
|| findMazePath(x+1, y) || findMazePath(x, y-1)){
return true;
}
maze[x][y] = BLOCKED_COLOUR;
return false;
}
}
: 처음에는 0,0을 호출한다.
201011: Counting cells in a Blob
바이너리 이미지
각 픽셀은 백그라운드 픽셀이거나 이미지 픽셀
서로 연결된 이미지 픽셀들의 집합을 blob이라고 부름
상하좌우 및 대각방향으로도 연결된 것으로 간주
이런 경우에는 blob 크기가 4개 (연결된 것 3개와 size 1짜리 1개)
입력:
N*N 크기의 2차원 그리드
하나의 좌표(x,y)
출력:
픽셀(x,y)가 포함된 blob의 크기,
(x,y)가 어떤 blob에도 속하지 않는 경우에는 0
현재 픽셀이 속한 blob의 크기를 카운트하려면
현재 픽셀이 image color 가 아니라면
0을 반환한다.
현재 픽셀이 image color 라면
먼저 픽셀을 카운트한다 (count=1);
현재 픽셀이 중복 카운트 되지 않도록 다른 색을 칠한다.
현재 픽셀에 이웃한 모든 픽셀들에 대해서 (대각 방향까지 8개)
그 픽셀이 속한 blob의 크기를 카운트하여 카운터에 더해준다.
카운터를 반환한다.
이것을 수도 코드로 변경하면
Algorithm for countCells(x,y)
if the pixel (x,y) is outside the grid
the result is 0;
else if pixel (x,y) is not an image pixel or already counted
the result is 0;
else
set the color of the pixel (x,y) to a red color;
the result is 1 plus the number of cells
in each piece of the blob that includes a nearest neighbor;
private static int BACKGROUND_COLOR = 0;
private static int IMAGE_COLOR = 1;
private static int ALREADY_COUNTED = 2;
public int countCells(int x, int y){
if(x<0 || x>=N || y<0 || y>=N)
return 0;
else if(grid[x][y] != IMAGE_COLOR)
//이미지 픽셀이 아니거나 이미 세졌거나
return 0;
else{
grid[x][y] = ALREADY_COUNTED;
return 1
+ countCells(x-1, y+1) + countCells(x, y+1)
+ countCells(x+1, y+1)
+ countCells(x-1, y)
+ countCells(x+1, y)
+ countCells(x-1, y-1) + countCells(x, y-1)
+ countCells(x+1, y-1)
}
}
201011: N-Queens
N x N 크기의 체스판 중 N개의 말을 어떤 열/행/대각선 내에 같은 말이 안 놓여 있도록 배치 하는 문제
첫 번째 말의 위치 : N개
두 번째 말의 위치 : N개
N 번째 말의 위치 : N개
= N^N
상태공간트리 : 찾는 해를 포함하는 트리.
해가 존재할 경우 반드시 이 트리의 어떤 한 노드에 해당함.
따라서 이 트리를 체계적으로 탐색하면 해를 구할 수 있음.
이유 : 전체 경우수를 다 적어주기 때문에
그러나 사실 상대공간 트리의 모든 트리를 탐색해야 하는 것은 아니고
infeasible (실행 불가능) 한 것을 빼야 한다.
이거를 되추적 기법(백트랙킹(backtracking) 방식으로 탐색한 건데
: 상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘이다.
return-type queens(arguments){
if non-promising //할 곳 없으면
report failure and return; // 끝
else if success //찾고 있는 곳이면
report answer and return; // 표기하고 종료
else
visit children recursively // 꽝도 아니고 찾는 것도 아니면 다시 child 확인
}
: 매개변수는 내가 현재 트리의 어떤 노드에 있는지를 지정해야 한다.
arguments는 [현재 내가 트리의 어떤 노드에 있는지 지정해야 한다.]
201011: 멱집합(powerset)
임의의 집합 data의 모든 부분집합을 출력하라.
n -> 2^n
data = {a,b,c,d}
2^4 = 16 개
Recursion을 이용해서 해결하는 방법
: {a,b,c,d,e,f} 의 모든 부분집합을 나열하려면,
- a를 제외한 {b,c,d,e,f}의 모든 부분집합들을 나열하고,
- {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열한다.
: a를 포함하지 않는 것들과, = {b...f}까지로 이루어진 것 = 2^5
a를 포함하는 것들로 이루어져 있는 것 = {b...f}까지를 다 구한 뒤 {a}를 추가 = 2^5
따라서 2^5 + 2^5 = 2^6
그러므로
: {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면,
- {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고,
- {c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열한다.
: b를 포함하지 않는 것들과, = {c...f}까지로 이루어진 것
b를 포함하는 것들로 이루어져 있는 것 = {c...f}까지를 다 구한 뒤 {a,b}를 추가
그러므로
: {c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면,
- {d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고,
- {c,d,e,f}의 모든 부분집합에 {a,c}를 추가한 집합들을 나열한다.
: c를 포함하지 않는 것들과, = {d...f}까지로 이루어진 것
c를 포함하는 것들로 이루어져 있는 것 = {d...f}까지를 다 구한 뒤 {a,c}를 추가
: 내포하고 있는 Recursion은 어떤 집합에 모든 부분집합을 구하려면,
원소 하나를 제거한 다른 집합의 부분집합을 구하는 일을 하면
원래 집합의 교집합을 구할 수 있다.
수도 코드로 변경 시
PowerSet(S) // S의 멱집합 출력
if S is an empty set
print nothing; //공집합일 경우에는 출력 하지 않는다.
else
let t be the first element of S;
find all subsets of S-{t} by calling PowerSet(S-{t});
//PowerSet을 다시 Recursion으로 호출해서
원소 하나를 제거한 다른 집합의 부분집합을 구하게 함
print the subsets;
print the subsets with adding t;
: 이렇게 하려면 PowerSet 함수는 여러 개의 집합들을 return 해야 하는데,
실질적으로 사용 하기가 어렵다.
또한 PowerSet이 recursion이라, 멱집합을 리턴해 줘야 하기 때문에
PowerSet(S)
if S is an empty set
print nothing;
else
let t be the first element of S;
find all subsets of S-{t} by calling PowerSet(S-{t});
return all of them;
: 위와 같이 변경해야 하지만 멱집합 출력이 목적이므로 메모리 저장이 필요한 이러한 방식은 좋지 않다.
또한 모든 집합들에 t를 추가해서 출력해주는 일을 할 수 없는 방식의 수도 코드이다.
수정된 수도 코드 - S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력하라
PowerSet(P, S)
if S is an empty set
print P;
else
let t be the first element of S; //어떠한 원소 t
PowerSet(P, S-{t}); //t를 제외한 집합의 모든 부분집합을 구한다.
PowerSet(P∪{t}, S-{t}); // ∪는 합집합 표시임(폰트 문제) , t를 포함
: recursion 함수가 두 개의 집합을 매개변수로 받도록 설계해야 한다는 의미이다.
두 번째 집합의 모든 부분집합들에 첫번째 집합을 합집합하여 출력한다.
: 맨 처음 호출 시에는 PowerSet(공집합, data); 로 설정한다.
: {b,c,d,e,f}의 모든 부분집합에 {a}를 추가한 집합들을 나열하려면,
- {c,d,e,f}의 모든 부분집합들에 {a}를 추가한 집합들을 나열하고,
- {c,d,e,f}의 모든 부분집합에 {a,b}를 추가한 집합들을 나열한다.
집합 S : k번째부터 마지막 원소까지 연속된 원소들이다.
집합 P : 처음부터 k-1번째 원소들 중 일부이다. (S에 속하지 않는다.)
: Recursion 돌리면 S랑 P에 매칭하는 구조가 항상 같다.
P : 0 부터 k-1까지 중 일부
S : k 부터 n-1까지
include 라는 boolean 배열을 하나 추가해서 해당되는 사항만 true로 설정
private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
private static int n = data.length;
private static boolean [] include = new boolean [n];
public static void powerSet(int k){
//전체 집합에서 k번째 원소부터 나머지 : S
//앞쪽에서 k-1번째까지 원소 중 배열 include의 값이 true면 : P
if(k==n){
for(int i =0; i<n; i++){
if(include[i]){
//공집합이면 P만 출력한다.
print(data[i] + " ");
}
sysout();
return;
}
}
include[k] = false;
powerSet(k+1);
//data[k] (집합 S의 첫번째 원소) 를 포함하지 않는 부분집합
//k+1부터 n-1까지가 S로 변경되어 powerSet 함수 실행
include[k] = true;
powerSet(k+1);
//data[k] (집합 S의 첫번째 원소) 를 포함하는 부분집합}
: data[k],..., data[n-1]의 멱집합을 구한 후,
각각에 include[i] = true, i=0,...,k-1 인 원소를 추가하여 출력하라.
: 처음 이 함수를 호출할 때는 powerset(0)으로 호출한다.
즉 P는 공집합이고 S는 전체집합이다.
상태공간트리(state space tree)
원소가 {a,b,c} 일 때, 모든 역집합을 구하는 과정을 하나의 tree로 시각화하는 것
= 모든 부분집합 구하는 트리
include와 exclude가 바뀌어야 함 (잘못된 그림)
a - 포함 / 제외
b - 포함 / 제외
c - 포함 / 제외
2^3 = 8 가지 갈래가 있음
마지막 노드의 개수를 보면 모든 부분집합을 구할 수 있다.
: 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리
- 트리의 모든 노드들을 방문하면 해를 찾을 수 있다.
- 루트에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술한다.
※ 해가 여기서는 모든 부분 집합들이라고 보면 됨.
따라서 결과를 찾기 위해서는 모든 노드를 방문하는 일을 한다
private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'};
private static int n = data.length;
private static boolean [] include = new boolean [n];
//include와 k는 트리상에서 현재 나의 위치를 표현한다.
public static void powerSet(int k){
if(k==n){
//만약 내 위치가 리프노드일 시 출력 후 종료한다.
for(int i =0; i<n; i++){
if(include[i]){
print(data[i] + " ");
}
sysout();
return;
}
}
//리프노드가 아니고, 트리의 어디에 위치 할 때는,
include[k] = false;
powerSet(k+1);
//먼저 왼쪽으로 내려가서 (왼쪽의 모든 노드를 방문한다.) exclude를 했다가,
include[k] = true;
powerSet(k+1);
//이번에는 오른쪽으로 내려가서 (오른쪽의 모든 노드를 방문한다.) include를 한다.
}
: 이런 식으로 Recursion으로 구현 가능하다.
댓글
댓글 쓰기