알루 코딩

순차 탐색 이진탐색 알고리즘을 배우기 전에 가장 기본 탐색 방법인 순차 탐색 방법에 대해 알아보자. 순차 탐색이란, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법이다. 말그대로, 순차적으로 탐색을 한다는 의미인데, count() 함수를 이용할 때도 내부에서는 순차 탐색이 수행될 정도로 자주 사용된다. N개의 데이터에서 최대 N번의 비교 연산이 필요하므로 순차 탐색의 시간복잡도는 최악의 경우, O(N)이다. 순차 탐색 코드는 아래와 같다. import sys input = sys.stdin.readline # 순차 탐색 소스코드 구현 def sequential_search(n,target,array): # 각 원소를 하나씩 확인하며 for i in range(..

신장 트리 : 신장 트리(Spanning Tree)란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하기 때문에, 이러한 그래프를 신장 트리라고 부르는 것이다. 예를 들어보자. 크루스칼 알고리즘 다양한 문제 상황에서 가능한 한 최소한의 비용으로 신장 트리를 찾아야 하는데, 이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '신장 트리 알고리즘'이라고 한다. 대표적인 신장 트리 알고리즘으로는 '크루스칼 알고리즘(Kruskal Algorithm)'이 있다. 크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 모든 간선에 대하여 정렬을..

'DFS/BFS'와 '최단 경로'에서 다룬 내용도 그래프 알고리즘의 한 유형으로 볼 수 있다. 그래프 알고리즘은 코딩 테스트에서 출제 비중이 낮은 편이지만, 출제되기 때문에 기타 그래프 알고리즘도 살펴볼 필요가 있다. 지금부터 다룰 알고리즘은 앞서 배운 내용에 기반하는데, 예를 들어 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류되고, 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료구조 혹은 스택 자료구조를 활용해야 구현할 수 있다. 복습을 해보자면, 그래프란 노드와 간선의 정보를 가지고 있는 자료구조이고, 알고리즘 문제에서 '서로 다른 개체가 연결되어 있다'는 얘기가 있다면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 더불어, 그래프 자료구..

최단 경로(Shortest Path) 란 ? : 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. '길 찾기' 문제라고도 불리는데, 다양한 유형이 있다. 예를 들어, "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우" 나 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우" 등이 있다. 보통, 최단 경로 문제는 그래프를 이용해 표현하는데, 각 지점은 그래프에서 '노드(node)'로 표현되고, 각 지점마다 연결된 도로는 그래프에서 '간선(edge)'으로 표현된다. 코딩 테스트에서는 보통 최단 경로를 모두 출력하는 문제보다는 '최단 거리'를 출력하는 문제가 많다. 학부 수준에서 다루는 최단 거리 알고리즘은 대표적으로 아래와 같다. 1. 다익스트라 알고리즘 2. 플로이드 워..

다이나믹 프로그래밍(동적 계획법) 이란 ? : 컴퓨터 연산을 하면서 중복되는 연산을 줄이자는 목적으로 나온 기법이다. 보통, 다이나믹이라고 하면 '프로그램이 실행되는 도중에' 라는 의미로 쓰이는데(ex.동적할당), 여기서는 그런 의미는 아니다. 연산을 줄이자는 것이 목적이라면, 재귀함수로 프로그램을 짤 수도 있는 것 아니냐고 생각할 수 있다. 물론, 할 수는 있다. 하지만, 수가 크다면, 실행시간은 기하급수적으로 늘어나기 때문에, 계속해서 재귀함수를 호출하는 것은 컴퓨터에 많은 부하를 줄 수 있다. 예를 들어, 피보나치 수열을 재귀함수로 구현한다면, n이 100 이기만 해도, 연산 횟수가 약 1,000,000,000,000,000,000,000000,000,000번이다. 즉, 1초에 1억번 정도의 연산을..