본문 바로가기
반응형

stack6

[백준/C++] 오아시스 재결합 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 두 사람이 서로 볼 수 있는지 수를 계산하는 문제다. A와 B를 선택해 그 사이에 사람의 키를 비교하기에는 매우 비 효율적이다. 두 사람 사이에 키가 큰 사람이 없기만 하면 서로 마주볼 수 있으므로 이를 이용해 문제를 풀면 된다. 그럼 여기서 두 사람 사이에 키가 큰 사람이 없다는 것은 어떤 의미일까? 잘 생각해보면 A와 B의 사이가 아닌 곳에는 키가 큰 사람이 있어도 된다는 뜻이다. 아래 그림을 한번 보면 A와 B 사이에 키가 큰 사람이 없으므로 A와 B는 볼 수 있다. 이를 이용하면 A의 왼쪽에는 키가 큰 사람이 와도 전혀 영향이 없다는 사실을 알 수 있다. 이제 문제를 푸는 방법은 다음과 같.. 2024. 4. 11.
[백준/C++] 오등큰수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 오큰수 문제와 크게 다른게 없다. HTML 삽입 미리보기할 수 없는 소스 오큰수가 오른쪽에 있는 수 중에서 크면서 가장 가까운 수를 찾는 문제였다면, 오등큰수 문제는 등장하는 횟수를 비교하는 문제다. 즉, 비교하는 게 숫자의 크기가 아니라 등장횟수로 바뀐 것 뿐인 문제다. 처음에 문자가 몇 번 등장했는지를 map이나 array를 이용해 기록한다. 이후 순차적으로 숫자를 비교해 등장 횟수가 i번 째 수보다 큰지 비교하면 된다. 만약 i번째 수와 같거나 작다면 stack에 i번째 숫자를 기록한다. (stack에 i번째 수 추가) 마찬가지로 stack구조를 이용하면 문제를 쉽게 풀 수 있기 때문에 stack.. 2024. 4. 10.
[백준/C++] 오큰수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 i번째 숫자의 오른쪽에 있는 수 중에서 가장 왼쪽에 있는 수를 찾으면 되는 문제다. 즉, i번째 수가 오면 그 수를 기준으로 오른쪽에 큰수가 나오는지 탐색을 하면 되는 문제다. 여기서 문제를 풀 때, 만약 i번째 수마다 오른쪽을 탐색하면 O(n^2)의 시간복잡도가 걸리게 된다. 대신 빠르게 푸는 방법이 있다. 아래 그림과 같이 3, 5, 2, 7의 4개의 숫자의 수열을 예로 들어보자. 처음에 3이라는 숫자가 들어오면 기록을 한다. 아직까지는 3의 왼쪽에 어떤 숫자가 오는지 모른다. 이후 들어오는 숫자는 5다. 여기서 5는 3보다 크기 때문에, 3은 자신보다 오른쪽에 있는 큰 수를 발견한다. 그러므로 3.. 2024. 4. 9.
[백준/C++] 문자열 폭발 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 문자열이 완성되면 삭제를 하고, 뒤에 문자들을 이어 붙이면 되는 문제다. 문제를 풀 때, 앞에서 부터 문자열을 추가해 나가다가 M의 마지막 문자가 나오면, 저장된 문자들을 탐색해 삭제가 되는지 확인했다. 아래 그림을 통해 자세하게 알아보자 M의 마지막 문자인 4가 나왔으므로 4부터 탐색해 문자열 M과 같은지 확인한다. C4로 같았으므로 문자열을 삭제해 준다. 마찬가지로 진행을 하면 아래와 같이 정답이 나오게 된다. 이렇게 하면 문자열을 앞에서부터 n번 탐색해 문제를 해결할 수 있다. 이때 문자를 저장하고 삭제를 하는 방법은 여러가지가 있겠지만, 뒤에 있는 문자부터 빼 사용할 것이므로 stack을 .. 2024. 4. 8.
[프로그래머스/C++] 풍선 터트리기 HTML 삽입 미리보기할 수 없는 소스 n개의 풍선이 일렬로 나열되어 있다고 하자. 이 때, 모든 풍선에는 서로 다른 숫자가 써져 있다.다음 규칙에 따라 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터뜨리려고 한다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터뜨린다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생기면, 빈 공간이 없도록 풍선들을 중앙으로 밀착 시킨다 여기서 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터뜨리는 행위는 최대 1번만 할 수 있도록 제한 되어있다.즉, 한번이라도 인접한 두 풍선 중 번호가 더 작은 풍선을 터뜨리면 이후에는 번호가 큰 풍선만 터뜨려야 한다. 이 규칙에 따르면 어떤 풍선은 어떤 방법을 쓰더라도 절대 마지막까지 남길 수 없다. 이때, 최후까지 남.. 2024. 1. 5.
[백준/Python] 6549번 - 히스토그램에서 가장 큰 직사각형 HTML 삽입 미리보기할 수 없는 소스 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. HTML 삽입 미리보기할 수 없는 소스 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는.. 2024. 1. 4.
반응형

티스토리툴바