[이코테] 최단 경로 알고리즘

1. 다익스트라 알고리즘 최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 내가 학교를 다닐 때 배운 알고리즘은 다익스트라 알고리즘과 플로이드 워셜 이렇게 2가지였다.(더 있는데 기억 안나는 걸 수도 있음.) 이 2가지가 코딩 테스트에서 가장 많이 등장하는 유형이라고 하니 이 2가지만 먼저 자세히 알아보자. 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음..

• format_list_bulleted Algorithm
• · 2020. 12. 3.
• textsms

[이코테] 자료구조 - 힙 (heap)

힙 자료구조에 대해서 알아보자. 힙 자료구조는 우선순위 큐 (Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나다. 'DFS/BFS'를 공부할 때 스택과 큐의 원리에 대해서 알아봤는데 스택은 가장 나중에 삽입된 데이터를 가장 먼저 삭제하고, 큐는 가장 먼저 삽입된 데이터를 가장 먼저 삭제한다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다. 자료구조 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터 큐(Queue) 가장 먼저 삽입된 데이터 우선순위 큐(Priority Queue) 가장 우선순위가 높은 데이터 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예를 들어 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높..

• format_list_bulleted Algorithm
• · 2020. 12. 3.
• textsms

[이코테]순차탐색과 이진탐색

순차 탐색 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. #순차 탐색 코드 def sequentail_search(n,target,array): #각 원소를 하나씩 확인하며 for i in range(n): #현재의 원소가 찾고자 하는 원소가 동일한 경우 if array[i] == target: return i+1 #현재의 위치 변환(인덱스는 0부터 시작하므로 1더하기) print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열..

• format_list_bulleted Algorithm
• · 2020. 11. 17.
• textsms

[이코테]계수정렬

계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 모든 데이터가 양의 정수인 상황이라면 , 데이터의 개수가 N , 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 다만 계수 정렬은 이처럼 매우 빠르게 동작할 뿐만 아니라 원리 또한 매우 간단하다. 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬이 이러한 특징을 가지는 이유는, 계수 정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 리스트를 선언'헤야 하기 때문이다. 계수 정렬은..

• format_list_bulleted Algorithm
• · 2020. 11. 16.
• textsms

[이코테]정렬알고리즘의 개요

정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다. 숫자가 하나씩 적힌 카드가 10장 있다면, 이 카드를 오름차순으로 정렬해보자. 어떻게 이 카드들을 정렬할 수 있을까? 보통은 카드를 훑은 후 숫자를 0부터 0까지 구성된 걸 확인하고 순차적을 나열할 것이다. 하지만 컴퓨터에게는 쉬운 작업이 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다. 정렬 알고리즘은 다음과 같은 기준으로 분류된다..

• format_list_bulleted Algorithm
• · 2020. 11. 15.
• textsms

<