문제 풀이/백준 알고리즘

[baekjoon 2800] 괄호 제거 (스택, 구현, 재귀) (C++)

https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 주어진 문자열에서 괄호 쌍을 제거해서 만들 수 있는 문자열을 모두 출력하는 문제이다. 괄호가 3쌍이 있다면, 0 1 2 01 02 12 012를 지울 수 있다. 그래서 조합을 통해 숫자들을 만들고, 저 번호에 해당하는 괄호의 쌍을 지우면 되겠다고 생각을 했다. 처음에 아무 생각 없이 (1+(2*(3+4))) 이런 경우만 생각해서 그때마다 괄호의 개수를 세서 괄호를 ..

[baekjoon 2696] 중앙값 구하기 (우선순위 큐) (C++)

https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 어떤 수열을 읽고, 홀수번째 수를 읽을 때마다, 지금까지 입력받은 값의 중앙값을 출력하는 문제이다. 수가 입력될 때마다, 정렬해서 입력받은 값을 출력하기보다 우선순위 큐를 이용하면 매번 정렬 대신 전체 데이터를 nlogn만에 풀이가 가능하다. maxHeap은 top에 가장 큰 값이 저장되고, minHeap은 top에 가장 작은 값이 저장된다. minHeap과 maxHe..

[baekjoon 12904] A와 B (문자열, 그리디) (C++)

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 시작 단어에서 뒤에 A를 붙이거나, 단어를 뒤집어서 B를 붙이거나 해서 목표 단어까지 만들 수 있는지의 여부를 계산해내는 문제이다. 처음엔 아무 생각 없이 DFS로 매번 A를 붙이거나, B를 붙였더니 시간 초과가 났다. 그도 그럴 것이, 시작 단어가 1글자에서 시작하고 목표 단어가 1000 글자면 매 단계마다 2번 ^ 1000이다. 4글자 단어를 만드는데 2^..

[baekjoon 3079] 입국심사 (매개변수탐색, 이분탐색) (C++)

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 심사대의 개수와 심사를 할 사람 수가 주어진다. 각 심사대에서 걸릴 수 있는 시간은 최대 10^9이고, 총 10만 개가 있다. 매개 변수 탐색을 통해서 우리가 찾으려는 값은 최종 걸리는 시간이다. 만약 자리가 1 2 3 4 5가 있고, 최종 걸리는 시간이 10이라고 가정한 상황이면 총 10의 시간 동안 몇 명이 앉을 수 있을까? 1의 자리에 10명, 2의 자리에 5명, 3의 자리에 ..

[baekjoon 2075] N번째 큰 수 (우선순위큐, 정렬) (C++)

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이런 표가 주어지고, 같은 열에 있는 수는 아래로 갈수록 커지는 특징이 있다. 이런 수의 구성 중에서 N번째 큰 수를 찾는 것이다. 이 문제의 메모리 제한은 4MB로, 모든 수를 입력받아서 정렬 후 N번째를 찾는 방법은 메모리 초과가 날 것으로 예상되었다. (N은 1500개까지) 따라서, 우선순위 큐나 벡터+정렬을 이용해서 한 줄을 입력받고 정렬한다. 이후에, 거기서 N개의 수만 남기고 모두 pop 한다..

[baekjoon 11659] 구간 합 구하기 4 (누적합) (C++)

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 기본적인 누적합 문제이다. 누적합 문제를 최근에 안 풀었더니 투 포인터로 접근했다가 시간 초과가 났다. 입력을 받으면서 앞의 인덱스의 누적 합을 따로 저장해준다. 그러면 start와 end의 구간 합을 sum[end] - sum[start-1]의 식으로 O(1)에 구할 수 있다. 여기에 쿼리가 추가되어 값이 수정되면서 구간 결과을 구하려면 세그먼트 트리 문제로 된다. 수많은..