https://www.acmicpc.net/problem/2805알고리즘 분류 : 이분 탐색, 매개 변수 탐색 ❓문제🔅해석투포인터와 비슷하게 세개의 포인터로 문제를 푼다.1 ~ 트리의 최대값까지의 배열을 만들어 start = 1, end = 트리의 최대값, mid = (start / end) / 2 로 초기화한다.mid 값을 현재 절단기 높이라고 생각하고, 입력받은 트리의 순회하면서 mid 값을 각각 빼주고 sum에 더한다. sum이 목표값보다 크다면 나무를 더 많이 잘랐다는 뜻으로 절단기 높이를 높이기 위해 start 값을 mid + 1로 설정한다.반대의 경우, end = mid - 1로 설정한다. 다시 mid = (start + end) / 2로 설정해고 위와 같이 트리를 순회하면서 절단된 나무들..
정렬정렬을 통해 유일성 검사 및 중복 제거가 가능하다.정렬된 데이터를 한번씩만 확인하면 각 숫자의 빈도 수를 확인할 수 있다. 정렬 방법1. Arrays.sort() - 오름차순int[] arr = {5, 3, 2, 8, 1};Arrays.sort(arr);System.out.println(Arrays.toString(arr)); // [1, 2, 3, 5, 8] - 내림차순Arrays.sort(arr, Comparator.reverseOrder());System.out.println(Arrays.toString(arr)); // [8, 5, 3, 2, 1] 2. 사용자 정의 정렬 (Comparator)Integer[] arr = {5, 3, 2, 8, 1};Arrays.sort(arr, new Com..
https://www.acmicpc.net/problem/2003 알고리즘 분류 : 브루트포스 알고리즘, 누적합, 투포인터❓문제🔅해석두 수의 합이 특정 값이 되는 경우를 찾는 문제로 투포인터를 이용한다.입력받은 숫자를 배열에 넣고 low pointer와 high pointer로 합을 구한다. //입력10 51 2 3 4 2 5 3 1 1 2 1) 초기화 및 sum 두개의 포인터 모두 0번째 인덱스부터 출발하고 sum은 0번째 인덱스 값으로 초기화해준다.sum이 특정 값(M) 5보다 작으므로 high pointer를 +1 해준다. 그리고 sum에 증가된 high 번째의 값을 더한다. 2) sum == M sum == M 이 될 때, cnt++ 해주고 low 또는 high을 +1 해준다. 그리고 su..
https://www.acmicpc.net/problem/1713알고리즘 분류 : 구현, 시뮬레이션❓문제🔅해석학생 객체에 학생 번호, 추천 수, 타임스탬프를 저장하여 조건에 맞게 정렬을 한다. Student[] students = new Student[101]; //학생 번호는 1부터 100까지의 자연수이다.학생 객체를 담는 배열을 만들어 학생 번호와 배열 인덱스를 맞춰 저장한다.예를 들어, 2번 학생이 추천을 받았을 때 배열 2번째에 학생 객체가 존재한다면 이미 추천받아 저장되어 있다는 것이다.이 때는 해당 객체의 추천수를 증가시킨다. List photos = new ArrayList(); // 사진틀의 개수 N를 저장한다.배열이 비어있다면 사진틀 리스트에 추가해준다.이 때 사진 틀이 꽉 찼을 때, ..
https://www.acmicpc.net/problem/1256알고리즘 분류 : 수학, 다이나믹 프로그래밍, 조합론❓문제🔅해석'a'와 'z'의 조합으로 n번째 단어를 출력하는 문제이다.사전에는 알파벳 순서대로 수록되어 있으므로 'a'로 시작하는 문자의 조합으로 계산해본다.입력 : 2 2 6 1. a_ _ _ 'a'로 시작하는 문자의 조합 개수는 남은 3자리수와 남은 'z'의 갯수 3C2이다. 3C2 = 3이므로 'a'로 시작했을 때 3가지의 조합을 만들 수 있다.우리는 6번째(K) 순서를 원하므로 'z'로 시작한다는 것을 알 수 있다. (3C2 1) 결과값을 담는 sb에 'z'를 추가하고2) 'z' 카운트를 하나 감소시킨다.3) K의 값을 조합 수 만큼 감소시킨다. 2. z a _ _위에서 'z'로 ..
https://www.acmicpc.net/problem/1837알고리즘 분류 : 수학, 브루트포스 알고리즘, 임의 정밀도 / 큰 수 연산❓문제🔅해석K까지의 소수배열을 만들기 위해 '에라토스테네스의 체'를 활용한다.//에라토스테네스의 체 생성for (int i = 2; i 이중 for문을 돌면서 자신의 배수에 방문 체크를 하여 지워준다. 해당 소수에 암호가 떨어진다면 K보다 작은 소수로 만들어진 암호이므로 소수 배열을 돌면서 입력받은 암호를 나눠본다.주의할 점은, 암호가 10의 100승까지 입력될 수 있어 int, long으로 입력받을 수 없다.BigInteger를 사용하는 방법도 있지만, String으로 입력받아 한 글자씩 연산을 진행하는 방법도 있다.(어떤 문제에는 BigInteger 사용이 ..
https://www.acmicpc.net/problem/3955알고리즘 분류 : 수학, 정수론, 확장 유클리드 호제법❓문제🔅해석확장 유클리드 호제법 알고리즘을 이용한다. (공식 : ax+by=gcd(a,b))방정식에 적용할 a, b, c를 생각해보자면, a와 b는 입력값인 인원수, 한 봉지에 든 사탕 개수로 둘 수 있다.axby인원수인당 나눠줄 사탕 수한 봉지에 든 사탕 수사탕 봉지수ax + 1 = by 아래와 같이 항 정리를 한다.-ax + by = 1 여기서 주의할 점은, 나머지 정의가 0 그래서 a, b에 음수가 들어오지 않도록 x가 음수 값을 가지게 한다.a(-x) + by = 1 이제 확장 유클리드 호제법을 통해 s, t, r 값을 구한다.public static EGResult egcd(l..
https://www.acmicpc.net/problem/14476 알고리즘 분류 : 수학, 정수론, 누적합, 유클리드 호제법❓문제 🔅해석위 문제는 누적합과 유클리드 호제법을 이용하여 풀이해야한다. 먼저 두 수의 최대공약수를 구하는 방법인 유클리드 호제법을 구현한 코드이다.// gcd(a, b) == gcd(b, r) : r = a % bstatic int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a;} 이 유클리드 호제법을 통해 나온 최대공약수를 누적합 배열에 담는다. 8 12 24 36 48예를들어, 입력이 위와 같이 들어왔을 때, 8 ~ 48의 최대공약..
*DFS, BFS는 그래프 알고리즘에서 기초가 되는 탐색 방식으로 반드시 숙지가 필요하다. DFS깊이 우선 탐색(Depth First Search)그래프 탐색 방법의 한가지한 경로로 탐색하다 특정 상황에서 최대한 깊숙하게 들어가서 확인 후 다시 돌아가 다른 경로로 탐색하는 방식일반적으로 재귀함수를 사용하여 풀이한다.(stack을 사용하는 문제는 거의 드물다)백트레킹, 단절선 찾기, 단절점 찾기, 위상정렬, 사이클 찾기 등에 사용된다. 풀이 팁현재 방문하고 있는 노드에만 관여한다.필요한 정보(부모가 누구인지, 얼마나 걸렸는지)는 코드를 작성하다 추가하도록 한다.추가하는 방식은 1) 파라미터로 넘기기 2) static 전역 변수 선언하기 방식이 있다. 풀이 순서 (들여쓰기 주의)체크인단순 방문 여부만 체크하..
정보처리기사 때 헷갈렸던 개념을 이제서야 정리해본다.super자손 클래스에서 조상 클래스로부터 상속받은 멤버를 참조하는데 사용되는 참조변수이다.조상 클래스로부터 상속받은 멤버도 자손 클래스 자신의 멤버이므로 super대신 this를 사용할 수 있지만 서로 구별해야하는 경우에 super를 사용하는 것이 좋다. super 예제코드1조상 클래스와 자손 클래스의 멤버 변수가 같은 경우public class SuperTest { public static void main(String[] args) { Child c = new Child(); c.method(); }}class Parent { int x = 10;}class Child extends Parent { int x = 20; void method(..
