루피

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 을 의미한다. >> 팩토리얼은 연속된 숫자를 반복해서 곱하여 표현하기에 재귀함수를 통해 쉽게 구..

큐 (Queue) 큐는 먼저 들어 온 데이터가 먼저 나가는 선입선출의 자료구조이다. 큐는 입구와 출구가 모두 뚫려 있는 터널 형태로 사긱화 할 수 있다. 예시를 통해 큐 동작 구조에 대해 살펴보자. "삽입(1) - 삽입(2) - 삭제() - 삽입(3) -삭제() - 삽입(4)"를 실행하면 큐에서는 다음의 순서로 동작한다. 파이썬에서의 큐 파이썬에서 큐를 구현할 때 deque 라이브러리를 사용하면 편리하다. deque에서는 append 메서드를 통해 삽입을, popleft 메서드를 통해 삭제를 할 수 있다. deque를 사용한 코드는 아래와 같다.

스택 (Stack) 스택은 나중에 들어 온 데이터가 먼저 나가는 형식(후입선출)의 자료구조이다. Last in First Out이란 뜻으로 LIFO라고도 표현할 수 있다. 이러한 스택은 입구와 출구가 동일한 형태로 시각화할 수 있다. 이 스택 구조를 사용하여 "삽입(1) - 삽입(2) - 삽입(3) - 삭제 - 삽입(4)" 을 실행해보자. 그럼 아래의 그림과 같은 순서로 진행이 된다. 파이썬에서의 스택 파이썬에서는 리스트 자료형를 사용하여 스택을 구현할 수 있다. 리스트의 append와 pop 매서드를 이용하여 "삽입(1) - 삽입(2) - 삽입(3) - 삭제 - 삽입(4)" 을 표현해보자.

구현(Implementation) 구현이란 알고리즘을 소스코드로 바꾸는 과정이다. 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 구현 문제의 유형은 다음과 같다. - 알고리즘은 간단하지만 코드가 긴 문제 - 실수 연산을 통해 특정 소수점까지 출력해야 하는 문제 - 문자열을 특정 조건에 맞게 처리해야 하는 문제 - 적절한 라이브러리를 활용해야 하는 문제 구현 예제 - 상하좌우 이동 자유롭게 이동할 수 있는 n x n의 공간이 있다. 이 공간은 (1, 1)에서 (n, n)으로 표현할 수 있고, 나의 현재 위치는 (1, 1)이다. 현재 위치에서 임의의 특정 방향으로 이동을 하였을 때 나의 최종 도착 지점의 좌표를 구해보자. (n x n의 공간을 벗어날 수 없다.) ..

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

리스트(List) 리스트는 여러 개의 데이터를 연속적으로 처리하기 위해 사용하는 자료형이다. (C나 자바의 배열과 유사함) 1. 리스트 선언하기 2가지 방법으로 리스트를 선언할 수 있다. 1) 대괄호 a = [] b = [1,2,3] c = ['가','나','다','라'] 2) list() a=list() 이 때 a=list()는 비어있는 리스트를 만들게 되며, a=[]와 같은 기능을 하게 된다. 2. 리스트 인덱싱, 슬라이싱 리스트 원소에 접근할 때 인덱스를 사용할 수 있다. 파이썬의 인덱스는 0부터 시작한다. a = ['가','나','다','라'] 라는 리스트에서 a[0] = '가' a[1] = '나' a[2] = '다' a[3] = '라' 를 의미하며 여기서 재밌는 점은 인덱스에 음수를 사용할 수 ..

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