2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 예제 5 6 9 5 7 4 ans : 0 0 2 2 4 문제를 풀 때 사용할 수 있는 조건들을 생각해 보자. 1. 첫 번째 탑은 무조건 수신할 탑이 없다. 2. 두 번째 이후의 탑은 자신보다 큰 탑 중 왼쪽 방향으로 가장 가까운 탑이 수신한다. 이 조건을 보고 스택을 떠올렸다. 스택을 메인 알고리즘으로 사용한 이유는 가장 최근에 들어온 데이터 중 조건에 맞는 데이터를 빼야 하는 조건부 후입선출 문제이기 때문이다. 처음에는 자신보다 높은 탑을 스택에서 고르기 위..

24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 예제 5 7 4 5 1 3 2 ans : 3 -------------------- 5 13 4 5 1 3 2 ans : -1 병합정렬만 구하면 풀리는 문제다. K 번째 저장되는 수라는 말이 조금 헷갈리는데 간단하게 주어진 퍼수도코드대로 구현했을 때 병합 결과를 저장하는 부분에서 K 번째 저장되는 수를 구하면 된다. 병합 정렬을 공부하고 특징, 장단점을 숙지하면서 구현해 보기 좋은 문제이다. /** 정렬 24060 알..

시뮬레이션 문제는 어려운 구현, 노가다 느낌이 강한 문제들로 N * N 크기의 판에서 길 찾기를 하거나 간단한 게임을 구현하고 그 속에서 시뮬레이션을 돌려보는 느낌의 문제이다. 시뮬레이션 알고리즘은 정렬이나 그래프, 동적 계획법처럼 일반화하여 상황에 맞게 그 알고리즘을 사용하는 느낌은 아니다. 문제를 정확히 이해하고 문제를 부분 문제로 나누어서 차근차근 독립적인 함수로 구현하는 편이 디버깅하기도 좋고 예외처리에도 용이하다. 기본적으로 알아야 할 몇 가지 배경지식 외에는 본인의 구현력이 가장 중요하다. 행렬의 연산과 좌표계를 다루는 것만 알면 나머지는 구현의 문제이다. 행렬 연산 행렬 덧셈/뺄셈 행렬의 덧셈과 뺄셈은 간단하게 각 행렬의 동일한 위치에 있는 값들끼리 연산해 주면 된다. 당연히 두 행렬의 크기..

스택 스택은 가장 최근에 삽입된 원소가 삭제되는 LIFO구조이다. 스택의 top에서 원소의 삽입과 삭제가 일어난다. 스택에서 필수적으로 지원해야 할 메서드를 보자. ​ Stack-Empty Stack-Empty(S){ if(S.top==-1) return 1; else return 0; } Push Push(S, x){ S.top++; S[S.top] = x; } Pop Pop(S){ S.top--; return S[S.top+1]; } 큐 큐는 가장 먼저 삽입된 원소가 먼저 삭제되는 FIFO구조이다. 큐의 front에서 삭제가 일어나고 rear에서 삽입이 일어난다. 큐를 그냥 배열로 사용하게 되면 큐가 메모리에서 마치 빙하처럼 점점 이동한다는 문제점이 생긴다. 데이터의 삽입/삭제가 반복되면 인덱스가 감..

특정 상황에서 비교를 하지 않고 정렬을 함으로써 O(n) 시간 내에 정렬을 할 수 있다. 계수정렬(Counting Sort) 원소의 값이 한정적으로 0 ~ k의 자연수로 제한되어 있는 경우 사용 가능하다. 각 입력원소 x에 대해 x보다 작은 원소의 개수를 센다. 그리고 원소 x의 위치를 정한다. 예를 들어 x보다 작은 원소가 17개라면 x를 18번째 자리에 위치시킨다. 입력 배열 A와 출력을 저장할 배열 B, 임시 작업 공간 배열 C를 사용한다. ​ CountingSort(A, B, k){ vector C(k, 0); for j=1 to A.length C[A[j]]++; //C[i]는 값이 i인 원소의 개수이다. for j=1 to k C[j]+=C[j-1]; //C[i]는 이제 값이 i보다 작거나 같..

퀵 정렬 평균적으로 가장 좋은 성능을 가졌다. 기준 원소를 잡고 기준 원소를 기준으로 양쪽으로 재배치하면서 정렬한다. 퀵정렬 또한 Divide-and-conquer을 이용한다. ​ 분할 : 배열 A [p.. r]을 두 개의 부분 배열 A [p.. q - 1], A [q + 1.. r]로 분할한다. 전자는 A [q]보다 작거나 같은 원소를, 후자는 A [q]보다 크거나 같은 원소를 배치한다. ​ 정복 : 퀵 정렬을 재귀 호출해서 두 부분 배열을 퀵정렬한다. ​ 결합 : 부분 배열이 이미 정렬되어 있으므로 저절로 합쳐져 있다. 기본적인 알고리즘은 이렇고 자세한 구현은 코드로 보자. QuickSort(A, p, r){ if(p < r) q = Partition(A, p, r) QUICKSORT(A, p, q-..