스택

https://www.acmicpc.net/problem/1863문제 요약주어진 스카이라인 정보를 보고 건물이 최소 몇 채인지 알아내라시간 제한2초입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000)다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y(1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000)첫 번째 지점의 x좌표는 항상 1이다.출력첫 줄에 최소 건물 개수를 출력접근법스택이 오름차순 스택을 유지하도록 담기만약 다음에 올 원소가 스택의 상단에 있는 값보다 작거나 같다면, pop시도이때, 카운트는 다음 원소보다 큰 원소를 pop할 때만 카운트마지막에 스택이 비어있지 않다면, 남은 높이가 0보다 큰 원소개수만큼만 추가로 카운트코드im..

알고리즘 문제) BOJ 3015. 오아시스 재결합 링크 : https://www.acmicpc.net/problem/3015문제 요약N명이 한 줄로 서서 기다리고 있다두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성시간 제한1초입력첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다모두 2^31보다 작다사람들이 서 있는 순서대로 입력이 주어진다.출력서로 볼 수 있는 쌍의 수를 출력한다.접근법N이 50만 까지 가능하므로 O(N)안에 연산을 마쳐야 한다.두 건물이 ..

알고리즘 문제) BOJ 20960. Po 링크 : https://www.acmicpc.net/problem/20960문제 요약증강작업을 실시하여, 어떠한 수열을 만들었을 때, 최소 증강 횟수를 출력해라증강작업은 수열의 한 구간을 선택해 그 구간의 모든 요소를 특정 야ㅇ만큼 증가시킨 것을 의미한다.시간 제한1초입력수열의 길이를 나타내는 정수 n (1 ≤ n ≤ 100,000)n개의 0 이상 10^9 이하의 정수 ai증강 작업 이후의 수열을 의미출력가능한 최소 증강 작업 횟수인 m을 출력접근법특정 구간을 한번에 증가 시키면서 최소 횟수로 원하는 수열 형태를 만들어야함예시로 다음과 같이 주어졌을 때1 3 4 2 5 2 1 2위 그림처럼 연속된 구간별로(색깔로 구분) 증가시키면 최소 횟수만큼만 연산을 수행할 수..

알고리즘 문제) BOJ 2374. 같은 수로 만들기 링크 : https://www.acmicpc.net/problem/17178문제 요약n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가이때, A[i]의 좌우로 인접한 같은 수의 그룹도 한번에 1씩 증가이와 같이 Add라는 연산을 사용하여 A[1] = A[2] = A[3] = … = A[n]이 되도록 하려 한다소 회수로 Add연산을 사용하는 방법을 찾아라시간 제한1초입력첫째 줄에 정수 n다음 n개의 줄에는 차례로 A[1], A[2], …, A[n]든 입력은 1,000,000,000을 넘지 않는다출력첫째 줄에 최소의 Add연산 사용 회수를 출력값은 10^..

알고리즘 문제) BOJ 30646. 최대 합 순서쌍의 개수 링크 : https://www.acmicpc.net/problem/30646문제 요약크기가 N인 배열 a배열 a의 임의의 위치를 나타내는 두 수 i, j를 골랐을 때, 아래 두 조건을 만족하면 같은 수 순서쌍 (i, j)를 만들 수 있다1 ≤ i ≤ j ≤ Nai = aj만들어진 같은 수 순서쌍 (i, j)의 합은 ai부터 aj까지의 합 ai + ai+1 + ai+2 + … + aj-1 + aj이때 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합을 찾고, 최대 합을 가지는 같은 수 순서쌍의 개수를 출력하는 프로그램을 작성시간 제한1초입력첫 번째 배열 a의 크기 N1 ≤ N ≤ 200,000두 번째 줄에 배열 a의 원소 a1, a2, …,..

알고리즘 문제) BOJ 17299. 오등큰수 링크 : https://www.acmicpc.net/problem/17299문제 요약크기가 N인 수열 A1, …, AN이 존재수열의 각 원소 Ai에 대해 오등큰수 NGF(i)를 구하고자 한다오등큰수는Ai가 수열에서 등장한 횟수를 F(Ai)라 할 때Ai의 오등큰수는 Ai보다 오른쪽에 있으면서, 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중 가장 왼쪽에 있는 수를 의미없다면 -1시간 제한1초입력수열 크기 N1 ≤ N ≤ 100만수열의 원소 A1, … , An이 주어진다1 ≤ Ai ≤ 100만출력총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력접근법1 1 2 3 4 2 1등장 횟수 : 3 3 2 1 1 2 3 → 카운팅 배..