이것이 취업을 위한 코딩 테스트다 with 파이썬
IT 취준생이라면 누구나 입사하고 싶은 카카오・삼성전자・네이버・라인!취업의 성공 열쇠는 알고리즘 인터뷰에 있다! IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년
www.google.com
최근 위 책을 공부하면서 우리가 알고리즘과 자료구조를 이해해야 하는 이유, 이것들을 어떻게 공부해야 하는지에 대해 면밀히 책을 1회독했다. 맨 땅에 헤딩 식으로 공부를 하다 보니 다행히 이해가 늦진 않아서 DFS/BFS/DP 등에 대해 좀 더 상세히 이해할 수 있었고, 프로그래머스 기준 3레벨 문제도 슬슬 잘 풀리기 시작했다. 2단계 벽이 생각보다 높게 느껴져서 재능이 여기까지인가.. 하고 좌절하고 있었는데 자신감을 찾는 계기를 이 책이 찾아주어서 너무 기뻤다.
3단계를 풀 수 있는 현재와 풀 수 없는 이전과의 차이를 생각해보면
- 자료구조/알고리즘 상세 이해도 차이
- 알고리즘 별 핵심 용어 이해 부족
- 재귀함수 사용 부재
이렇게 정리된다.
따라서 이 3가지 깨달은 점들을 앞으로 상세히 적어볼 것인데, 우선은 재귀함수에 대해 적어볼 것이다.
이 개념은 초급 단계에서 반드시 공부해두는 것이 좋다. 다음 게시글에서 작성하겠지만, DFS/DP 알고리즘 등 다양한 곳에서 사용할 개념이 많기 때문에 핵심요소를 반드시 알아야 한다.
'재귀' : 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 자기언급과도 관련된 재귀는 언어학에서 논리학에 이르기까지 다양한 분야에서 연구되는 주제로, 특히 컴퓨터 과학과 수학에서, 재귀는 함수가 자신의 정의에 의해 정의될 때의 개념을 가리킨다. - 위키백과 -
재귀함수란 이 재귀를 이용한 함수이다. 아래 간단하게 재귀함수를 적었다.
def function():
print('재귀함수')
function()
function()
이렇게 치면 '재귀함수'가 무한정 나올 것이다. '재귀함수'를 print한 다음 다시 자기 자신을 구현하기 때문이다.
하지만 직접 해보면 결국 오류 하나가 발생한다.
RecursionError : maximum recursion depth exceeded while pickling an object
컴퓨터가 무한정으로 출력하다 보니 파이썬 인터프리터에서 호출 횟수 제한을 발동시켜서 막은 것이다. 아마 파이썬 말고 다른 언어라도 출력에 제한을 두지 않을까 생각하는데, 무한정으로 재귀함수를 뽑아낼 일은 현재까지 보지 못했다.
그래서 우리는 무한 호출을 막기 위해 '종료 조건'을 설정해야 한다. 일정 조건을 달성하면 종료를 시키는 조건을 만들어야 위와 같은 오류코드를 볼 일이 없을 것이다.
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
종료조건을 설정한 팩토리얼 함수를 구현했다. 여기서는 n을 0까지 순차적으로 감소시켜서 n이 0일 때는 함수 식을 끝내는 종료조건을 설정했다.
재귀함수를 잘 구현하기 위해서는 기본적인 종료조건 설정 외에도, 인자에 어떤 것을 넣을지를 코딩테스트에서 잘 생각해야 한다. 결국 공부한 것을 토대로 잘 활용하기 위해서는 다른 알고리즘과 잘 결합하여 구현하는 것이 중요한데, 개인적으로 1주일 간 수십 문제를 풀어보니 전체적인 알고리즘 속에서 어떻게 메인 함수에 재귀함수를 적용시킬지, 어떻게 그 재귀함수를 종료시킬지, 재귀함수의 대상 범위를 어느 정도로 설정할지 정도가 중요해 보인다. 결국은 많이 풀어봐서 잘 적용하라는 말이긴 한데.. 그렇게 해야 하는 이유를 간략하게 적어보았다.
필자처럼 코딩테스트 준비하는 많은 분들께 건승을 빌며!
'Computer Science > 자료 구조, 알고리즘' 카테고리의 다른 글
| 원형연결리스트 (0) | 2023.10.21 |
|---|---|
| 이중연결리스트 (0) | 2023.10.21 |
| 버블 정렬 (0) | 2023.10.02 |
| 병합 정렬 (0) | 2023.09.24 |
| 퀵 정렬 (0) | 2023.09.24 |