All Categories

계수 정렬 (Count Sort) 은 매우 빠른 정렬 알고리즘이다. 그러나 한 가지 치명적인 약점이 있는데 바로 특정한 조건이 부합할 때만 사용할 수 있다는 것이다. 그 약점은 바로 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능하다' 라는 것이다. 만약 데이터가 무한한 범위를 가질 수 있는 실수형 데이터라면 이 계수 정렬을 사용하기 힘들다는 것이다. 또한 일반적으로 가장 작은 데이터와 가장 큰 데이터의 값의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 즉, 앞서 다루었던 정렬 알고리즘과는 다르게 직접 데이터의 값을 비교한 뒤에 위치를 변경하는 정렬 방식..

퀵 정렬 (Quick Sort) 는 매우 빠른 정렬 알고리즘으로 널리 알려져 있으며 대부분 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬이란 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 정렬을 진행하는 알고리즘이다. 퀵 정렬에서는 기준이 필요하다. 이 기준은 피벗 (Pivot) 이라고 부른다. 먼저 피벗을 설정하고 피벗보다 큰 수와 작은 수를 교환한 후 리스트를 반으로 분할하는 방식으로 진행된다. 피벗을 선정할 때는 명확한 기준이 필요하고 그 기준을 명시해야 한다. 리스트의 첫 번째 데이터를 피벗으로 설정하는 호어 분할 (Hoare Partition) 방법으로 퀵 정렬을 이해한다. 먼저 아래와 같은 데이터가 있다고 가정한다. 5 7 9 ..

삽입 정렬 (Insertion Sort) 는 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하여 정렬하는 알고리즘이다. 따라서 삽입 정렬 또한 선택 정렬과 마찬가지로 직관적으로 동작원리를 이해하기 쉬운 알고리즘이라고 할 수 있다. 삽입 정렬은 선택 정렬에 비해 구현 난이도가 다소 높은 편이지만 실행시간 측면에서 더 효율적인 알고리즘으로 알려져 있다. 또한 필요할 때만 위치를 바꾸기 때문에 '데이터가 거의 정렬 되었을 때' 사용하면 그 효율은 배가 된다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 아래와 같은 데이터를 삽입 정렬을 통해서 정렬하는 모습을 보자. 7 5 9 0 3 1 6 2 4 8 삽입 정렬은 두 번째 데이터부터 ..

먼저 코딩 테스트의 중요 알고리즘 중 하나인 정렬에 대해서 알아보자. 정렬이란 말 그대로 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 프로그램에서 주어진 데이터를 정렬하고 사용하는 경우가 많기 때문에 프로그램을 작성할 때 자주 사용되는 알고리즘 중 하나이다. 또한 정렬 알고리즘이 중요한 이유 중 하나는 이진 탐색의 전처리 과정이기 때문이다. 선택 정렬 (Selection Sort) 란 데이터가 무작위로 나열되어 있을 때, 이 중에서 가장 작은(혹은 가장 큰) 데이터를 가장 앞의 데이터와 바꾸고, 두 번째로 작은 데이터를 두 번째에 위치한 데이터와 계속 바꾸는 방법으로 데이터를 정렬하는 알고리즘이다. 선택 정렬은 가장 원시적인 방법으로 매번 '가장 작은 데이터를 선택한다'는 의미에서 이..

문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건) 첫째 줄에 두 정수 N, M(4

문제) N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라. 다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다 입력 조건) 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1

BFS 알고리즘은 너비 우선 탐색이라는 의미를 갖고 있다. 말 그대로 가장 가까운 노드부터 탐색해가면서 탐색 범위를 넓혀 나가는 개념이다. DFS는 가장 깊은 노드까지 탐색하고 되돌아가서 다른 경로를 택하는 방법을 취한 것과는 반대로 동작한다는 뜻이다. BFS는 큐를 사용해서 선입선출 (FIFO) 의 방식을 사용한다. 인접 노드를 큐에 삽입하고 먼저 들어온 노드가 먼저 큐에서 나가게 되면서 인접한 노드부터 차례대로 탐색을 할 수 있는 것이다. BFS의 동작과정은 다음과 같다. BFS 동작과정 1. 탐색을 시작하는 노드를 큐에 삽입하고 방문 처리 한다. 2. 큐에서 가장 앞에 있는 노드를 꺼내서 그 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다. 3. 과정2를 더 이상 반복..

DFS (Depth-First Search)란 깊이 우선 탐색의 약자로 그래프의 탐색(traversal, 순회) 방법 중 하나이다. 이 탐색 알고리즘은 말그대로 특정한 경로로 노드를 탐색하다가 가장 깊은 곳까지 탐색하고 경로를 다시 돌아가 다른 경로로 탐색하는 방식을 보인다. 구체적인 DFS의 동작 과정은 아래와 같다. DFS의 동작과정 1. 탐색을 시작하는 노드를 스택에 삽입하고 방문 처리한다. 2. 스택의 최상단 노드에 인접한 노드가 있을 때 아래와 같은 경우에 나누어서 처리한다. 2-1. 인접 노드 중 방문하지 않은 노드가 존재할 때, 그 노드를 방문하고 스택에 삽입, 방문 처리한다. 2-2. 인접 노드 중 방문하지 않은 노드가 존재하지 않을 때, 스택의 최상단 노드를 꺼낸다. 3. 과정2를 더 이..