https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 문제다. 8개월 전에도 이 문제를 만났었다. 그 때는 벡터를 이용해 넣을 때마다 정렬하고 중앙값을 뽑아내는 작업으로 당연히 시간초과가 났다. 그리고 오늘 이 문제를 다시 만났다. 이 문제가 우선순위 큐를 이용한다는 것은 알고 있었다. 그러나 시간 복잡도를 계산했을 때 1000만이 넘어가 0.1초 보다 더 걸릴 것이라고 생각했다. 그리고 시간이 그렇게 걸릴 뿐만 아니라 ..
Algorithm/Data Struct
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 스택 자료구조 문제다. N자리 숫자에서 K개를 지워서 만들 수 있는 가장 큰 수를 찾는 문제다. 앞에서부터 순회해 스택에 숫자를 push한다. push 할 숫자가 stack에 들어있는 숫자보다 크다면 pop을 한다. 스택의 top보다 값이 작을 때까지 or k 범위 내에서 pop을 반복한다. 위 작업이 끝나면 스택에 남은 값들을 pop하면서 남은 문자열과 합쳐 답을 구한다. #include #include using namespace std; int n, m; int arr..
https://www.acmicpc.net/problem/1999 1999번: 최대최소 첫째 줄에는 세 정수 N, B, K가 주어진다. 다음 N개의 줄에는 행렬이 주어진다. 차례로 1행, 2행, …, N행이 된다. 각 줄에는 N개의 정수가 주어지며, 이는 차례로 1열의 성분, 2열의 성분, …, N열의 성 www.acmicpc.net 자료구조 문제다. N x N 행렬에서 B x B 크기 만큼에서 최대 최소를 찾아 그 차를 구하는 것이다. 모든 질문에 대해 B의 크기가 같다는 것을 못 보고 DP를 활용해 각각 최대 최소를 저장하는 배열을 만들려 했다. 그러나 B의 크기가 항상 동일하다는 것을 알고 DP가 아니라는 것을 알았다. 범위의 크기를 보니 무지성으로 탐색을 해도 괜찮을 것 같았다. 주의할 점은 중복..
https://www.acmicpc.net/problem/15926 15926번: 현욱은 괄호왕이야!! 첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다. www.acmicpc.net 스택 문제다. 올바른 괄호 부분 문자열 중 길이가 가장 긴 것을 찾는 것이다. 처음에는 일반 괄호 짝 맞추기처럼 여는 괄호는 스택에 넣고 닫는 괄호를 만나면 스택에서 여는 괄호를 빼는 방법을 택했다. 이 때, 스택에 넣고 뺄 때마다 카운트를 했다. 닫힌 괄호를 만났을 때 스택이 비어 있으면 해당 사이즈 만큼 카운트를 줄였다. ((() 와 같이 열린 괄호가 많은 경우 반례가 생..
https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 스택 자료구조 문제다. 이 문제를 볼 때마다 뭘 구하라는 건지 이해가 안돼서 패스했었는데 드디어 이해하고 해결했다. 스카이라인의 높이가 바뀌는 경우 좌표가 주어진다. 모든 칸을 커버하는 최대의 직사각형 개수를 구하는 문제라고 판단했다. 스택 문제긴 하지만 스택을 이용하지 않았다. 높이가 바뀌는 지점이 순서대로 입력되므로 입력받는 대로 결과를 처..
https://www.acmicpc.net/problem/2179 2179번: 비슷한 단어 첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다. www.acmicpc.net 문자열 문제다. 두 단어의 비슷한 정도를 접두사의 길이로 비교하여 가장 비슷한 두 단어를 찾는 문제다. 답으로 S와 T라는 문자열을 출력한다고 했을 때, 우선 순위는 먼저 입력된 순이다. S와 T가 될 수 있는 문자열이 여러개라면 가장 앞쪽에 위치한 단어가 S, S가 같다면 T를 기준으로 판단한다. 접두사의 공통부분을 찾기 위해 입력단에서 문자열과 인덱스를 벡터에 저장했다. 벡터에 저장한 이유는 정렬을 위해서다. 정렬을 하면 인접한 문자..
