[2022.05.24] 자료구조/알고리즘 - 재귀
Section1이 끝나고 Section2가 시작되었다!
Section2부터는 매일 간단한 코딩 테스트 문제 1개를 풀기 시작하였다.
그리고 오늘은 자료구조/알고리즘에서 재귀함수에 대해 공부를 하였다.
Daily coding
오늘은 입력받은 배열의 첫 요소와 마지막 요소를 뽑아 이를 각각 Key와 Value로 HashMap으로 만들어 반환하는 메서드를 구현하는 문제였다.
이제 시작인 부분이기 때문에 쉬운 문제가 출제된 것 같으나.. HashMap을 초기화하는 방법을 몰라서 검색을 해봐야 했다.
검색 결과 HashMap을 초기화하는 방법은 아래와 같이 구현이 가능하다는 사실을 알았다.
new HashMap<String, String>(){
{
put("Key", "Value");
}
}
처음 생각할 땐 "new HashMap<String, String>(){ "Key" : "Value", ...}" 형태로 초기화를 하는 줄 알았는데.. 위 방법으로 한다는 것을 알고선 신기했다. 중괄호 안에 중괄호를 작성하고 put() 메서드를 활용해서 초기화를 한다는 것이..
C언어를 쓸 땐 이러한 초기화 방법을 볼 수 없었기에 상상조차 하지 못 한 방법이었다.
재귀 함수(recursion function)
재귀 함수가 뭔지는 알고 있었으나 잘 사용을 안해봐서 어렵게 느끼고 있었던 개념이다.
재귀 함수를 간단하게 정리를 해보자면 이렇다.
함수 내에서 자기 자신을 호출하여 문제를 해결하는 함수
말 그대로 자기 자신을 계속하여 호출해서 결과를 해결할 수 있도록 만드는 함수(메서드)다.
개념을 공부한 후 페어와 함께 재귀 함수를 이용해서 푸는 문제를 풀어보며 이해도를 올렸다.
문제를 풀면서 어느정도 감을 잡았지만.. 어느정도 간단한 문제들이었기에 이해하고 풀 수 있었다고 생각이 된다.
재귀 함수에 대한 대표적인 문제 중 하나로써 팩토리얼(factorial)을 해결하는 재귀 함수 구현이 있다.
매개 변수로 받는 숫자의 팩토리얼을 구하는 재귀 함수를 구현한다면 아래와 같이 구현이 가능할 것이다.
int factorial(int num) {
if(num == 0) return 1;
return num * factorial(num - 1);
}그리고 해당 재귀 동작에 대한 예로는 아래의 그림을 참고하면 된다.
