동적 프로그래밍 (DP) : 큰 하나의 문제를 여러 하위 문제로 나누어 풀고 그 결과들을 결합해서 최종 목적인 큰 문제를 해결하는 방식의 알고리즘. 💡 반복적인 처리(계산)를 피할 수 있음 ☞ 이전 단계 처리 결과를 저장하고 다음 단계를 해결할 때 이미 진행했던 부분은 저장되어 있던 값을 불러옴 💡 점화식을 세우면 쉽게 DP 문제 해결 가능 (ex. 피보나치수열 점화식 : dp[i] = dp[i-1]+dp[i-2] ) 💡 어떤 값을 어떤 방식으로 저장할지 정하는 것이 포인트!! 1. Top-Down: 말 그대로 문제풀이가 위에서 아래로 진행 > 주로 재귀 함수 사용 > 시간 복잡도 문제가 발생할 수 있고 저장 유무에 따라 DP로 보지 않는 의견도 있음 2. Bottom-Up: 반대로 문제풀이가 아래에서 ..

Counting sort Counting sort는 정렬 알고리즘으로 시간 복잡도는 O(n)이다. 빠른 속도로 유명한 Quick sort의 시간 복잡도가 O(nlogn)이므로 counting sort의 속도는 상당히 빠르다. counting sort는 말 그대로 배열에 존재하는 숫자의 등장 횟수를 카운트해서 정렬한다. 1. 각 숫자의 등장 횟수를 카운트한다. : A배열 원소의 범위를 0~5까지로 가정하면 B배열의 크기는 6이다. B[idx] = A배열에 등장하는 숫자 idx가 등장하는 횟수 (ex. B[1] = A배열에서 1이 등장하는 횟수 = 1) 2. 등장 횟수를 누적 합으로 변경한다. : B2[i] = B[i] + B[i-1] + B[i-2] + ... + B[0] (ex. B2[2] = B[0]+..

6이 3번이상 연속으로 나오는 수 중에서 N번째로 작은 수 출력하는 프로그램 (666, 1666, 2666, 3666, ... ) - N=1이면 출력값: 666, N=7이면 6660 N 입력 N번째로 작은 666을 포함한 숫자 찾기 666부터 1씩증가 증가시 문자열로 변형하여 '666'포함하는 지 검사 포함하면 개수 세며 N과 동일한지 확인 동일하면 반복문 out 숫자 출력 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int num = 666; int count = 1; String check..

카드와 자연수 M이 주어졌을 때, 카드 3장을 골라 M을 초과하지 않는 제일 가까운 수를 구하는 프로그램 - 브루트 포스 알고리즘 카드 수와 자연수 M 입력 카드 번호 입력 3개씩 뽑을 수 있는 조합을 검사하며 max_sum 구하기 [ 조건: max_sum

입력받은 자연수 N에 대한 가장 작은 생성자를 구하는 프로그램 -분해합 & 생성자 원리 : A = 245일 때, A의 분해합 = 245 + 2 + 4 +5 = B. B의 생성자 = 245 - 숫자 N의 생성자는 1~N사이 값이다. 따라서, 1~N까지 생성자 인지 아닌지 검사하며 최소 생성자를 구한다. - 브루트 포스 알고리즘 구현 순서 : 자연수 N 입력 자연수 1 ~ N-1까지 N의 생성자 인지 검사 buf = N - test_N (test_N은 1부터 N까지 검사하는 수) buf와 test_N의 각 자릿수 합이 동일한지 검사 동일하다면 test_N 출력 -> 프로그램 종료 다르다면 2-1로 돌아가 test_N+1 검사 검사해도 찾지 못할 경우, 0 출력 종료 import java.util.Scanne..

포인트! : 사람들의 몸무게와 키를 입력하여 덩치 순서 출력 1. 사람들 수 입력 2. 사람들 몸무게와 키 입력 3. 사람들의 덩치 순서 구하기 방법: 자신보다 몸무게와 키가 큰 사람들의 수 +1 = 자신의 덩치 순위 4. 덩치 순서 출력 import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int[][] data; int size; //step1 : Enter the number of people size = sc.nextInt(); if(size < 1) return; data = new int[size][3]; //step2 : Ent..

Brute force : 무식한 힘 - 완전 탐색 알고리즘 : 가능한 모든 경우의 수를 탐색하여 요구조건에 충족되는 결과만을 가져온다. 장: 단순한 알고리즘으로 쉽게 구현 가능, 정확성 100% 단: 모든 경우를 탐색하여 시간 효율성이 떨어진다. 예시) N={a, b, c}에서 a가 들어가는 N의 부분 집합을 구할 때, 일단 N의 전체 부분 집합을 구한다 {a}, {b}, {c}, {ab}, {bc}, {ac}, {abc} 이중에서 a를 포함하는 부분집합만 골라 선택한다. 완전탐색 알고리즘 사용 전 고려사항 가능한 경우의 수를 대략적으로 계산 가능한 모든 방법 고려 적용 완전탐색 알고리즘 구현 방식 Brute Force 기법 - 경우의 수 모두 테스트 순열 (Permutation) - n개의 원소중에서 ..

문제: N개의 원판 개수를 입력 받았을 때, 이동 과정 출력 하노이 탑의 원리를 알기! 하노이 탑 이동 횟수 = 2^N - 1 한 번 이동할 때, 제일 위에 있는 원판 하나만 이동 가능 크기가 큰 원판은 작은 원판 위에 쌓을 수 없음 이동 방법(위치1에 원판 n개가 있다고 가정) n-1개의 원판을 위치 2로 옮기기 마지막 원판을 위치 3으로 옮김 n-1개의 원판을 다시 위치 3으로 옮김 import java.util.Scanner; public class Main { public static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = ..