코딩테스트

[백준] 문자열 폭발

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net https://life318.tistory.com/68 [백준] 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크 life318.tistory.com 한번 파이썬으로 해결한 ..

[백준] 히스토그램에서 가장 큰 직사각형

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net stack을 이용하는 문제입니다. 다양한 풀이들이 많이 있는 문제로 유명하다고 하는데, 다른 방식들을 또 알게되면 추가해 보도록 하겠습니다. 우선 문제부터 간단하게 요약하면, 그림과 같이 히스토그램이 위치할 때, 히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제입니다. 이 때, 직사각형의 수는 10만개 까지, 그리고 각각의 높이는 0부터..

[백준] 택배

https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 그리디 알고리즘을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 용량이 정해진 택배 트럭이 마을마다 물건을 배송합니다. 이 때, 보내는 마을, 받는 마을, 박스 개수가 주어질 때, 트럭 한대로 배송할 수 있는 최대 박스 수를 구하는 문제입니다. greedy 알고리즘을 활용해야 하는 문제입니다. 간단한 예시로 문제를 살펴봅시다. [INPUT] 4 40 6 3 4 20 1..

[백준] 색종이 - 3

https://www.acmicpc.net/problem/2571 2571번: 색종이 - 3 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net N^6 로직을 활용하여 해결하였습니다. 우선 문제부터 간단하게 요약하면, 흰 도화지 위에 검정 색종이를 붙입니다. 이 때, 검정색 부분을 가장 큰 직사각형 모양으로 잘라내고 싶을 때, 잘라낼 수 있는 가장 큰 넓이를 구해야 합니다. 도화지의 크기가 크지 않으므로, 시작지점(N^2)과 끝지점(N^2)을 찾아서, 해당하는 구간이 모두 검정색이 맞는지 탐색(N^2)을 하면서 만약 맞다면 area의 넓이를 ..

[백준] Cow Lineup

https://www.acmicpc.net/problem/5926 5926번: Cow Lineup Input Details There are 6 cows, at positions 25,26,15,22,20,30, with respective breed IDs 7,1,1,3,1,1. Output Details The range from x=22 up through x=26 (of total size 4) contains each of the distinct breed IDs 1, 3, and 7 represented in FJ's herd. www.acmicpc.net 투포인터 알고리즘을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 소의 좌표와, 품종아이디가 들어옵니다. 좌표는 x좌표로 사진을 ..

[백준] 나룻배

https://www.acmicpc.net/problem/2065 2065번: 나룻배 강을 사이에 두고 위치한 두 정박장 사이를 한 대의 나룻배가 오가고 있다. 두 정박장은 강을 기준으로 왼쪽(left), 오른쪽(right)으로 구분한다. 제일 처음에는 나룻배가 왼쪽 정박장에 위치해 있 www.acmicpc.net 큐, 구현, 시뮬레이션 문제입니다. 우선 문제부터 간단하게 요약하면, 강을 사이에 두고 나룻배가 이동을 하게 됩니다. 이동에는 t의 시간이 걸리고, 만약 정박지에 도착하게 되면 태운 손님을 모두 내려주고, 만약 탈 손님이 있다면 태우고 이동합니다. 만약 도착한 정박지에 손님이 없다면, 그 정박장에서 손님을 기다리고, 이 때 반대쪽 정박장에 손님이 온다면, 그 정박장으로 이동하게 됩니다. 문제의..

[백준] 오타

https://www.acmicpc.net/problem/5875 5875번: 오타 올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키 www.acmicpc.net 문제부터 간단하게 요약하면, 괄호의 입력이 들어오면, 하나의 문자만 고쳐서 올바른 괄호쌍이 될 수 있는 경우의 수를 출력해야 합니다. ()(()))) 의 input의 경우, 2번째, 5번째, 6번째, 7번째 문자를 고치는 경우에 올바른 문자열이 되므로 4를 출력해야 합니다. 기본적으로 괄호와 관련한 문제는 depth를 사용합니다. ( ) ( ) ) ) ) 의 예시에서 depth를 생각해보면, 1 0 1 0 1 2 ..

[백준] 고기잡이

https://www.acmicpc.net/problem/7573 7573번: 고기잡이 한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고 www.acmicpc.net 문제부터 간단하게 요약하면, 그물의 크기가 주어질 때, 가장 많은 물고기를 잡을 수 있는 경우, 몇 마리를 잡을 수 있는지를 구해야 하는 문제입니다. 일단 그물의 종류별로 확인을 해야 하는 것은 당연합니다. 예를 들면 길이 10인 그물이 주어진다면, 1x4, 2x3, 3x2, 4x1 의 그물 종류에 대해 모두 확인해야 하는 것은 당연합니다. 하지만 모든 점에 대해 이 그물 종류들을 모두 조사하게 된다면, 시간..