ING

안녕하세요 Jin's 입니다.

백준 알고리즘의 팩토리얼 ( 문제 번호 : 10872)의 풀이입니다.

import java.util.Scanner;
 
public class Main {
 
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        System.out.println(factorial(n));
    }

    private static int factorial(int n){
        if(n<=1) return 1;
        return n*factorial(n-1);
    }
}

[ 링크 ]

https://www.acmicpc.net/problem/10872

* 선형 검색(순차검색)이란?

   배열 검색 중 가장 기본적인 알고리즘으로 요소가 직선 모양으로 늘어선 배열에서 원하는 키값을 찾을 때까지

   맨 앞부터 순서대로 요소를 검색하는 것

위의 표와 같이 배열이 존재할 경우 1을 찾기 위해 0, 1, 2, 3번째 배열을 모두 검색하는 방법이다.

선형검색을 하게되면 종료의 조건은 아래 두가지로 정의 할 수 있다.

   1) 검색값을 찾은 경우

   2) 검색값이 존재하지 않는 경우

이때 종료 판단 횟수를 줄이는 역할을 하게 되는 것이 보초법 이다.

* 보초란?

   검색하고자 하는 키 값을 맨 끝 요소에 저장하는 값이다. 

   일반배열에서 7이라는 값을 찾으려고 할때 아래와 같이 배열이 구성 된다.

    - 보초 넣은 배열

따라서 보초는 반복문에서 종료 판단 중 2)검색값이 존재하지 않는 경우를 체크하지 않아도 되게 함으로써 종료 판단을 2회에서 1회로 줄이는 역할을 한다.

아래는 보초법를 사용한 알고리즘 책의 p106 실습 3-3 예제입니다!

package chap03;

import java.util.Scanner;

public class SeqSearchSen {
    static int seqSearchSen(int[] a, int n, int key){
        int i=0;

        a[n] = key; //보초를 추가

        while (true) {
            if (a[i] == key) // 검색성공!
                break;
            i++;
        }
        return i == n ? -1 : i;
    }


    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.print("요솟수 : ");
        int num = stdIn.nextInt();
        int[] x = new int[num +1]; //요솟수 num+1인 이유는 보초값을 추가하기 위함

        for(int i=0;i<num; i++){
            System.out.print("x["+i+"] : ");
            x[i]= stdIn.nextInt();
        }

        System.out.print("검색할 값 : ");
        int ky = stdIn.nextInt();

        int idx = seqSearchSen(x, num, ky); //배열 x에서 값이 ky인 요소를 검색

        if(idx == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(ky+"은(는) x["+idx+"]에 있습니다.");
        }
    }
}

* 보충수업 3-1 무한루프

   do while문은 끝까지 읽어야만 무한 루프인지 알기 때문에 권장하지 않는다!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 직각삼각형 ( 문제 번호 : 4153 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

* 직사각형 공식 z² = x² + y²

1) JAVA

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true){
			ArrayList<Integer> list = new ArrayList<>();
			int x = 0;
			for(int i=0; i<3; i++){
				x = scan.nextInt();
				list.add(x);
			}
			if(x==0) break;

			list.sort(Comparator.naturalOrder());
			
			if(Math.pow(list.get(2), 2)== Math.pow(list.get(0), 2)+Math.pow(list.get(1), 2)){
				System.out.println("right");
			}else{
				System.out.println("wrong");
			}	
		}
		scan.close();
	}

}

2) PYTHON

while True:
    t = sorted(list(map(int, input().split())))
    if sum(t) == 0:
        break
    else:
        if t[2] ** 2 == (t[1] ** 2 + t[0] ** 2):
            print('right')
        else:
            print('wrong')

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 네 번째 점 ( 문제 번호 : 3009 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

1) JAVA

import java.util.HashMap;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		HashMap<Integer, Integer> x_map = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> y_map = new HashMap<Integer, Integer>();
		int x = 0;
		int y = 0;
		for(int i=0;i<3;i++){
			x = scan.nextInt();
			y = scan.nextInt();
			x_map.put(x, x_map.getOrDefault(x, 0)+1);
			y_map.put(y, y_map.getOrDefault(y, 0)-1);
		}
		
		for(Integer i : x_map.keySet()){
			if(x_map.get(i)==1){
				x = i;
			}
		}
		
		for(Integer i : y_map.keySet()){
			if(y_map.get(i)==-1){
				y = i;
			}
		}
		
		System.out.println(x+" "+y);
		scan.close();
	}

}

2) PYTHON

x_map = [0 for _ in range(3)]
y_map = [0 for _ in range(3)]

for i in range(3):
    x_map[i], y_map[i] = map(int, input().split())

for i in range(3):
    if x_map.count(x_map[i]) == 1:
        x = x_map[i]
    if y_map.count(y_map[i]) == 1:
        y = y_map[i]
