멍두의 개발새발

📍 문제https://www.acmicpc.net/problem/18110 상,하위 15퍼센트 의견은 제외하고 평균을 낸 뒤 반올림하는 문제쉬운 문제이지만 두 가지 방법으로 풀 수 있어서 글을 작성한다. 의견의 개수 n이 매우 크므로 이 부분에 유의 (0 ≤ n ≤ 3^105)📍 코드 설명첫번째 방법가장 떠올리기 쉬운 방법1. 의견을 배열에 받은 뒤 오름차순 정렬한다.2. 상 하 15%를 계산한다.3. 15%에 해당하는 index를 제외한 배열을 전부 더한 뒤 평균을 구한다 이 방법은 배열을 정렬할 때 평균 : O(nlog(n)) / 최악 : O(n^2),전부 더할 때 입력의 수만큼 돌아야한다. 두번째 방법countingSort를 이용한 방법1. 배열 index를 점수라 생각하고, 점수가 들어올때마다..

📍 문제https://www.acmicpc.net/problem/10814📍 코드 설명나이 순으로 정렬하고 나이가 같다면 먼저 입력된 순으로 정렬하는 문제이다. 두가지 방법으로 풀어볼수있다.1. class 를 이용하여 age, name을 입력받고 compareTo를 override하여 age순으로 정렬한다2. 배열 index로 age를 사용하여 나이와 이름을 저장한다.📍 코드✔️ class - compareTo 코드1. class로 Person을 만들어 age와 name을 변수로 가진다 2. Comparable의 compareTo를 구현한다.이때, 나이를 기준으로 정렬한다추후 출력에 용이하기 위해 출력 형식에 맞춰 ToString도 구현한다. 3. List으로 입력받고, Collection.sort..

📍 문제https://www.acmicpc.net/problem/9095📍 코드 설명입력 된 수를 1, 2, 3의 합으로 만들 수 있는 경우의 수를 세는 문제이다. 1, 2, 3이 합에서 이용되므로 일단 1, 2, 3을 만들 수 있는 경우의 수를 세보자 아직까지는 잘 모르겠으니 5까지 경우의 수를 구해보자 엇 이때 어떤 규칙을 알 수 있다 n=4를 자세히 보자 n=4일때 결국 n=3일때의 경우의 수에 + 1, n=2일때의 값에 + 2, n=1일때의 값에 + 3 을 하면 n=4의 경우의 수와 동일해진다 혹시모르니 n=5도 자세히 보자 여기서도 동일하게 n=4경우의 수에 +1, n=3의 경우의 수에 +2, n=2 의 경우의 수에 +3을 하면 n=5의경우의수가 나오는 것을 볼 수 있다. 이것으로 우리는 n..

📍 문제https://www.acmicpc.net/problem/11726📍 코드 설명2 * n 의 직사각형을 2 * 1 or 1 * 2 의 직사각형으로 채울 때 가능한 경우의 수를 찾는 문제 이 때 결국 1 * n개의 직사각형을 1 * 1 or 1 * 2의 직사각형으로 채울 때와 동일하므로 결국 배열을 2칸 채우냐, 1칸 채우냐로 생각하면 편하다.일단 어떻게 풀어야할지 감이 오지 않으므로 5개 까지는 손으로 직접 구해본다 n = 1경우의 수 1 => 1개 n = 2경우의 수 11 / 2 => 2개  n = 3경우의 수 111 / 12 / 21 => 3개 n = 4경우의 수 1111 / 112 / 121 / 211 / 22 => 5개 n = 5경우의 수 11111 / 1112 / 1121 / 1211..

📍 문제https://www.acmicpc.net/problem/1463📍 코드 설명n % 3 ==  0 이면 n/3 , n% 2 == 0이면 n/2, n-13가지 연산을 진행해서 가장 빨리 1에 도달하는 연산횟수를 찾는 문제 입력의 크기가 1 ~ 10^6이고 시간 제한 0.15초이므로 모든 경우의 수를 계산하면 시간 초과 직전의 연산 결과를 기억하고 계산하는 DP 문제로 예상가능 재귀문제로 접근1. 종료 조건 : 현재 탐색 횟수 count 가 현재 탐색최소 탐색 횟수 1보다 클 때 굳이 계산할 필요 X2. n의 초기 값은 integer max => 가장 먼저 1에 접근한 count를 min으로 저장하기 위해3.  n이 1에 도달시 min과 비교하여 더 작은 값을 min에 저장4. n/3 , n/2 ..