본문 바로가기

Dot Algo∙ DS

[BOJ] 백준 3745번 오름세 (Java)
Dot Algo∙ DS/PS 2022. 2. 5. [BOJ] 백준 3745번 오름세 (Java) #3745 오름세 난이도 : 골드 2 유형 : LIS / DP / 이분 탐색 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net ▸ 문제 주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다. 정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다. n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다. n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성..
[BOJ] 백준 8983번 사냥꾼 (Java)
Dot Algo∙ DS/PS 2022. 2. 4. [BOJ] 백준 8983번 사냥꾼 (Java) #8983 사냥꾼 난이도 : 골드 4 유형 : 이분 탐색 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net ▸ 문제 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물..
[BOJ] 백준 1561번 놀이 공원 (Java)
Dot Algo∙ DS/PS 2022. 2. 3. [BOJ] 백준 1561번 놀이 공원 (Java) #1561 놀이 공원 난이도 : 골드 2 유형 : 이분 탐색 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net ▸ 문제 N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다. 모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구..
[BOJ] 백준 10090번 Counting Inversions (Java)
Dot Algo∙ DS/PS 2022. 2. 2. [BOJ] 백준 10090번 Counting Inversions (Java) #10090 Counting Inversions 난이도 : 플레 5 유형 : 세그먼트 트리 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net ▸ 문제 A permutation of integers from 1 to n is a..
[BOJ] 백준 12846번 무서운 아르바이트 (Java)
Dot Algo∙ DS/PS 2022. 2. 1. [BOJ] 백준 12846번 무서운 아르바이트 (Java) #12846 무서운 아르바이트 난이도 : 플레 5 유형 : 세그먼트 트리 / 분할정복 12846번: 무서운 아르바이트 성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다. 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다. 돈은 당일에 주지 않고 퇴직을 할 때 한 www.acmicpc.net ▸ 문제 성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다. 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다. 돈은 당일에 주지 않고 퇴직을 할 때 한번에 준다. 성화는 욕심쟁이라서 해당 일을 한 동안 중 가장 일급이 작을 때를 기준으로 급여를 지급한다. 일급이 다른 것을 들키지 않기 위하여 한번이라도 퇴직한 자를 다시 취직 시..
[BOJ] 백준 1615번 교차개수세기 (Java)
Dot Algo∙ DS/PS 2022. 1. 31. [BOJ] 백준 1615번 교차개수세기 (Java) #1615 교차개수세기 난이도 : 플레 5 유형 : 세그먼트 트리 / 펜윅 트리 1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net ▸ 문제 각각 N(1 ≤ N ≤ 2,000)개의 쌍으로 이루어진 2N개의 정점과 M(1 ≤ M ≤ N×(N-1)/2)개의 간선으로 구성된 이분그래프가 주어질 때 서로 교차하는 총 개수를 구하는 것이다. 교차 조건 : 한 독립 집합 A와 다른 독립 집합 B가 연결된 두 개의 간선을 (A1, B1), (A2, B2)라 한다면 A1 B2 또는 A1 > A2,..
[BOJ] 백준 5419번 북서풍 (Java)
Dot Algo∙ DS/PS 2022. 1. 30. [BOJ] 백준 5419번 북서풍 (Java) #5419 북서풍 난이도 : 플레 4 유형 : 세그먼트 트리 / 좌표 압축 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net ▸ 문제 강한 북서풍이 불고 있다. 이 뜻은 동쪽과 남쪽 사이의 모든 방향으로 항해할 수 있다는 뜻이다. 북쪽이나 서쪽으로 항해하는 것은 불가능하다. 작은 섬이 여러 개 있는 바다가 있다. 섬은 좌표 평면의 한 점으로 나타낼 수 있다. y 좌표가 증가하는 방향은 북쪽, x좌표가 증가하는 방향은 동쪽이다. 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 구하는 프로그램을 작성하시오. ▸ 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 섬의 수 n (1 ≤ n ≤ 750..
[BOJ] 백준 1849번 순열 (Java)
Dot Algo∙ DS/PS 2022. 1. 29. [BOJ] 백준 1849번 순열 (Java) #1849 순열 난이도 : 플레 5 유형 : 세그먼트 트리 1849번: 순열 1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라 www.acmicpc.net ▸ 문제 1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라. ▸ 입력 첫째 줄에 수열 원소의 개수 (1 ≤ N ≤100,000)이 주어진다. 그리고 두 번째 줄부터 N+1 번째 줄까지 차례로 A[i]가 주어진다. ▸ 출력 N개의 줄에 걸쳐..

티스토리툴바

티스토리툴바