print(x, y, end=" ")

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 직사각형에서 탈출 ( 문제 번호 : 1085 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

문제가 되게 심플한데 여기서 경계해야할 점은 직사각형의 경계는 중심축(빨간 굵은 선)도 포함이라는 점이다

(w-x,0)이 (x,0) 보다 클 수 있다는 점을 포함하여 코딩하면 된다. 

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int y = scan.nextInt();
		int w = scan.nextInt();
		int h = scan.nextInt();
		scan.close();
		int x_min = Math.min(w-x, x);
		int y_min = Math.min(h-y, y);
		if(x_min>y_min){
			System.out.println(y_min);
		}else{
			System.out.println(x_min);
		}
	}

}

2) PYTHON

x, y, w, h = map(int, input().split())
x_min = min(x, w-x)
y_min = min(y, h-y)
if x_min < y_min:
    print(x_min)
else:
    print(y_min)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 골드바흐의 추측 ( 문제 번호 : 9020 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

* 2n의 범위까지 나오는 소수들을 미리 구한 뒤 소수의 개수를 더해주는게 시간을 줄일 수 있다.

  반복해서 사용하게 될 경우 그때 그때 다시 계산해줄 필요가 없으므로 자바 또한 이러한 방식으로 바꿔서 풀면

  좋을 것 같다

* 이 문제의 포인트는 두 소수 차이가 적은 값을 구하는 것이다.

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		boolean[] num_list = new boolean[10001];
		for(int i=2; i<=10000; i++){
			int result = 0;
			int half = (int)Math.sqrt(i);
			if(i==1) result++;

			for(int j=2; j<=half; j++){
				if(i%j==0){
					result++;
					num_list[i]=false;
					break;
				}
			}
			
			if(result==0){
				num_list[i]=true;
			}
		}

		int t = scan.nextInt();
		for(int i=0; i<t; i++){
			int n = scan.nextInt();
			int k = n;
			int diff =n;
			for(int j=2; j<=n/2; j++){
				if(num_list[j] && num_list[n-j]){
					if(diff > (n-2*j)){
						k=j;
						diff = n-2*j;
					}
				}
			}

			System.out.println(k+" "+(n-k));
		}
		scan.close();
	}

}

2) PYTHON

import math
k = 10001
num_list = [True]*k
for i in range(1, k):
    if i == 1:
        continue
    for k in range(2, int(math.sqrt(i))+1):
        if i % k == 0:
            num_list[i] = False
            break

t = int(input())
for _ in range(t):
    n = int(input())
    k = n
    diff = n
    for i in range(2, n//2 + 1):
        if num_list[i] and num_list[n-i] and diff > (n-2*i):
            k = i
            diff = n-2*i
    print(k, n-k, end=" ")

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 베르트랑 공준 ( 문제 번호 : 4948 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true){
			int n = scan.nextInt();
			int cnt = 0;
			if(n==0) break;
			
			for(int i=n+1; i<=2*n; i++){
				int result = 0;
				int half = (int)Math.sqrt(i);
				if(i==1) result++;

				for(int j=2; j<=half; j++){
					if(i%j==0){
						result++;
						break;
					}
				}
				
				if(result==0){
					cnt++;
				}
			}
			System.out.println(cnt);
		}
		scan.close();
	}

}

2) PYTHON

   * 파이썬은 자바처럼 해결하게 될 경우 시간 초과가 뜨게 된다.

     따라서 2n의 범위까지 나오는 소수들을 미리 구한 뒤 소수의 개수를 더해주는게 시간을 줄일 수 있다.

     반복해서 사용하게 될 경우 그때 그때 다시 계산해줄 필요가 없으므로 자바 또한 이러한 방식으로 바꿔서 풀면

     좋을 것 같다

import math
k = 123456*2+1
num_list = [1]*k
for i in range(1, k):
    if i == 1:
        continue
    for k in range(2, int(math.sqrt(i))+1):
        if i % k == 0:
            num_list[i] = 0
            break

while True:
    n = int(input())
    sum = 0
    if n == 0:
        break
    for i in range(n+1, 2*n+1):
        sum += num_list[i]
    print(sum)

여러분도 한번 풀어보세요!

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 소수 구하기 ( 문제 번호 : 1929 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int m = scan.nextInt();
		int n = scan.nextInt();
		scan.close();
		
		for(int i=m; i<=n; i++){
			int result = 0;
			int x = (int)Math.sqrt(i);
			if(i==1) result++;

			for(int j=2; j<=x; j++){
				if(i%j==0){
					result++;
					break;
				}
			}
			
			if(result==0){
				System.out.println(i);
			}
		}
	}

}

2) PYTHON

import math
m, n = map(int, input().split())
for i in range(m, n+1):
    result = 0
    if i == 1:
        result += 1
        continue
    x = int(math.sqrt(i))
    for k in range(2, x+1):
        if i % k == 0:
            result += 1
            break

    if result == 0:
        print(i)

여러분도 한번 풀어보세요!