Algorithm
-
[BOJ] 2283번 - 구간 자르기Algorithm/BOJ 2022. 7. 6. 15:13
[BOJ] 2283번 - 구간 자르기 문제 푼 방식과 어떻게 풀었는지에 대해 설명하여 보겠습니다. 문제 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 문제 이해 처음 문제를 이해한 바로는 N 은 1000까지 K는 10억까지로써, K로 나누어질 수 있는 좌우 부분을 구하라는 문제로 이해하였습니다. 이에 따라 10억까지의 숫자 범위에서 메모리적으로 투포인터로 범위를 구하..
-
[BOJ] 2461번 - 대표 선수Algorithm/BOJ 2022. 7. 5. 23:43
[BOJ] 2461번 - 대표 선수 https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 문제 이해 문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제 알고리즘 문제는 N개의 반에 M명씩 있을 때 각각의 학생들을 선택하여 최대 최소 구간이 적게 만드는 문제이다. 1. 접근 시에는 각 N개의 List를 Heapq로 구현 -> 맨 앞에 있는 값들을 매번 갱신하며 찾아보았지만, 시간 초과가 발생..
-
[BOJ] 20922번 - 겹치는 건 싫어Algorithm/BOJ 2022. 6. 29. 12:16
오늘 풀어본 문제는 [BOJ] 20922번 - 겹치는 건 싫어 입니다. https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 알고리즘 위 문제는 연속되는 부분 수열 중에서 특정 숫자가 K개 아래인 경우 중 제일 긴 길이를 선택하면 됩니다. N의 범위는 10만 a의 범위는 10만으로써, 메모리가 1024MB임으로 여유가 있으니 해당 범위만큼 길이를 선언하고 시작해도 무방할 것으로 보입니다. 한번만 순회하면서 가장 긴 경우의 수를 찾기 위해 투포인..
-
[BOJ] 2110번 - 공유기 설치Algorithm/BOJ 2022. 6. 20. 23:14
[BOJ] 2110번 - 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근 방식(틀린 풀이) 해당 문제는 풀어본적 있는지 여부에 따라 풀 수 있는지 여부가 달라질 것으로 보인다. 처음에는 공유기를 맨 앞과 맨뒤로 부터 놓은 다음에 하나씩 증가 시키며 Devide 시켜 그 중에 max된 값을 추출하여 값을 구하는 방식으로 구현하였다. 하지만 위와 같은 방식은 O(N^2)이 소요되..
-
[BOJ] 2482번 - 색상환Algorithm/BOJ 2022. 6. 13. 22:15
[BOJ] 2482번 - 색상환 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘 연속되어 있는 색은 추가가 불가능 단계별 갯수를 세가면서 추가 -> DP DP를 나타낼 때 DP[i][j] 시 i는 색의 갯수 / j는 색을 고를 수 있는 경우이다. 1. i가 1인 경우에는 모두 n의 갯수에 맞추어 증가한다. 2. 후에 i가 2부터는 경우의 수를 나타내다 보면 DP[i][j] = DP[i-1][j-2] + DP[i][j-1] 로 계산식이 되는 것을 알 수 있다...
-
[BOJ] 1700번 - 멀티탭 스케줄링Algorithm/BOJ 2022. 6. 13. 22:07
[BOJ] 1700번 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 알고리즘 그리디 알고리즘 멀티탭을 오랫동안 유지하고 싶음으로 가장 나중에 사용할것을 바꾸어주는게 좋다. 1. 멀티탭에 이미 있는 경우 -> PASS 2. 멀티탭에 빈자리가 있는 경우 -> 빈자리에 꼽는다. 3. 멀티탭에 있는것을 뺀 다음 새롭게 꼽는다. 4. 단 멀티탭에 있는 것을 빼기 위해서는 다음에 사용하지 않을 것이 우선순위 5. 다음에 사용된다면 가..
-
[BOJ] 2473번 - 세 용액Algorithm/BOJ 2022. 6. 11. 14:27
[BOJ] 2473번 - 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 알고리즘 각 용액의 3가지의 합이 최소가 되는 경우의 수를 찾아야한다. 이분탐색을 이용하여 하나를 선택한 다음에 나머지 두가지를 매칭하는 방법을 사용하였다. 1. 데이터를 입력 받는다. 2. 이분 탐색을 위하여 데이터를 정렬한다. 3. 각 용액 별로 최소의 경우(left , right 를 두어 결과 값이 0보다 크면 right를 작게 반대는 ..
-
[BOJ] 11660번 - 구간 합 구하기 5Algorithm/BOJ 2022. 6. 11. 14:00
[BOJ] 11660번 - 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 알고리즘 구간 합을 미리 DP로 구하여 둔 다음에 해당되는 행 영역의 합을 구하여준다. 계산상 편의를 위해 2차원은 N+1로 적용하였다. 코드 #BOJ 11660번 import sys input = sys.stdin.readline answer = [] n , m = map(int,input().split()..