이번 유닛은 자료구조와 알고리즘에 대해 배우기 시작했는데 그 중에서도 재귀를 배우게 됐다. 재귀는 java를 많이 하면서 꽤 많이 접했던 것이고, 많이 사용하기도 했던터라 쉬울 것이라 생각을 했지만, 막상 다시 부딪혀보니 어려운 부분도 있었고 아직 종료조건과 recursion을 다시 호출해야 할 때를 잘 파악하지 못하는 것 같다. 이제는 재귀에 대한 정리를 해보고 강의자료에서 추천해준 실습을 위주로 정리하고 느낀 점을 풀어보겠다.
재귀함수
-
어떤 문제를 해결할 때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법
-
함수가 실행과정 중에 자기 자신을 호출하는 방법을 재귀호출이라 한다.
재귀의 사용 시기
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복분이 많거나 반복문의 중첩 횟루를 예측하기 어려운 경우
JSON의 Stringify 재귀로 구현해보기
JSON
-
JavaScript Object Notation의 줄임말로, 데이터 교환을 위해 만들어진 객체 형태의 포맷이다. 즉, 서로 다른 프로그램 사이에서 데이터를 교환하기 위한 포맷이다. -
JSON.stringify:Object Type을JSON으로 변환한다. (serialize) -
JSON.parse:JSON을Object Type으로 변환한다.(deserialize) -
JSON은 키(key)는 반드시 쌍따옴표를 붙이며, 문자열 값(value) 은 반드시 쌍따옴표로 감싸야 한다. 그리고 키와 값 사이, 키-값 쌍 사이에 공백이 없어야 한다.
재귀를 이용한 구현
우선 아이디어를 얻은 것은 JSON이 객체 형태의 포맷이며, object type을 JSON으로 변환하는 것이라는 것에서 얻었다. 사실 타입이 object일 경우를 제외하고라면 각 조건에 맞게 리턴을 해주면 된다. 인자로 들어온 값의 타입이 object일 때는 두 가지로 나누어 생각을 해야한다. 한 가지는 배열일 때이고, 다른 한 가지는 객체일 때를 생각해야 한다. 배열일 경우에는 배열 요소를 전체를 '[]'으로 감싸야 하기 때문에 40번과 46번 줄과 같이 처리를 해주었으며, 각 요소는 다시 재귀를 통해서 각 값에 맞는 stringify를 해주도록 했다. 그리고 객체일 경우에도 비슷하지만 객체는 키와 값의 쌍으로 되어있기 때문에 key에 해당하는 것은 쌍따옴표를 붙여 처리를 해주고 값에 해당하는 것은 다시 stringify를 해주어 처리를 해주었다. 완벽하지는 않지만 얼추 기능을 구현할 수 있었다.
실습 및 느낀점
하노이 탑
실습을 끝내고 나서는 강의자료에서 하노이 탑 알고리즘도 생각해보는 것을 권장했다. 그래서 하노이 탑에 대해 알아봤으며, 전에도 하노이 탑 알고리즘을 푼 기억이 있어서 다시 풀어보려고 한다.
정의
하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.
게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.
- 한 번에 한개의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안 된다.
위키피디아 내용 참조
풀이
하노이 탑은 우선 가장 밑의 원반이 도착 지점으로 옮겨야 나머지 원반들을 옮길 수가 있다. 그리고 맨 밑의 원반을 도착 지점으로 옮기기 위해서는 나머지 원반들을 시작 지점과 도착 지점이 아닌 다른 기둥에 옮겨야 한다. 이를 기본으로 코드를 짰다.
우선 하노이 탑에서 기둥은 세 개가 존재하고 각 기둥이 1,2,3 이라고 한다면 다른 기둥의 번호는 6 - from - to를 통해 알 수가 있다. base case는 n이 1 이하일 때이다. 이 때는 바로 원반을 옮겨주기 때문이다. 그 외에는 위에서 얻은 아이디어 대로 총 원반이 n개라고 한다면 n-1개의 원반을 먼저 다른 기둥으로 옮기는 작업이 필요하다. 이는 다시 재귀적으로 처리할 필요가 있다. 이 작업이 완료가 됐다면 이제 원반 한 개를 시작 지점에서 도착 지점으로 보낼 수가 있다. 그런 다음에는 다른 기둥에 있는 n-1개의 원반을 도착 지점으로 옮겨주는 작업을 다시 재귀적으로 처리하면 하노이탑은 구현이 된다. 그리고 이동 횟수는 재귀의 중첩과 관련이 있으므로 재귀 안에서 원반이 움직임을 표현할 때 count를 올려주면 된다.
이번에는 재귀 연습문제와 여러가지 실습을 통해서 재귀를 배워봤다. 재귀함수를 확실히 많이 해왔었지만 다시 겪어보니 언제 종료조건을 주어야할지 어디에서 재귀적으로 다시 처리를 해야할지에 대한 고민을 하게 됐다. 전에는 이런 생각을 하지 못했는데 튜터링을 받고 생각을 해보니 조금 더 재귀에 대해 생각해볼 수 있었던 것 같다. 튜터님은 재귀는 무조건 연습이라고 하셨다. 많은 코드를 짜볼테지만 재귀를 많이 사용해봐서 나에게 익숙해지는 것이 중요할 것 같다. 아직 풀이에 대한 정리도 제대로 하지 못하는 것 같은데 이런 점도 보완하여, 블로그도 잘하는 개발자가 되어보자 ^^
Reference
- 코드스테이츠 강의자료
