코딩하는 고릴라

🦍 문제 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 🐈 문제 풀이 1. 무엇을 구해야 할까? 주어진 숫자들의 빈도를 계산한 후, 빈도수가 높은 숫자들부터 순서대로 출력한다. 빈도수가 같다면 먼저 나왔던 숫자들을 우선적으로 출력한다. 2. 어떻게 구해야 할까? 1) 빈도수를 구해야 한다. - 보통 빈도수를 구하는 방법으로는 배열을 사용하는 방법을 떠올릴 수 있지만 입력되는 수의 최댓값이 10억이기에 HashMap 자료구조를 이용하였다. - key 값으로는 입력받은 숫자를, value로는 빈도수를 저장하였다. - HashMap에 저장된 값을 빈도수(..

🦅 문제 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 🦍 문제 풀이 1. 무엇을 구해야 할까? 집합 A, B에 대해서 대칭 차집합 원소의 개수를 구해야한다. 여기서 대칭 차집합은 각각의 집합에 대한 차집합의 합집합이다. (A-B) U (B-A) 2. 어떻게 구해야 할까? 입력받은 두 집합의 값들을 각각의 컬렉션에 담은 후, A가 가진 값들을 B가 가지고 있는지, 그리고 그 반대의 경우를 확인해주며 원소의 개수를 카운트해주면 된다. 3. 특별히 고려할 사항은? 1) 컬렉션의 선택 - 단순히 A 집합의 ..

🐒 문제 7626번: 직사각형 첫째 줄에 양의 정수 N이 주어진다. (1 ≤ N ≤ 200,000) 다음 N개 줄에는 공백으로 나누어진 네 값 "x1, x2, y1, y2"가 주어진다. 이 값은 직사각형 [x1,x2] × [y1,y2]를 나타낸다. 모든 좌표는 0보다 크거나 www.acmicpc.net 🐈 풀이 1. y좌표 압축 2. x축 정렬 후 x축 방향으로 순차적으로 스위핑 3. 스위핑하며 직사각형의 세로선 활성화 및 비활성화를 통해 좌표상의 직사각형 넓이를 구한다. 1. 주어지는 x, y 좌표의 최대값이 매우 커 이를 바로 활용해 트리를 만들 수 없다. 따라서 좌표 압축을 필요로 한다. 2. 스위핑 기법을 통해 문제풀이를 진행하되, 과연 어떤 값을 어떻게 저장하고 꺼내와야 하는지의 아이디어가 중요..

🐒 문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 🐈 문제풀이 핵심 이분 탐색 기법을 사용할 줄 알고, 어떤 상황에서 어느쪽 절반을 택해 탐색을 파고 들어가야할 지 결정할 수 있어야 하는 문제였다. 한 쪽 절반을 선택하여 파고 들어가는 부분을 결정하는데 특정 변수의 값을 기준으로 하기 때문에 이분 탐색의 응용인 매개 변수 탐색(Parametric search)을 진행하여야 한다. 아래 예시를 보자. 길이가 9인 랜선 1개를 가지고 있고, 이를 잘라 길이가 균등하면서 가장 긴..

🐒 문제 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 🐈 문제풀이 핵심 A번 ~ B번 인덱스를 확인했을 때 해당 구간에 A번부터 B번까지의 값이 모두 존재하는지 확인하는 것을 어떤 식으로 구현할지가 관건이다. 이를 위해 해당 구간의 최솟값, 최댓값을 구하여 확인하는 방법을 이용했다. A번 ~ B번 인덱스 구간의 값을 확인했을 때, 최소값이 A이고 최댓값이 B라면 그 둘 사이의 값은 모두 A와 B 사이에 있음을 보장받는다. 따라서 해당 구간의 최솟값, 최댓값만 구..