2018.03.29
Question:
자연수 n을 입력받아, n의 각 자릿수의 합을 출력하게 하세요. Ex) n=123이면 출력값은 1+2+3=6
import java.util.*;
public class Solution {
public static int solution(int n) {
int answer = 0;
int tmp;
int c = (int) Math.log10(n);
for (int j = 1 ; j<=c+1 ; j++) {
tmp = n%10;
answer += tmp;
n = n/10;
}
return answer;
}
public static void main(String args[]) {
System.out.println("n의 각자릿수의 합은 : " + Solution.solution(123));
}
}
혹은
import java.util.*;
public class Solution {
public static int solution(int n) {
if (n == 0) {
return 0;
}
else {
return n%10 + solution((n - n%10)/10);
}
}
public static void main(String args[]) {
System.out.println("n의 각자릿수의 합은 : " + Solution.solution(123));
}
}
알 수 있었던 점:
1. 메소드를 static으로 선언하면 객체생성없이 사용할 수 있다.
2. (int) double하면 double의 정수부분만 남게 된다.(-2.3은 -2로, 2.3은 2로)
3. main함수는 반드시 static void가 붙는다. static은 JVM에서 main함수를 찾기 위함이고, void는 프로그램 끝으론 그 출력값을 사용하지 않으므로
4. tmp는 사실상 필요없고 answer += n%10;해도 됐었다.
5. 자연수의 자릿수를 알아내는 데에 로그(log)를 사용하지 않고도 가능한 방법으로는
String[] arr = Integer.toString(n).split(""); // 즉 n을 str으로 만들었다가 그것을 split해서 str 배열로 만들어서 arr의 length를 세기
String nStr = String.valueOf(n); // n을 str으로 만들어서 str의 length를 세기, 이후 Integer.parseInt사용해서 str을 int로
6. main함수의 위치는 가독성을 위해 제일 하단에 둔다. 클래스 내에 어디다 두든 상관은 없음
7. 모든 반복문은 순환문(recursion)으로 바꿀 수 있다. 순환문으로도 써보았다.
2018.03.30
Question:
길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다.
1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.
import java.util.*;
public class Solution {
public static boolean solution(int[] arr) {
boolean answer = true;
Arrays.sort(arr);
answer = Solution.src(arr, arr.length);
return answer;
}
public static boolean src(int[] arr, int i) {
if(i==0) {
return true;
}
else {
if(Arrays.binarySearch(arr, i) < 0) {
return false;
}
else
i -= 1;
return true&Solution.src(arr, i);
}
}
public static void main(String args[]) {
int[] a= {1,2,4,5};
System.out.println(Solution.solution(a));
}
}
혹은
import java.util.*;
class Solution {
public boolean solution(int[] arr) {
boolean answer = true;
Arrays.sort(arr);
if (arr[0]==1 && arr[arr.length-1]==arr.length)
answer=true;
else
answer=false;
return answer;
}
}
혹은
(sort를 쓰지않고)
import java.util.*;
class Solution {
public boolean solution(int[] arr) {
int k = arr.length;
int[] temp_arr = new int[k+1];
for(int i = 0 ; i<arr.length ; i++) {
if(arr[i]>arr.length) {
return false;
}
else {
temp_arr[arr[i]]++;
}
}
for(int j =1 ; j<=arr.length ; j++) {
if (temp_arr[j] != 1)
return false;
}
return true;
}
}
알 수 있었던 점:
1. 만약 필요조건인, int[] arr의 각 정수의 모든 합 == (arr.length*(arr.length+1))/2 를 넣어서할 수도 있지만, 그렇게 효율성이 늘어나는건 아닌듯 하다.
2. Arrays.binarSearch(arr, int k), k가 arr에 없을 때 음수가 나오며 어떤 음수가 나오는 지도 알 수 있었다.
예를 들면 {1,2,3,4}와 k=6이라면, k가 1보다 왼쪽인 수면 -1, 1과 2사이 수면 -2, 2와 3사이 수면 -3, 3과 4사이수면 -4, 4초과이면 -5
3. 첫번째 방법은 sort에 binarySearch까지 반복으로 쓰니까, 효율성이 굉장히 떨어져서 통과하지 못했다.
4. 재귀함수를 쓰게되면, 함수호출이 잦아지고, 그럼 효율성이 떨어진다고한다. 아직까진 구체적인 그 의미를 모르겠다. 함수호출시 컴퓨터의 자원이 어떻게 쓰이는 지를 모르기 때문이다.
5. 마지막으로 가장 최적화시킨 방법, index를 활용하는 방법이다. 배열의 index에 자연수를 포함하므로, for문을 2번 써서 가능했다.
6. 기본적으로 Arrays.sort(arr)는 input array의 size에 따라 size가 적을 땐 Insertion Sort, 클 땐 Merge Sort를 사용한다. 각각의 방법을 공부해야할 필요가 있다.
2018.03.31
Question:
(1) 임의의 자연수n에 대해 n을 소인수분해하는 알고리즘을 조사하여라.
(2) 완전수 구하기. 자연수 n을 input으로 넣고, 그것보다 같거나 작은 자연수 중에서 완전수들을 output으로
https://www.alpertron.com.ar/ECM.HTM // elliptic curve method와 self-initializing quadratic sieve를 써서 계산해주는 웹사이트