algorithm

문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50) 다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다. 사탕의 색이 다른 인접한 두 ..

문제 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다. 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오. 입력 첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째..

Shell Sort란? Insertion Sort를 기반으로 합니다. 서로 멀리 떨어져 있는 순자들을 정렬(insertion sort로)하기 시작하여 점점 두 숫자들 사이의 거리(gap)을 좁혀서 정렬합니다. 최종적으로 gap=1이 되면, 원래의 insertion sort를 실행하는 것과 동일합니다. Not stable하며 In-place 알고리즘 입니다. Gap, Gap Sequence Gap 정렬할 원소들이 떨어져 있는 거리입니다. 처음에는 큰 gap을 사용하여 시작하지만, 점점 작게 만들고, 최종적으로는 1이됩니다. Gap Sequence 주어진 시작 숫자부터 gap만큼 떨어진 모든 숫자들의 집합입니다. 같은 gap sequence에 속하는 숫자들을 insertion sort로 정렬합니다. Pass..

Insertion Sort란? Selection Sort처럼 정렬 중간 과정에 데이터가 두 부분으로 나눠 집니다. Stable하며 In-place한 정렬입니다. 왼쪽에는 정렬이 된 데이터입니다. 오른쪽은 정렬이 되지 않은 데이터입니다. 오른쪽 데이터의 제일 앞 숫자를 그 왼쪽의 정렬된 데이터의 제 위치에 삽입합니다. 중간의 모든 데이터는 오른쪽으로 한 칸씩 이동합니다. Insertion Sort sorting 과정 Insertion Sort 코드 #include using namespace std; #define MAX_SIZE 1000 void insertionSort(int a[], int n); int main() { int numTestCases; scanf("%d", &numTestCases);..

Selection Sort란? 기본 아이디어 정렬 중간 과정에서 데이터가 두 부분으로 나누어집니다. 왼쪽 데이터는 정렬이 된 데이터 오른쪽 데이터는 정렬이 되지 않은 데이터 Not stable한 알고리즘이면서 In place 알고리즘입니다. 오른쪽 데이터에서 제일 작은 데이터를 검색하여 선택하고 오른쪽 데이터의 제일 앞 숫자를 그 숫자랑 교환합니다. 정렬 과정 Selection Sort 코드 #include #include #define MAX_SIZE 1000 using namespace std; void selectionSort(int a[], int n); int main() { int numTestCases; scanf("%d", &numTestCases); for (int i = 0; i < n..

Bubble Sort Algorithm 정렬 알고리즘 중 기본적인 알고리즘 중 하나로 인접한 두 숫자를 비교하여 두 수의 정렬 순서가 맞지 않은 경우에 swap을 하는 알고리즘입니다. 마치 깊은 물속의 큰 물방울이 표면으로 떠 오르는 것과 같이 큰 데이터들이 배열의 왼쪽에서 오른쪽으로 이동하기 대문에 bubble sort라고 부른다고 합니다. 해당 알고리즘은 stable한 Algorithm이면서, In-Place한 Algorithm입니다. Stable: 정렬 이후 입력된 순서 그래도 유지가 되는가? In-place: 데이터를 저장하는 메모리 이외는 상수 크기의 메모리만 필요하는가? 평균적인 시간 복잡도는 O(n^2)입니다. Pass 맨 왼쪽 인접한 두 숫자를 비교하기 시작합니다 맨 끝 인접한 두 숫자를 ..

이중우선순위큐 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어 수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의 원소는 큐가 수행할 연산을 나타냅니다. 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우..

땅따먹기 문제 설명 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다. 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네..

플로이드 워셜 알고리즘은 최단경로 알고리즘 중 하나로 다익스트라 알고리즘과 더불어 제일 많이 언급되는 알고리즘 중 하나입니다. 최단 경로 알고리즘을 다시 공부하면서 공부했던 내용을 포스팅 하고자 글을 작성하게 됐습니다. 플로이드 워셜 알고리즘이란? 모든 정점 사이의 최단 경로를 찾는 알고리즘입니다. 최단 경로 알고리즘인만큼 최당경로는 길이 순으로 구해집니다. 플로이드 워셜 알고리즘의 과정입니다. 1. 하나의 정점에서 다른 정점을 바로 갈 수 있으면 최소비용을 설정하며, 갈 수 없다면 INF로 무한대 값을 배열에 값으로 저장합니다. 2. 3중 for 문을 통해 거쳐가는 정점을 설정 한 후 해당 정점을 거쳐가서 비용이 줄어든느 경우에는 값을 바꿔줍니다. 3. 위 과정을 계속해서 반복하여 모든 정점 사이의 최..