[백준] 17298 오큰수
2023. 1. 13. 19:53
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 크기가 n인 수열이 주어질 때, 수열의 각 원소에 대해서 오큰수를 구하여라 오큰수는 각 원소의 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수이다 그러한 수가 없는 경우에는 -1이다 문제 풀이법 이 문제도 역시 Monotone stack을 사용하면 된다 수열을 담을 vector v monotone stack을 활용할 stack s; 답을 담을 vector ans; 이 3개가 필요하다 우선 수..
[백준] 6198 옥상 정원 꾸미기
2023. 1. 13. 19:23
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net n개의 빌딩이 있고, 오른쪽의 빌딩만 볼 수 있다 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있을 때, 그 다음에 있는 모든 빌딩의 옥상을 보지 못할 때, 관리인들이 옥상 정원을 확인 할 수 있는 수 구하기 문제 풀이법 문제에서 주어지는 문제 풀이 방법를 통해 문제를 풀려면, 풀리지 않는다 Monotone stack을 사용해야 한다 Monotone stack이란? 스택의 원소들을..
[백준] 2493 탑
2023. 1. 12. 19:48
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net n개의 탑이 서로 다른 높이를 가지로 있다. 탑은 수평 직선의 왼쪽 방향으로 레이저 신호를 발사하고, 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신할 수 있을 때, 각각의 탑에서 발사한 레이저 신호는 어느 탑에서 수신하는지 구하기 문제 풀이법 처음에는 굳이 stack을 써야 하나 싶었다 하지만 stack을 써야 하나씩 입력을 받으면서, 바로바로 값을 구..
[백준] 1874 스택 수열
2023. 1. 12. 19:14
Algorithm Study
문제 설명 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, 주어진 수열을 담을 vector, 연산 과정을 넣어줄 vector가 필요하다 우선 주어진 수에 맞게 while문을 돌도록 한다. 단, while문을 한..
[백준] 10773 제로
2023. 1. 12. 18:41
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 풀이법 일단 k개의 수를 입력 받은 후 stack을 선언하여 입력 받은 수가 0이 아닐때는 stack에 push 해준다 문제에서 입력받은 수가 0일 경우 지울 수가 있음을 보장할 수 있다고 하였으므로, 입력 받은 수가 0이면 pop을 해준다 소스 코드 #include #include using namespace std; int main() { in..
[백준] 10828 스택
2023. 1. 12. 18:24
Algorithm Study
문제 설명 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램 만들기 push X : 정수 X를 스택에 넣기 pop : 스택에서 가장 위에 있는 정수를 뺴고, 그 수를 출력하기. 만약 스택에 들어있는 정수가 없는 경우에는 -1 출력 size : 스택에 들어있는 정수의 개수를 출력 empty : 스택이 비어있으면 1, 아니면 0 출력 top : 스택의 ..
[프로그래머스] 1단계 - 크기가 작은 부분 문자열
2023. 1. 11. 19:43
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분 문자열 중에서, 이 부분 문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 구하기 문제 풀이법 처음에는 stoi, stol로만 풀었다가 제출시 code dump가 떠서 하나씩 비교하려고 했다 그렇게 되면 좀 더 복잡해져서 포기하려던 찰나, stoll에 대해서 발견하였다 long는 안..
[프로그래머스] 1단계 - 실패율
2023. 1. 11. 18:32
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42889 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개 변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return하기 문제 풀이법 단순 구현이기에 문제에서 설명하는대로 잘 구현하면 된다 여기서 몇가지 주의 해야할 점이 있는데 N + 1의 스테이지에 도달한 사람은 N번째 스테이지까지 ..
[프로그래머스] 1단계 - 소수 찾기
2023. 1. 11. 17:06
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12921 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr n까지의 소수의 개수 구하기 문제 풀이법 소수를 찾는 문제들은 그냥 for문을 냅다 돌려버리면 찾을 수는 있지만 시간 초과가 나기 때문에 에라토스테네스의 체를 이용하면 시간초과 없이 효율적으로 풀 수 있다 에라토스테네스의 체란? 소수는 1과 자기자신만으로만 나눠지는 수이기 때문에, 어떤 숫자의 배수일 수는 없다 따라서 for문을 돌면서 배수인 수를 제거하면서 소수만 남겨두는 방법이다 우..
[프로그래머스] 1단계 - 폰켓몬
2023. 1. 10. 23:42
Algorithm Study
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이법 중복되는 수를 피하면 되는터라, 처음에는 정렬을 하고 중복되는 수를 무시하는 방법을 선택하려 했다 하지만 너무 비효율적인것 같았고 찾아보니 set이라는 컨테이너가 있었다 set은 노드 기반 컨테이너이며 균형 이진으로 구현되어있으며, key라 불리는 원소들의 집합으로 이루어진 컨테이너이다 중요한 것은 key값은 중복이 허용되지 않고, 삽입 시 원소는 자동 정렬이다 그러기에 se..