자료구조

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 3258. 컴포트 링크 : https://www.acmicpc.net/problem/3258문제 요약1에서 게임을 시작해서, Z번째 필드에 도착하는 것이 이 게임의 목표도착점은 K만큼씩 시계방향으로 이동해 도달해야 한다도착점으로 가는 길에 장애물이 있는 필드를 밟아서는 안 된다예를들어 N=13, K=3 그리고 Z=9라고 했을 때 아람이는 1,4,7,10,13,3,6 그리고 9 의 필드를 지나게 된다게임판의 정보가 주어졌을 때 도착점에 도착할 수 있는 가장 작은 K를 찾는 프로그램을 작성시간 제한1초입력첫째 줄에는 N(2 ≤ N ≤ 1000), Z(2 ≤ Z), M(0 ≤ M ≤ N-2)N은 필드의 수이고 Z는 도착해야하는 필드의 번호를 의미다음 줄에 M개의 서로 다른 정수정수는 장..

알고리즘 문제) 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 → 카운팅 배..

트라이 정의문자열을 저장하고 검색하는 효과적인 트리 구조의 자료구조각 노드가 문자를 가지며, 루트 노드부터 자식 노드를 따라가며 문자열을 구성루트 노드루트 노드는 비어 있다루트 노드의 자식 노드는 각 단어들의 첫 글자를 나타낸다.사용하는 이유?좀 더 빠르게 문자열을 탐색할 수 있다그러나 각 노드마다 문자, 자식 노드 객체를 저장한다는 점에서 메모리가 많이 필요하다는 단점이 존재 구현노드 클래스와 트리 클래스 2개를 갖는다.노드 클래스각 노드는 child라는 자식 노드의 맵을 가짐Map단어의 끝인지를 표시 하는 boolean 타입 변수 필요트리 클래스트라이의 자료구조를 구현한 클래스insert 메서드 : 단어를 트라이에 삽입search 메서드 : 단어가 트라이에 존재하는지 확인static class Nod..

트리의 정의트리란?임의의 두 노드를 연결하는 단순 경로가 정확히 하나 존재하는 그래프단순 경로 : 같은 노드를 2번 이상 지나지 않는 것.다음과 같은 조건을 만족하면 트리🌲① 모든 노드가 하나의 연결 요소 ② 사이클이 없어야 한다.③ 노드의 개수가 간선의 개수보다 하나 많다.ex) 노드가 3개면 간선은 2개1번, 2번 조건을 만족하면 3번 조건도 만족할 수밖에 없다. (간선이 N개가 되면 무조건 사이클이 생길 수 밖에 없음)2번, 3번 조건을 만족하면 1번 조건도 만족하고, 1번, 3번 조건을 만족하면 2번 조건도 만족한다.즉, 위 조건 중 2개가 문제에 나오면 트리라고 생각하면 된다.ex) 두 도시를 지나는 경로는 정확히 하나 존재 ⇒ 트리ex) 어떤 두 도시를 잡을 때 그 경로가 무조건 존재하고, ..