hue9010 Reading time ~1 minute

인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

순환 알고리즘의 설계

무한 루프를 피하기 위해서는

  • 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.

  • 모든 case는 결국 base case로 수렴해야 한다.

가능하면 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다.

int search(int[] data, int n, int target){
  for(int i=0; i<n; i++){
    if(data[i] == target){
      return i;
    }
  }
  return -1;
}

순차 탐색: Recursion 버전

이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.

int search(int[] data, int begin, int end, int target){
  if(begin>end){
    return -1;
  } else if(target == data[begin]){
    return begin;
  } else{
    return search(data, begin+1, end, target);
  }
}

이 함수를 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);
    }
  }
}

최대값 찾기: 매개변수의 명시화

이 함수의 미션은 data[begin]에서 data[end] 사이에서 최대값을 찾아 반환한다. begin <= end라고 가정한다.

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));
  }
}

최대값 찾기: 다른 버전

int findMax(int[] data, int begin, int end){
  if(begin==end){
    return data[begin];
  } else{
    int middle = (begin + end)/2;
    int max1 = findMax(data, begin, middle);
    int max2 = findMax(data, middle+1, end);
    return Math.max(max1, max2);
  }
}

item[begin]에서 items[end] 사이에서 target을 검색한다.

public static int binarySearch(String[] items, String target, int begin, int end){
  if(begin > end){
    return -1;
  } else{
    int middle = (begin + end) / 2;
    int compResult = target.compareTo(items[middle]);
    if(compResult == 0){
      return middle;
    } else if(compResult < 0){
      return binarySearch(items, target, begin, middle-1);
    } else{
      return binarySearch(items, target, middle+1, end);
    }
  }
}

반복문을 사용한다면 begin = 0, end = n으로 두고 짜면 된다.

hue9010 Reading time ~1 minute

오늘 한일

  • 코드스쿼드의 화이트 과정 반복주기를 복습 했다.

    • Question의 String형의 writer를 User 클래스로 변경했다.

    • 역시 오랜만에 하면 익숙치 않아서 헤매는 부분이 있다.

  • 알고리즘 강의의 순환개념에 대해 공부 했다. (포스팅)

    • 가능하면 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

    • 암시적 매개 변수란 
      for(int i = 0; i < n; i++)

      같은 형태에서 0의 값에서 부터 시작할 것이라고 생각 하고 작성하는 것이다.
      명시적 매개변수는 begin, end 값을 매개변수로 받아서 이를 명시한다.

    • 이전까지는 Recursion, 즉 재귀함수는 사용하기 복잡해서 피보나치 및 몇몇 특수한 케이스를 제외하면 쓰기 힘들다고 생각했는데 생각이 바뀌게 된거 같다. 재귀함수를 어떻게 작성해야 할지 많은걸 배운거 같다.

  • 코드스쿼드 마스터즈 멤버스 모집 설명회에 참석했다.

    • 레벨4를 추천 받았다. 개인적으론 같이 들으실 분들보다 웹에 대해서는 지식이 적다고 판단 되기 때문에 그전에 많은 지식을 쌓아가자(지식도 중요하지만 실습을 통해 만들줄 아는 능력도 같이 고려해서 학습하자)

내일 할일

  • 코드스쿼드의 화이트 과정 복습

  • 알고리즘 강의 듣기

hue9010 Reading time ~1 minute

인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

Recursion Thinking(순환적으로 사고하기)

수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.

  • 모든 순환함수는 반복문(iteration)으로 변경 가능하다.

  • 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능하다.

  • 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.

  • 하지만 함수 호출에 따른 오버레드가 있다.(매개변수 전달, 액티베이녀 프레임 생성 등)

문자열의 길이 계산

public static int length(String str){
  //Base case
  if(str.equals("")){
    return 0;
  }
  //Recursice case
  else{
    return 1 + length(str.substring(1));
  }
}

문자열을 화면에 출력하는 함수

public static void printChars(String str){
  //Base case
  if(str.length()==0){
    return;
  }
  //Recursice case
  else{
    System.out.print(str.charAt(0));
    printChars(str.substring(1));
  }
}

문자열을 뒤집어서 화면에 출력하는 함수

