CodingTest

[Backjoon_4375] 1 (Java)

문제 링크 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 더보기 더보기 더보기 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성한다. 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. 1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다. 시간 제한 1초 메모리 제한 128MB 문제 풀이 n을 입력받아 n의 배수중 1로만 이루어진 가장 작은..

브루트포스(3) 순열

순열 순열(Purmutation)은 숫자를 사전순으로 나열한 것을 의미한다. 더보기 Ex) 1,2,3 순열 1 2 3 -> 시작 순열(오름차순) 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 -> 끝 순열(내림차순) 순열은 시작지점, 끝지점, 다음 순열,이전 순열로 표현할 수 있다. 시작순열과 끝 순열을 각각 오름차순과 내림차순으로 구성된다. 다음 순열 순열의 다음을 구하는 방법이다. 끝순열을 구해서 그 다음 구해주어 해결한다. private boolean nextPermutation(int[] numbers){ int prevIndex; int n = numbers.length; int nextIndex = n-1; int changeIndex = -1; for(int i = n-2; i >= ..

브루트포스(2) 재귀

재귀를 쓰면 재귀를 쓰면 모든 경우의 수를 확인하도록 만들 수 있다. 재귀를 써서 모든 경우를 확인하는 경우는 두가지이다. 1. 순서가 있는 경우(P) n개의 수를 나열하는 방법의 수이다.(중복가능) -> O(n!) /** * index -> 현재 수를 놓는 위치 * arr -> 확인하려고 만드는 배열 */ public void recursive1(int index, int[] arr){ if(index == arr.length){ //종료 조건 } for(int i = 1; i O(2^n) /** * index -> 현재 수를 놓는 위치 * arr -> 확인하려고 만드는 배열 */ public void recursive2(int cnt, int[] arr, int value, int n){ if(ind..

브루트포스(1) - 무작정 해보기

브루트 포스 알고리즘 모든 경우의 수를 해보는 알고리즘이다. 무작정 반복문을 돌려 구할 수도 있다. 브루트포스 알고리즘 예시 문제 : n이 주어졌을때, 1부터 n 중에 2의 배수의 수는? (1

최대, 최소공배수 그리고 소수

최대공약수(GCD) 두 수 a,b의 공통된 약수중 가장 큰 수 - 구하는 방법 1. 2부터 시작해서 a,b로 공통되게 나누어 떨어지는 것중 최대값을 구한다. O(n) -> n은 a,b중 최소값 2. 유클리드 호제법을 사용하기 // 나는 주로 재귀를 사용하는 편 public int gcd(int a, int b){ if(a%b == 0) return b; return gcd(a,a%b); } //반복문을 사용하여 구할수도 있음 public int gcd(int a, int b){ int temp; while(true){ if(a%b == 0) return b; temp = a % b; a = b; b = temp; } } 위 코드는 유클리드 호재법을 사용해서 구현해본 코드이다. 최소공배수(LCM) - 최소..

약수

약수를 구하는 방법 1. 1부터 n까지 %연산을 활용하여 구하기 2. 1부터 루트n까지 %연산을 활용하여 구하기 루트n까지만 비교해도 되는 이유는 약수는 짝을 지어 있기 때문이다. 약수의 개수가 홀수일 경우 root를 씌어준 값이 약수가 된다.(루트n까지 확인해야한다.) 시간복잡도 1번 방법 : O(n) 2번 방법 : O(√n) // 1번 방법 O(n) int n = 121; for(int i = 1; i

수학 - Mod연산

Mod 연산 나머지 연산의 특징 (A + B) % C == ((A % C) + (B % C)) % C (A * B) % C == ((A % C) * (B % C)) % C (A - B) % C == ((A % C) - (B % C) + C) % C 나누기 연산을 제외하고는 분배법칙 처럼 Mod를 처리하고 사용 가능하다. (주의사항) '-' 연산일 경우 범위는 -C