알고리즘

알고리즘이란 어떠한 문제를 해결하기 위한 일련의 수행 과정이다. 실제 개발에 자주 등장하며, 그렇기에 프로그래머에게는 피할 수 없는 숙명이다. 알고리즘을 사용함으로써 우리는 효율적인 개발이 가능해진다. 이러한 효과를 발휘하기 위해서는 다음과 같은 조건을 만족해야 한다.

정렬(Sort) 문제는 알고리즘 공부의 가장 기초가 된다. 이는 효율성 또는 시간 복잡도의 차이를 명확하게 보여주기 때문이다."3 1 2 9 8 4 7 10 5위 숫자들을 오름차순으로 정렬하라."이 문제에서 가장 간단한 해결 방법은 정렬하지 않은 숫자들 가운데 가장 작

이번 글에서는 이전의 선택 정렬과 유사한 또 하나의 기초적이고 간단한 정렬 방법인 버블 정렬을 소개하고자 한다. 또한, 선택 정렬과 비교하며 알고리즘의 효율성에서 어떤 차이를 가지는지 알아보고자 한다.

삽입 정렬은 앞선 선택 정렬, 버블 정렬과 같이 O(N^2)의 시간 복잡도를 가지는 알고리즘이다. 하지만 이 세 가지 알고리즘 중에서는 가장 효율적인 알고리즘이다. 그 이유에 대해 한번 알아보겠다."3 1 2 9 8 4 7 10 5 6위 숫자들을 오름차순으로 정렬하라.

지금까지는 시간 복잡도 O(N^2)을 가지는 정렬을 다루어보았다. 하지만, 이러한 정렬 알고리즘은 데이터의 양이 방대해질수록 처리 속도가 느려지기에 그 성능이 떨어진다. 이를 보완할 수 있는 알고리즘이 바로 퀵 정렬이다."3 1 2 9 8 4 7 10 5 6위 숫자들을

너비 우선 탐색은 말 그대로 탐색을 수행하는 알고리즘으로, 너비를 우선으로 한다. 이는 최단 경로 탐색에 많이 사용되며, 자료구조 중 큐(queue)를 사용한다는 특징이 있다.

깊이 우선 탐색은 너비를 우선으로 했던 너비 우선 탐색과 달리 깊이를 우선적으로 수행하는 탐색 알고리즘이다. 너비 우선 탐색과 달리 스택(stack)을 사용한다는 특징이 있지만, 사용하지 않고 구현할 수도 있다.

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘으로, 네비게이션과 같은 SW에서 많이 사용된다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그

플로이드 와샬 알고리즘은 지난 글에서의 다익스트라 알고리즘과 같은 최단 경로 탐색 알고리즘 중 하나이다. 이번 글에서는 플로이드 와샬 알고리즘에 대해 알아보고자 한다.다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이었다. 하지

A* 알고리즘은 최단 경로 찾기 알고리즘으로, 다익스트라 알고리즘과 유사하지만 시작 노드에서 특정 노드로 도착하는 최단 경로를 찾는다는 점에서 차이가 있다. 휴리스틱 추정값을 통해 알고리즘을 개선할 수 있으며, 그 방식에 따라 성능이 결정된다.

"1 3 5 7 9 11 13 15 17 19에서 13는 몇 번째 위치에 존재하는가?"이 문제에서 숫자들은 정렬되어 있는 상태이다. 이때 배열을 반씩 나누어 탐색을 하게 되면 첫 번째 숫자부터 탐색하는 것보다 빠르게 탐색할 수 있게 된다. 이러한 방법을 이분 탐색이라