대학교 수업시간에 엄청 많이 경험을 해보았고, 파이썬으로 수많은 코드를 작성해 보았지만, 알고리즘에 관련된 문제들은 정말로 어려운 것 같다. 그래도 계속해서 문제를 풀다보면 언젠가는 빠르게 풀리는 날이 오지 않을까?
재귀
재귀는 함수의 리턴값으로 자기 자신을 호출하는 방법이다. for이나 while을 대신하여 사용하는데, 코드를 간결하게 작성 할 수 있다는 장점이 있다.
재귀적으로 코드를 작성하는 방법은
1. 작은 문제로 쪼개기: 우선 해결해야 하는 문제를 여러가지 작은 문제들로 쪼개어 생각해봐야 한다.
2. 가장 작은 단위로 쪼개기: 계속해서 쪼개다가 가장 작은 단위로 쪼개 더이상 쪼갤 수 없을 때의 상태를 알아본다.
3. 가장 작은 단위부터 문제 해결하기: 가장 작은 단위의 문제를 해결하고, 그 다음 문제를 해결하고를 반복하여 원하는 값을 구한다.
말로는 이렇게 설명 되어있지만, 사실 코드 자체를 보지 않으면 이해가 되지 않을 수 있다. 예시로 배열의 모든 원소의 합을 구하는 재귀함수를 수도코드로 작성하면
[1,2,3,4,5]의 배열의 모든 원소의 합
1. 1+[2,3,4,5]와 같다.
2. 1+2+[3,4,5]와 같다.
3. 계속 하면 1+2+3+4+[5]와 같다.
4. 마지막에는 1+2+3+4+5+[]와 같은 것이다.
5. 재귀적으로 맨 처음 요소와 그 나머지 배열의 요소들의 합을 계속해서 구해주면 될 것이다.
function arrSum (arr) {
// basecase
if (arr.length === 0) {
return 0
}
// return case
return arr.shift() + arrSum(arr)
}이런 쉬운 문제들은 사실 금방 해결 할 수 있는데, 재귀와 반복문을 합쳐서 사용하는 문제들이 이번 과제로 제시되었는데, 상당한 어려움을 느꼈다. 개념부터 확실히 적립하고, basecase구하고, 그 베이스케이스 시에 코드를 종류하는 if문의 작성을 잘 생각해내는 것이 중요한 것 같다.
