알고리즘 / 재귀

1. SW 문제 해결 능력

  1) SW 문제 해결 역랑

    - 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력

    ※ 한 문제를 풀고 3명 이상의 풀이법을 보기

    - 문제 해결 역량은 추상적인 기술이다.

    - 문제 해결 역량을 향상하기 위해서 훈련이 필요하다.

  2) 문제 해결 과정

    - 문제를 읽고 이해한다. (3회독)

    - 어떻게 해결할지 계획을 세운다.

    - 계획을 검증한다. (시간 복잡도, 공간 복잡도)

    - 프로그램으로 구현한다.

    - 어떻게 풀었는지 돌아보고, 개선한 방법이 있는지 찾아본다.

    - 1시간이 지나면 풀었든 못 풀었든 다른 사람들의 코드를 찾아본다. (3명 이상) 

  3) 알고리즘 

    - 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다.

 

---

 

2. 알고리즘 성능

  1) 시간 복잡도

    - 최선의 경우 : 빅 오메가 표기법 사용

    - 최악의 경우 : 빅 오 표기법 사용

    - 평균적인 경우 : 빅 세타 표기법 사용

  2) 공간 복잡도

    - 메모리 사용량

  3) 빅오 표기법

    -  시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시

 

---

 

3. 재귀 호출

  1) 반복과 재귀

    - 반복은 수행하는 작업이 완료될 대 까지 계속 반복

    - 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법

    - 재귀는 함수로 구현한다.

    - 재귀는 기본 부분과 유도 부분으로 구성된다.

 

---

 

4. 재귀 호출 - 피보나치수열

public static int fibonacci(int number) {
		if (number == 1) {
			return 1;
		} else if (number == 2) {
			return 1;
		} else {
			return fibonacci(number - 1) + fibonacci(number - 2);
		}
	}

 

 

※ 참고 : https://adjh54.tistory.com/194

[Java/알고리즘] 재귀 함수(Recursion Function) 이해하기