본문 바로가기

Dot Algo∙ DS

[BOJ] 백준 1572번 중앙값 (Java)
Dot Algo∙ DS/PS 2022. 1. 28. [BOJ] 백준 1572번 중앙값 (Java) #1572 중앙값 난이도 : 플레 5 유형 : 세그먼트 트리 1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1 www.acmicpc.net ▸ 문제 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1초에 온도를 하나씩 재는 온도계를 만들었다. 이 온도계에는 작은 디스플레이 창이 하나 있는데, 이 ..
[BOJ] 백준 1671번 상어의 저녁식사 (Java)
Dot Algo∙ DS/PS 2022. 1. 27. [BOJ] 백준 1671번 상어의 저녁식사 (Java) #1671 상어의 저녁식사 난이도 : 플레 3 유형 : 이분 매칭 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net ▸ 문제 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크거나 같다면 상어 A는 상어 B를 먹을 수 있다. 그러나, 상어들의 왕 김재홍은 상어들이 많이 없어지는 것을 방지하기 위해서 한 상어가 최대 두 개의 상어만 먹을 수 있게 했다...
[BOJ] 백준 1298번 노트북의 주인을 찾아서 (Java)
Dot Algo∙ DS/PS 2022. 1. 26. [BOJ] 백준 1298번 노트북의 주인을 찾아서 (Java) #1298 노트북의 주인을 찾아서 난이도 : 플레 5 유형 : 이분 매칭 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net ▸ 문제 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 받을 수 있었지만, 애석하게도 N명의 학생들이 정확히 자신의 노트북이 어떤것인지 알지 못했다. 왜냐하면 그들은 노트북을 구입한게 바로 어제였기 때문이다. 어차피 새것인 노트북, 바뀐들 어떠하랴...
[BOJ] 백준 11378번 열혈강호 4 (Java)
Dot Algo∙ DS/PS 2022. 1. 25. [BOJ] 백준 11378번 열혈강호 4 (Java) #11378 열혈강호 4 난이도 : 플레 4 유형 : 이분 매칭 11378번: 열혈강호 4 첫째 줄에 직원의 수 N과 일의 개수 M, 지난달에 받은 벌점의 합 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 www.acmicpc.net ▸ 문제 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 여기서 지난달에 벌점을 X점 받은 사람은 일을 최대 X+1개까지 할 수 있다. 예를 들어, 직원이 3명이고, 지난달..
[BOJ] 백준 18436번 수열과 쿼리 37 (Java)
Dot Algo∙ DS/PS 2022. 1. 24. [BOJ] 백준 18436번 수열과 쿼리 37 (Java) #18436 수열과 쿼리 37 난이도 : 골드 1 유형 : 세그먼트 트리 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ www.acmicpc.net ▸ 문제 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 홀수의 개수를 출력한다. 수열의 인덱스는 1..
[BOJ] 백준 12844번 XOR (Java)
Dot Algo∙ DS/PS 2022. 1. 23. [BOJ] 백준 12844번 XOR (Java) #12844 XOR 난이도 : 플레 3 유형 : 세그먼트 트리 / Lazy Propagation 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net ▸ 문제 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. ▸ 입력 첫 번째 줄에 수열의 크기 N이 주어진다. 두 번째 줄..
[BOJ] 백준 11658번 구간 합 구하기3 (Java)
Dot Algo∙ DS/PS 2022. 1. 22. [BOJ] 백준 11658번 구간 합 구하기3 (Java) #11658 구간 합 구하기3 난이도 : 플레 5 유형 : 펜윅 트리 / 누적합 11658번: 구간 합 구하기 3 첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 www.acmicpc.net ▸ 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 표의 i행 j열은 (i, j)로 나타낸다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 여기서 (2, 2)부터 (..
[BOJ] 백준 13325번 이진 트리 (Java)
Dot Algo∙ DS/PS 2022. 1. 21. [BOJ] 백준 13325번 이진 트리 (Java) #13325 이진 트리 난이도 : 골드 4 유형 : 트리 / DFS 13325번: 이진 트리 입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가 www.acmicpc.net ▸ 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치..

티스토리툴바

티스토리툴바