본문 바로가기
728x90

스택

[백준알고리즘] 2104번: 부분배열 고르기-C++ 2104번: 부분배열 고르기 (acmicpc.net) 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 문제를 푸는데 되게 오래걸렸다. 처음에는 세그먼트 트리를 오랜만에 공부하려고 시작한 거라, 공부하는데 시간이 소요됐다. 그러고 나서는 어떻게 적용되면 좋을지 고민하느라 시간이 소요됐다. 마지막으로, 알 수 없는 '틀렸습니다'의 늪에서 헤어나오지 못했다. 게다가 하루에 30분 저도씩 밖에 시간을 못 쓰는 바람에 며칠이 걸.. 더보기
[백준알고리즘] 6549번: 히스토그램에서 가장 큰 직사각형-C++ 6549번: 히스토그램에서 가장 큰 직사각형 (acmicpc.net) 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 보니까 2년 전에 풀다가 말았던 문제인 것 같다. 파이썬으로 풀려고 시도했던 흔적이 남아있다. 플레티넘 5라고 해서 너무 쉬운 방법은 안 풀릴 거 같았다. 조금 생각해서 스택을 이용해 푸는 방법을 생각했고, 약간 지저분해 보여 조금 아이디어를 가다듬고 문제를 풀었다. 사실 바로 풀릴지 모르고 했는데 돼서 놀랬다. 해당 문제에 대한 게시판.. 더보기
[백준알고리즘] 10799번: 쇠막대기 -Python, C++ [백준알고리즘] 10799번: 쇠막대기 -Python, C++ 10799번: 쇠막대기 (acmicpc.net) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 예전에 파이썬으로 풀었다가 쉬웠어서 안올렸던 문제다. 그런데.. 오늘 C++로 풀면서 완전 대참사였다. 계속 '틀렸습니다'가 떠서 이전에 파이썬으로 푼 코드를 봤는데 로직이 같은 개념으로 짠 것인데도 해결이 안 됐다. 이래저래 모두 안되길래 아예 파이썬으로 짰던 로직 그대로 짰는데도 안됐다. 그래서 오늘 C++로 .. 더보기
[백준알고리즘] 2493번: 탑 -Python [백준알고리즘] 2493번: 탑 -Python https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. www.acmicpc.net 문제를 해결하기 위해서는 현재 탑의 바로 직전 탑의 높이만 알아야 하는 것이 아닌 자신이 도달할 수 있는 탑의 위치를 알기 위해서 어느 정도 이전 탑들의 정보가 필요하다. 하지만 탑의 개수도 많고, 높이의 범위도 넓기 때문에 이전에 나왔던 탑들을 모두 검사하는건 시간이 오래 걸릴 수밖에 없다. 그래서 필요.. 더보기
[백준알고리즘] 1874번: 스택 수열 -Java [백준알고리즘] 1874번: 스택 수열 -Java https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 처음에 문제를 이해하는 데 이상했었다. 문제를 설명하자면 1부터 n까지의 수를 차례대로 stack에 push 하거나 pop 해서 주어진 수열을 만들 수 있는가를 물어보는 문제이다. 이에 대해서 문제를 풀기 위해서는 stack에 push할 때의 조건과 pop 시킬 때의.. 더보기
728x90

티스토리툴바