QodeLog

2023.2.22 포스팅 기준 solved.ac 문제 등급 : 골드 1 단계별로 풀어보기 -> 트리에서의 동적계획법 알고리즘 분류 다이나믹 프로그래밍 트리 트리에서의 다이나믹 프로그래밍 https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 시간제한 메모리제한 2 초 128 MB 그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 간선이 없으면) S를 독립 집합(in..

2022.02.22 포스팅 기준 solved.ac 문제 등급 : 플래티넘 3 단계별로 풀어보기 -> 세그먼트 트리 알고리즘 분류 자료구조 세그먼트 트리 https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 시간제한 메모리제한 2 초 256 MB 최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을..

2022.02.21 포스팅 기준 solved.ac 문제 등급 : 플래티넘 5 단계별로 풀어보기 -> 세그먼트 트리 알고리즘 분류 자료 구조 정렬 세그먼트 트리 분할 정복 https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 시간제한 메모리제한 1 초 512 MB N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 ..

2022.02.14 포스팅 기준 solved.ac 문제 등급 : 골드 1 단계별로 풀어보기 -> 세그먼트 트리 알고리즘 분류 자료구조 세그먼트 트리 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 시간제한 메모리제한 2 초 192 MB N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만..

2022.02.11 포스팅 기준 solved.ac 문제 등급 : 골드 1 단계별로 풀어보기 -> 세그먼트 트리 알고리즘 분류 자료구조 세그먼트 트리 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 시간제한 메모리제한 1 초 256 MB 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5..

2022.02.10 포스팅 기준 solved.ac 문제 등급 : 골드 1 단계별로 풀어보기 -> 세그먼트 트리 알고리즘 분류 자료구조 세그먼트 트리 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 시간제한 메모리제한 2 초 256 MB 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가..

2022.02.09 포스팅 기준 solved.ac 문제 등급 : 플래티넘 4 단계별로 풀어보기 -> 세그먼트 트리 알고리즘 분류 자료구조 세그먼트 트리 https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 시간제한 메모리제한 2 초 512 MB 자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다. 유형 1 : S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 ..