Redddy's Devlog

재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다. 아래와 같은 함수가 재귀 함수이다. def recursive_function(): print("재귀 함수를 호출합니다.") recursive_function() recursive_function() 그러나 이 코드를 실행시킨다면 "재귀 함수를 호출합니다." 라는 문장을 출력하다가 어느 순간 에러를 내며 멈출 것이다. RecursionError: maximum recursion depth exceeded while calling a Python object 이 오류 메세지는 재귀의 최대 깊이를 초과했다는 내용이다. 보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 그 한계를 벗어났기에 다음과 같은 메세지를 출력한 ..

구현이란? 구현(Implementation)이란 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정입니다. 물론 어떤 문제를 풀던 간에 소스코드를 작성하는 과정은 필수이다. 그러나 구현이라고 따로 분류하는 문제들은 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 완전 탐색과 시뮬레이션은 모두 구현이 핵심이 되는 경우가 많다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 이것이 코딩테스트다를 읽고 정리한 내용입니다.

그리디 알고리즘이란? 한국어로 탐욕이라는 뜻의 그리디 알고리즘(Greedy Algorithm)은 단순하만 강력한 문제 해결 방법이다. 탐욕적으로 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'이 바로 탐욕법, 그리디 알고리즘이다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 다른 알고리즘과는 달리 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 유형의 문제이다. 다음번에 다룰 최단 경로, 정렬 등의 알고리즘 유형은 이미 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 ..

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리 Complete binary Tree로 되어 있다. 힙 트리의 루트 노드(root node)에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데, 전자는 최대힙(max-heap), 후자는 최소힙(min-heap)이라 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(log N)이다. 무작위 숫자들을 힙에 전부 넣고 하나씩 빼면 정렬된 결과를 얻을 수 있는데, 이게 힙정렬이다. from queue import PriorityQueue pq = PriorityQueue() pq.put(123) pq.put(789) p..

Queue는 스택과 상반된 특징을 띄고 있는 자료구조이다. 둘 다 선형 자료구조이지만, 데이터 입출 순서가 달라지는 부분이 있다. 큐에는 데이터를 넣은 순서 그대로 빼게 된다. 첫 번째로 넣은 데이터가 첫 번째로 빠지며 이를 FIFO라 한다. 큐에 데이터를 넣고 뺄 때 시간 복잡도는 O(1)이므로 N개의 데이터를 넣고 빼야 한다면 총 O(N)이 될 것이다. from queue import Queue q = Queue() q.put(123) q.put(456) q.put(789) while not q.empty(): print(q.get()) 이렇게 import 해서 사용하면 된다. 위 코드에서 대문자 Q로 시작하는 Queue 모듈은 멀티스레딩 환경까지 고려해서 스레드 간에 안전한 방식으로 동작하는 모듈이..

Stack은 '쌓다', '무언가가 쌓여 있는 더미' 등을 의미한다. 스택은 의미 그대로 어떤 데이터를 삽입/삭제하는 과정을 '쌓는' 형태로 나타낼 수 있는 자료구조이다. 스택의 특징은 FILO (First In Last Out) 즉 먼저 저장된 데이터가 가장 나중에 나가는 방식으로 저장된다. 이름에서 힌트를 준것처럼 데이터가 차례대로 쌓인다. 가장 나중에 들어온 데이터는 먼저 나간다 LIFO (Last In First Out). 풜스트인풜스트 아웃 이말은 전에 TV 프로그램을 보다가 소방관 얘기가 나왔을 때 먼저 접했던 것 같다. 자료구조 얘기 하다가 뭔 소방관 얘기냐? 할 수 있겠는데 소방관들이 화재 현장을 들어 갈 때 FILO을 한다고 한다. 즉 먼저 들어가서 구조를 하고 끝까지 현장에 남아서 구조를..