정렬 정렬이란 데이터를 특정한 기준에 따라 순서대로 나열한 것이다. 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 가장 앞의 데이터와 바꾼다. 앞선 1번의 과정을 반복한다. 정렬되지 않은 데이터가 하나가 남은 경우 처리하지 않아도 완성이 된다. array = [7, 3, 5, 4, 2, 6, 1, 0] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j a..
Python/알고리즘 - 이론
DFS DFS는 깊이 우선 탐색이라고도 불리며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며, 구체적인 동작은 아래와 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다 # DFS 함수 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not vi..
재귀 함수 자기 자신을 다시 호출하는 함수 단순한 형태의 재귀 함수 예제 '재귀 함수를 호출합니다'라는 문자열을 무한히 출력합니다. 어느 정도 출력하다가 최대 재귀 깊이 초가 메시지가 출력됩니다. def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() 재귀함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. def recursive_function(i): # 100번째 호출을 했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, '번째 재귀함수에서', i + 1, '번째..
스택 자료구조 먼저 들어온 데이터가 나중에 나가는 형식의 구조(후입 선출) 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 큐 자료구조 먼저 들어온 데이터가 처음 나가는 형식의 구조 (선입 선출) 입구와 출구가 일자로 이어져있는 터널형태로 큐를 시각화 ..
그리디 알고리즘 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 코딩 테스트에서는 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이론 추론할 수 있어야 풀리도록 출제된다. 예제: 거스름돈 문제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거..
