Algorithm
-
[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임으로 여유가 있으니 해당 범위만큼 길이를 선언하고 시작해도 무방할 것으로 보입니다. 한번만 순회하면서 가장 긴 경우의 수를 찾기 위해 투포인..
-
코딩 테스트 문자열 처리 시 주의점Algorithm/Algorithm 2022. 6. 22. 16:13
BOJ 13414번을 풀다가 쉽게 놓칠 수 있는 문자열 처리 경우의 수에 대해 정리하여 본다. https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 주의 점 1. 문자열 -> Int -> Key 접근 시 위 문제를 보면 일반적으로 아무 생각 없이 Dictionary에 Key로 구현하여 값을 넣는데, 이 때 Key에 관련된 문자열을 넣을 때 Int 형으로 바꾸어서 입력을 넣게 되면, 학번과 같은 경우는 앞이 0이 나올 수가 있어 예외가 발..
-
[BOJ] 13144번 - List of Unique NumbersAlgorithm/BOJ 2022. 6. 22. 15:41
[BOJ] 13144번 - List of Unique Numbers https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 문제 이해 수열에서 연속되게 1개 이상 뽑는 경우에서 같은 수가 등장하는 경우는 제외하고 갯수를 세라. 여기서 중요한 점이 "연속"과 "같은 수"이다. 알고리즘 처음 문제를 보자마자 투포인터로 풀어야겠다는 생각을 하였다. 각 시작점에서 같은 수가 없이 등장하는 뒷단계를 알면 한번에 계산이 되기 때문이다. 처음에는 Left , Right를..
-
[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] 8980번 - 택배Algorithm/BOJ 2022. 6. 20. 17:36
[BOJ] 8980번 - 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 알고리즘 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다. 최대한 많은 박스들을 가져가야 함으로 그리디 알고리즘으로 생각하여 구현하였습니다. 처음에는 Truck을 Time에 따라 구현하였으나, 시간 복잡도가 부족하여 75점이 나왔기 때문에 후에 정렬된 박스들의 표를 보고 얼마나 보낼 수 있는지로 구현하여 O..
-
[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. 다음에 사용된다면 가..