루피

DFS (Depth- First Search) 그래프를 탐색하는 방법 중 하나인 DFS는 깊이 우선 탐색을 의미한다. DFS는 노드에서 탐색을 시작할 때 다음 분기로 넘어가기 전 해당 분기를 끝까지 탐색하는 알고리즘으로, 스택 자료구조 혹은 재귀 함수를 이용하여 구현할 수 있다. 처음 접한다면 위처럼 간단한 말로는 이해하기 어려울 수 있기에 조금 더 구체적으로 동작 과정을 설명해보겠다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 탐색 시작 노드와 인접한 노드를 스택에 넣고 방문 처리를 한다. 3. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다. 4. 수행할 수 없을 때까지 3번을..

재귀 함수 (Recursive Function) 재귀 함수란 자기 자신을 호출하는 함수를 의미한다. 자기 자신을 호출하는 재귀 함수는 반복해서 코드를 실행하기에 반복문과 유사하다. 따라서 재귀 함수를 반복문으로, 혹은 반복문을 재귀 함수로 변환할 수 있으며, 사용 목적에 따라 무엇을 사용할지 선택하는 것이 좋다. 또한 재귀 함수에서는 종료 조건을 명시해주어야 한다. 종료 조건을 명시하지 않으면 함수가 무한히 호출되며 최대 재귀 깊이를 초과하는 RecursionError가 발생한다. 재귀 함수 예제 - 팩토리얼 자연수 n의 팩토리얼을 구하여라. n의 팩토리얼은 n! = 1 x 2 x ... x (n-1) x n 을 의미한다. >> 팩토리얼은 연속된 숫자를 반복해서 곱하여 표현하기에 재귀함수를 통해 쉽게 구..

그리디 알고리즘이란? 그리디 알고리즘은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 결과를 도출하는 기법이다. 그리디 알고리즘은 지금 당장의 상황만을 고려하면 되기에 편리하다. 하지만 매 선택의 순간에서의 최적이 종합적 측면에서의 최적을 보장하지는 않기에 주의를 해야한다. 또한 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지 못하는 경우가 많다. 따라서 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요하다. 편의점에서 손님이 물건을 사고 값을 지불하였을 때 N원의 돈을 거슬러 줘야한다. 그럼 이 N을 거슬러 줄 때 사용할 수 있는 동전의 최소 개수는 몇 개일까? (N은 10의 배수이며 동전은 500원, 100원, 50원, 10원짜리이다.) >> 최적의 ..

복잡도(Complexity) 알고리즘의 성능을 어떻게 평가할 수 있을까? 흔히 우리는 복잡도(Complexity)를 이용하여 알고리즘을 평가할 수 있다. 이 때 복잡도는 시간 복잡도와 공간 복잡도로 구성된다. 시간 복잡도: 알고리즘의 수행 시간 분석 공간 복잡도: 알고리즘의 메모리 사용량 분석 같은 기능을 수행하는 알고리즘이 있다면, 복잡도가 낮을숙록 좋은 알고리즘이라고 할 수 있다. (기업의 코딩 테스트에서도 요구사항(복잡도)를 고려해야 불미스러운 사고를 예방할 수 있다...) 빅오 표기법(Big-O Notation) 그렇다면 복잡도를 어떻게 구체적으로 표기할 수 있을까? 그 방법 중 하나는 바로 빅오 표기법(Big-O Notation)이다. 빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법이..