알고리즘

[Silver II] N번째 큰 수 - 2075 문제 링크 성능 요약 메모리: 149928 KB, 시간: 680 ms 분류 자료 구조, 우선순위 큐, 정렬 문제 설명 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고..

[Silver II] 최대 힙 - 11279 문제 링크 성능 요약 메모리: 70668 KB, 시간: 736 ms 분류 자료 구조, 우선순위 큐 문제 설명 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. ..

[Silver IV] 괄호 - 9012 문제 링크 성능 요약 메모리: 69100 KB, 시간: 8 ms 분류 자료 구조, 스택, 문자열 문제 설명 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 V..

LCS LCS란 보통 최장 공통 부분수열(Longest Common Subsequence)을 의미하지만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. 여기에서 부분수열(Subsequence)과 문자열(Substring)의 차이는 문자열이 연속적인지 아닌지에 따라 달라지는데요, 연속적이라면 문자열(Substring)이고, 비연속적이면 부분수열(Subsequence)입니다. 다음과 같은 예시가 있다고 가정해봅시다. [AUTABBEHNSAAB, BCUAMEFKAJNAAB] 위 예시에서 AAB는 연속적이기 때문에 문자열이라고 할 수 있고, UAENAAB는 비연속적이기 때문에 부분 수열이라고 할 수 있습니다. 위에서 말한 두 가지의 LCS를 구현하는 방법에 대해 알아보겠습니..