소개 병합 정렬(Merge Sort)은 대표적인 분할 정복(Divede and Conquer) 알고리즘 중 하나로, 리스트를 반으로 나눈 뒤 각각을 재귀적으로 정렬하고, 정렬된 두 개의 리스트를 합쳐서 정렬된 하나의 리스트를 만드는 알고리즘입니다. 작동 개념💡 병합 정렬은 일반적으로 다음과 같은 세 단계로 구성됩니다. 분할(Divide): 입력 리스트를 같은 크기의 두 개의 부분 리스트로 분할합니다. 이때 분할은 리스트의 중간 지점에서 수행됩니다. 정복(Conquer): 각 부분 리스트를 재귀적으로 병합정렬을 이용해 정렬합니다. 이 과정은 입력 리스트의 크기가 충분히 작아질 때까지 반복됩니다. 병합(Merge): 정렬된 두 부분 리스트를 하나의 정렬된 리스트로 병합합니다. 0개 요소, 1개 요소 배열이 ..

소개 간단하고 직관적인 정렬 알고리즘 중 하나입니다. 배열의 원소를 순서대로 탐색하며, 각 원소를 이미 정렬된 배열 부분과 비교하여 적절한 위치에 삽입하는 방식으로 정렬을 진행합니다. 대부분의 경우 다른 고급 정렬 알고리즘보다 성능이 떨어지기 때문에 매우 큰 배열이나 시간제한이 있는 경우에는 다른 정렬 알고리즘을 사용하는 것이 좋습니다. 예제 코드 // 첫 번째 방법 function insertionSort(array) { for (let i = 1; i = 0 && array[j] > current) { array[j + 1] = array[j]; j--; } array[j ..

소개 주어진 리스트에서 가장 작은 값을 선택하여 맨 앞에 위치시키고, 그다음으로 작은 값을 찾아 두 번째 위치에 위치시키는 과정을 반복하여 정렬하는 알고리즘입니다. 앞으로 보내진 원소는 더 이상 위치가 변경되지 않습니다. 기본 개념 선택 정렬은 간단하면서도 이해하기 쉽고 코드 구현이 쉬운 알고리즘이지만, 그만큼 시간 복잡도가 높아 대규모 데이터를 정렬할 때는 성능이 떨어지는 단점이 있습니다. 선택 정렬의 시간 복잡도는 O(N^2)으로, 입력 데이터의 크기가 커질수록 성능 저하가 더욱 심해집니다. 예제 코드 function selectionSort(arr) { const n = arr.length; for (let i = 0; i < n - 1; i++) { let minIndex = i; for (let..

소개 버블 정렬(Bubble Sort)은 가장 간단하고 기본적인 알고리즘 중 하나로, 이름에서도 알 수 있듯이 배열의 요소를 '거품(Bubble)'처럼 서로 교환해 가며 정렬하는 방식입니다. 즉, 서로 인접한 두 원소를 비교해가며 오름차순이나 내림차순으로 정을 진행합니다. 기본 개념 버블 정렬의 개념은 만약 숫자 배열을 오름차순으로 정렬하는 상황에서 더 큰 숫자가 한 번에 하나씩 뒤로 이동하는 방법입니다. 기본적으로 어떤 항목이 더 크면 교환하고, 다음 항목과 비교하고, 다음 항목보다 더 크면 또 교환을 하고, 다시 다음 항목과 비교하면서 반복을 합니다. 오름차순의 상황에서는 가장 큰 값이 상단을 향해서 값을 정렬하는 방식으로 목록을 만듭니다. 예제 코드 #1 function bubbleSort(arr)..

난이도: 골드 4 풀이 알고리즘: BFS 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할..

난이도: 골드 3 풀이 알고리즘: BFS 문제 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈..

난이도: 골드 2 풀이 알고리즘: BFS 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다. 출력 첫째 줄에 1번역에서 N번역으로 가는데 방문하는 역의 개수의 최솟값을 출력한다. 만약, 갈 수 없다면 -1을 출력한다. 예제 입력 1 9 3 5 1 2 3 ..

문제 NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과..

문제 👀 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11개..