public static void printCharsReverse(String str){
  //Base case
  if(str.length()==0){
    return;
  }
  //Recursice case
  else{
    printCharsReverse(str.substring(1));
    System.out.print(str.charAt(0));
  }
}

2진수로 변환하여 출력(음이 아닌 정수 n)

public void printInBinary(int n){
  //Base case
  if(n<2){
    System.out.print(n);
  }
  //Recursice case
  else{
    printInBinary(n/2);
    System.out.print(n%2);
  }
}

배열의 합 구하기(n은 배열의 크기)

public static int sum(int n, int[] data){
  //Base case
  if(n<-0){
    return 0;
  }
  //Recursice case
  else{
    return sum(n-1, data) + data[n-1];
  }
}

데이터파일로 부터 n개의 정수 읽어오기

public void readFrom(int n, int[] data, Scanner in){
  //Base case
  if(n==0){
    return;
  }
  //Recursice case
  else{
    readFrom(n-1, data, in);
    data[n-1] = in.nextInt();
  }
}
hue9010 Reading time ~1 minute

오늘 한일

  • 코드스쿼드의 화이트 과정 반복주기를 복습 했다.

    • DB에 데이터 저장 : 기존에 List에 저장했던 데이터들을 DB를 이용하게 했다.

    • 인증 기반 개발 : HttpSession을 이용하여 사용자 인증을 했다. 이전에 할때는 이게 무엇인지 잘 몰랐는데, 자바 워크북을 통해 공부하고 나니 session을 통해 인증이 왜 가능한지 알게 됐다.

  • 알고리즘 강의의 순환개념에 대해 공부 했다. 반복문(for, while)로 짠 것은 recursion으로 변환 시킬 수 있고, 반대로 recursion으로 짠 것도 반복문으로 변환 가능 하다.( 포스팅)

내일 할일

  • 코드스쿼드의 화이트 과정 복습

  • 알고리즘 강의 듣기

  • 코드스쿼드 마스터즈 멤버스 모집 설명회 참석

hue9010 Reading time ~1 minute

인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

Recursion

  • 자기 자신을 다시 호출하는 함수(혹은 메소드)

  • 순환, 재귀함수라고도 불린다.

  • 재귀함수를 활용 할 수 있는 곳

    • x의 n승을 계산 하는 함수

    • 피보나치…등

void func(){
  func();
}

잘못 짜면 아래와 같이 무한 루프에 빠질 수 있다.

public static void main(String[] args){
  func();
}
public static void func(){
  System.out.println("Hello...");
}

<출력>

Hello...
Hello...
Hello...
Hello...
.
.
.

무한루프에 빠지지 않기 위한 조건

  • Base case:적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.

  • Recursice case: recursion을 반복하다 보면 결국 base case로 수렴해야 한다.

public class Code01{
  public static void main(String[] args){
    func(4);
  }

  public static void func(int n){
    //Base case
    if(n<=0){      
      return;
    }
    //Recursice case
    else {        
      System.out.println("Hello..");
      func(n-1);
    }
  }
}

<출력>

Hello..
Hello..
Hello..
Hello..

n에서 0까지 더하는 함수

public class Code01{
  public static void main(String[] args){
    int result = func(4);
    System.out.print(result);
  }

  public static int func(int n){
    //Base case
    if(n==0){      
      return 0;
    }
    //Recursice case
    else {        
      return n + func(n-1);
    }
  }
}

<출력>


10

factorial

public static int factorial(int n){
  if(n==0){
    return 1;
  } else{
    return n*factorial(n-1);
  }
}

fibonacci

public int fibonacci(int n){
  if (n<2){
    return n;
  } else{
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

최대 공약수

public static double gcd(int m, int n){
  if (m<n){      //swap m and n
    int tmp = m;
    m = n;
    n = tmp;
  }
  if (m%n==0){
    return n;
  } else{
    return gcd(n, m%n);
  }
}

m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n 이고,
그렇지 않으면 gcd(m,n) = gcd(n, m%n) 이다.

더 간단한 버전

public static int gcd(int p, int q){
  if(q==0){
    return p;
  } else {
    return gcd(q, p%q);
  }
}