반응형
이번 글에서 백준 11866번 문제를 통해 요세푸스 순열을 활용,
이를 통해 원형 큐와 결합하여 사용해보자.

문제 핵심

    • N : 사람 수
    • K : 건너뛸 수
    • ( 1 <= K <= N <= 1,000 )

풀이 과정

다음 문제는 요세푸스를 순열을 통해 한 사람씩 제거해 나가는 문제이다.

다음 글을 통해 개념을 참고하면 좋을 것 같다. 비교적 간단하다.

 

플라비우스 요세푸스 순열

요세푸스 순열은 유대인 역사가 플라비우스 요세푸스의 이야기에서 유래한 수학적 문제이다.요세푸스의 이야기1세기 로마 제국 시대, 유대인은 로마에 대항하여 대규모 반란을 일으켰다.이 때,

p-coding.tistory.com

 

1. 반복

해당 문제는 K의 배수마다 값을 꺼내오면 된다.

때문에 이전 값들은 모두 다시 큐의 뒤에 넣어주고 그 과정을 마지막 한 사람이 남을 때까지 반복해준다. 

        while(1 < queue.size()) {
            count++;
            if(count % K == 0){
                stringBuilder.append(queue.remove() + ", ");
                continue;
            }
            queue.add(queue.remove());
        }

 

2. 출력

백준의 문제 출력 조건에 따라 마지막 값은 기호와 함께 처리해 준다.

        stringBuilder.append(queue.remove() + ">");
        System.out.println(stringBuilder);

이번 문제는 큐의 개념과 요세푸스 순열을 이해하고 있다면, 
결합하여 아주 쉽게 풀 수 있는 문제이다.
요세푸스 문제는 재귀로도 풀 수 있는 만큼 한 번 시도해보는 것도 좋다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Queue<Integer> queue = new LinkedList<Integer>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("<");
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int K = Integer.parseInt(stringTokenizer.nextToken());


        for(int i = 0; i < N; i++) {
            queue.add(i + 1);
        }
        int count = 0;

        while(1 < queue.size()) {
            count++;
            if(count % K == 0){
                stringBuilder.append(queue.remove() + ", ");
                continue;
            }
            queue.add(queue.remove());
        }

        stringBuilder.append(queue.remove() + ">");
        System.out.println(stringBuilder);

    }
}
반응형
반응형
요세푸스 순열은
유대인 역사가 플라비우스 요세푸스의 이야기에서 유래한 수학적 문제이다.

요세푸스의 이야기

1세기 로마 제국 시대, 유대인은 로마에 대항하여 대규모 반란을 일으켰다.
이 때, 요세푸스는 유대 반군의 장군 중 한명으로 로마군에 의해 포위당했다.
전투에서 패배한 요세푸스와 동료들은 로마군에 항복하는 대신 자결하는 것을 택했다.
하지만 자결하는 것은 두려웠는지 원형으로 앉았고, 특정 규칙에 따라 순차적으로 서로 죽여주는 방식을 택했다.
1. 특정 수의 인원을 건너 뛰고 다음 사람을 제거한다.
2. 마지막 한 사람이 남을 때까지 반복.
그러나 요세푸스는 동료들의 뜻에 반대하여 살고 싶었고, 위 규칙을 이용하여 마지막 한 사람이 되어 로마군에 항복하였다.

 

공식

일반적인 공식은 다음과 같다. 

n : 인원 수

k : 건너뛸 수

재귀함수 형식을 띄고 있다.

 

 

예시)

f( 7, 3 ) 인 경우

idx f( N, K ) ( N + K ) mod N  result
1 (7, 3) (0 + 3) % 7 3
2 (6, 3) (3 + 3) % 6 0
3 (5, 3) (0 + 3) % 5 3
4 (4, 3) (1 + 3) % 4 0
5 (3, 3) (1 + 3) % 3 1
6 (2, 3) (0 + 3)  % 2 1
7 (1, 3) N = 1 0

 

코드

재귀 코드로 구현하면 다음과 같이 구현할 수 있다.

package org.example;

public class Main {
    public static int josephus(int N, int K) {
        if (N == 1) return 0;
        return (josephus(N - 1, K) + K) % N; // 재귀 호출
    }

    public static void main(String[] args) {
        int N = 7;
        int K = 3;
        System.out.println("Last survivor: " + (josephus(N, K) + 1));
    }
}

 

결과 ( 마지막 생존 자리 )

4

 

이번에는 재귀함수로 해결하였지만, 원형 큐 등 다양한 방법들이 있다.
생존을 위해서 역사가의 새로운 순열 공식
순차적인 제거 문제에서 다양하게 사용되고 있다.
반응형
반응형
이번 글에서는 4949번 문제를 통해 스택을 활용,
괄호의 균형을 맞춰완벽한 문장을 나타내 보자.


 

 

문제 핵심

  • 문자열은 ( ),  [ ] 이 두 소괄호와 대괄호가 짝을 이루어야 한다.
  • 1 : 1 매칭만 가능하다.
  • 공백 이후의 . 과 같은 괄호가 없는 문장도 균형 잡힌 문자열이다.
  • (, [ 이 나온 후에 ), ] 가 나와야 짝이 이루어 진다. 
    • ] [ 은 짝이 아닌 경우 

풀이 과정

먼저 우리가 찾아야 할 것은 괄호들이다.

이는 StringTokenizer를 활용해 볼 예정이다. ( 물론 chatAt()을 사용하면 더 빠르다. )

다음 자료구조 스택에 대한 글과 split과 StringTokenizer비교에 관한 글을 참고하면 좋을 것 같다.

 

 

스택 ( 자료구조 ) - JAVA

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.접시를 쌓아올린다고 생각하면 된다.스택 ( Stack )후

p-coding.tistory.com

 

 

[ JAVA ] 문자열 자르기 Splite VS StringTokenizer

문자열을 특정 구분자로 분리할 수 있는 StringTokenizer와 Splite을 사용하던 중구체적인 차이점이 무엇인지 궁금하여 조사하게 되었다.메모리에서 장점을 가진다고 하지만 정확히 어떤구조로 작용

p-coding.tistory.com

 

 

1. 괄호 문자 저장

먼저 StringTokenizer를 통해 소괄호, 대괄호를 기준으로 문자를 나눈다.

그렇게 되면 구분자를 저장하는 StringTokenizer의 특성을 활용해 문자를 가져올 수 있다.

true로 설정하면 구분자도 Token에 포함된다.

stringTokenizer = new StringTokenizer(sentence,"([)]",true);

 

2. 괄호 문자 찾아 균형확인하기

1. 구분자에 포함된 토큰 중에 괄호를 찾는다.

2. (, [ 라면 스택에 넣는다

3 - 1. ], ) 라면 스택에서 꺼내 비교한다

3 - 2. 이 때, 동일한 모양의 괄호 즉, )일 때 ( 괄호가 나오지 않는다면 균형이 맞지 않는 문자열로 처리

while(stringTokenizer.hasMoreTokens()) {

    String token = stringTokenizer.nextToken();

    if (token.equals("(") || token.equals("[")) {
        push(token);
    }
    else if (token.equals(")")) {
        if (!pop().equals("(")) {
            isPerfect = false;
            break;
        }
    }
    else if (token.equals("]")) {
        if (!pop().equals("[")) {
            isPerfect = false;
            break;
        }
    }
}

 

 

3. 스택에 남아있는 값 확인

마지막으로 스택에 남아 있는 경우 즉, (() 와 같은 문자열이 들어온다면 ( 이 스택에 남아 균형이 맞지 않는다.

if (!delimStack.isEmpty()) isPerfect = false;

 

스택을 활용하여 푸는 문제로 괄호를 저장하고 저장한 값을 꺼내 올 때,
다양한 경우에 대비하여 반론이 없게 푸는 것이 중요하다.
이번 문제는 빠르게 풀 수도 있지만, charAt함수가 아닌 StringTokenizer를 사용하듯이
다양한 방법으로 풀어보는 것을 추천한다.



전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

    private static LinkedList<String> delimStack;

    private static void push(String delim){
        delimStack.addLast(delim);
    }

    private static String pop(){
        return delimStack.isEmpty() ? " " : delimStack.removeLast();
    }


    public static void main(String[] args) throws IOException {
        delimStack = new LinkedList<>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();

        boolean isPerfect;
        StringTokenizer stringTokenizer;

        while (true) {
            isPerfect = true;
            delimStack.clear();
            String sentence = bufferedReader.readLine();

            if(sentence.equals(".")) break;

            stringTokenizer = new StringTokenizer(sentence,"([)]",true);


            while(stringTokenizer.hasMoreTokens()) {

                String token = stringTokenizer.nextToken();

                if (token.equals("(") || token.equals("[")) {
                    push(token);
                }
                else if (token.equals(")")) {
                    if (!pop().equals("(")) {
                        isPerfect = false;
                        break;
                    }
                }
                else if (token.equals("]")) {
                    if (!pop().equals("[")) {
                        isPerfect = false;
                        break;
                    }
                }
            }

            if (!delimStack.isEmpty()) isPerfect = false;


            stringBuilder.append(isPerfect ? "yes\n" : "no\n");
        }

        System.out.println(stringBuilder);
    }
}
반응형
반응형
오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.
가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.
접시를 쌓아올린다고 생각하면 된다.


스택 ( Stack )

  • 후입 선출 ( LIFO, Last In First Out )
  • 한쪽 끝에서만 데이터 삽입( push )과 삭제( pop )가 이루어짐
  • 재귀 호출, 백트래킹, 수식 계산 등 다양한 알고리즘에서 활용됨
    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

스택의 기본 연산

1. push(value): 데이터 삽입

  • 스택의 맨 위(top)에 데이터를 추가하는 연산
    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

2. pop(): 데이터 제거

  • 스택의 맨 위(top)에 있는 데이터를 제거하고 반환하는 연산
  • 만약 스택이 비어 있다면 언더플로우(Underflow, 데이터 부족 에러) 발생
    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

3. peek() (또는 top()): 최상단 데이터 확인

  • 스택의 맨 위(top)에 있는 데이터를 반환하지만, 제거하지 않음
    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

4. isEmpty(): 스택이 비어 있는지 확인

  • 스택이 비어 있으면 true, 아니면 false 반환
    public boolean isEmpty() {
        return top == -1;
    }

 

로직 예시)

왼쪽 위부터 오른쪽으로 진행된다

 

1. 빈 스택이다

2. push를 통해 값 ( 1 ) 을 넣었다. 이 때 top은 1을 가리킨다

3. push를 통해 값 ( 2 ) 을 넣었다. 이 때 top은 2를 가리킨다.

4. peek를 통해 값 ( 2 ) 을 받았다.

5. pop을 통해 값 ( 2 ) 를 꺼냈다. 이 때 top은 1을 가리킨다.

6. pop을 통해 값 ( 1 ) 를 꺼냈다. 이 때 top은 아무것도 가리키지 않는다. ( -1 상태 )

 

배열을 활용하여 스택에 대해 설명했지만, 
List 클래스 ( 하위 클래스 포함 ArrayList 등 ) 으로도 구현 가능하다.
 개념을 이해하고 상황에 맞게 사용하면 된다.

전체 구현 코드

package org.example;


public class TestStack {
    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}
반응형
반응형
이번 글에서는 백준 28116번 문제를 통해 선택 정렬 알고리즘을 활용하고,
이를 통해 성능 최적화 방안을 탐구해보려 한다.
선택 정렬의 기본 개념을 바탕으로 문제 해결 과정과 효율성을 높이는 방법을 단계별로 살펴보자.

 

문제 핵심

  • 이 배열은 N까지의 정수가 정확히 한 번씩 등장한다. 즉 중간에 빠진 정수나 중복된 수가 존재하지 않는다.
  • 선택 정렬 알고리즘을 사용하여 주어진 배열을 정렬한다
  • 이 과정에서 교환이 이루어질 때 이동한 거리를 각각 저장한다.
  • N : 배열의 길이

풀이 과정

이전의 선택정렬의 문제와 같이 2중 반복을 통해 풀었다. 하지만 이번의 N의 최대길이가 다르다.

지난 번 23881번 문제에서는 N이 10,000 즉, O(N^2)의 시간 복잡도를 가지더라도 10,000,000의 연산을 한다.

하지만 이번 문제는 N이 500,000으로 어마 어마한 숫자다. 특히 자바로 문제는 푸는 나에게는 더욱 더 좋지 않은 상황이다. 

    private static void solve() {

        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                 if(arr[j] < arr[minIndex]) {
                     minIndex = j;
                 }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;

                int distance = minIndex - i;
                arrSwapCount[arr[minIndex] - 1] += distance;
                arrSwapCount[arr[i] - 1] += distance;
            }
        }
    }

 

[ 문제 ] 시간 초과

그렇다면 위 코드는 아무리 줄여나가도 2중 반복이라는 한계로 시간초과의 문제를 해결할 수 없다. 어떻게 해야 할까?

한 개의 반복문에 모두 녹여내야 한다. 코드 몇 줄 최적화 시킨다고 해서 나아질 문제가 아닌 것이다. 

 

문제 해결

문제를 고민하던 중, 제한 조건에 있던 "각 정수는 N까지 정확히 한 번씩 등장한다"는 점이 눈에 들어왔다. 이 조건을 활용하면 인덱스를 이용한 접근이 가능하다고 판단했다. 이를 바탕으로, "위치를 저장하는 배열과 기존의 정렬 대상 배열을 비교하며 값을 처리할 수 있을 것"이라는 아이디어를 떠올렸다. 그 후, 이 규칙을 기반으로 점차 로직을 구체화하며 코드를 작성했다.

 

과정은 다음과 같다. ( 백준 두 번째 예시값 )

 

1. 초기화 단계

먼저 주어진 배열이 다음과 같이 저장되고, 값의 위치를 저장하는 배열로 두개를 선언한다.

 

0부터 시작하는 특성으로 num - 1을 선언하였으나

헷갈리지 않게 사용하려면 배열을 N + 1 만큼 사용하고 0 인덱스를 제외하여 사용하면 된다.

아래 그림에 실제 가르키는 값은 다음과 같다. 제외하고 봐도 무방하다.

    private static int[] arr;
    private static int[] numLocations;
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }

 

그림과 같이 저장된다.

 

2. 알고리즘 단계

위 그림을 보면 감이 올지도 모른다.

한 개의 반복문에서 index를 활용하여 매치 시키고, 위치에 있어야 할 값과 맞지 않는다면

해당 위치에 있는 값원래 있어야 하는(순서에 맞는) 값을 찾고 거리값을 구한다. 

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[numLocations[arr[i]]] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }

i = 0 일때

0 = 0 ( 실제로는 1 = 1 ) 이므로 위치에 맞게 존재한다.

i = 1 일때 ( num - 1 인 것을 감안해야 한다 )

위 그림과 같이 i = 1 ( 두 번째 위치) 에 1 (2) 이 있어야 한다.

그렇다면 numLocation[1] 을 통해 원래 있어야 하는 값의 위치를 찾는다.

왼쪽부터 정렬하며 오기 때문에 i값은 항상 작다. 때문에 numLocation[i] - i를 통해 거리를 계산 할 수 있다.

또한, 값의 교환이 할 필요는 없고, i 값에 해당하는 상태는 이제 필요없기 때문에 이 후 계산할 곳에만 값을 넣어준다.

이 후 distance의 값을  moveCount 배열에 더해주면 정수마다 이동한 거리 값이 계산된다.

 

나머지도 위를 통해 문제를 해결할 수 있다.

 

선택 정렬이라고 해서 무조건 2중 반복문을 사용하는게 아닌
그 틀은 그대로 유지하며 다르게 풀어나갈 수 있다는 것
활용하는 것이 가장 중요하다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int[] arr;
    private static int[] numLocations;
    private static int[] moveCounts;

    public static void main(String[] args) throws IOException {
        prepre();
        solve();
        Arrays.stream(moveCounts).forEach(num -> System.out.print(num + " "));
    }

    private static void prepre() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        arr = new int[N];
        numLocations = new int[N];
        moveCounts = new int[N];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(stringTokenizer.nextToken());
            arr[i] = num - 1;
            numLocations[num - 1] = i;
        }
    }

    private static void solve() {
        for (int i = 0; i < numLocations.length; i++) {
            if (arr[i] != i) {
                int distance = numLocations[i] - i;

                moveCounts[i] += distance;
                moveCounts[arr[i]] += distance;

                arr[numLocations[i]] = arr[i];
                numLocations[arr[i]] = numLocations[i];
            }
        }
    }
}
반응형
반응형
요즘 다시 알고리즘 공부를 시작하려고 하여
백준에서 문제를 풀어나가며 알고리즘을 따로 정리, 기술하는 방향으로 계획하고 있다.
그 중 정렬 알고리즘을 먼저 살펴보려고 하며,
오늘은 기본 중 하나인 선택 정렬를 알아보고자 한다.

선택 정렬 ( Selection Sort )

 

선택 정렬은 간단하지만 비효율적인 정렬 알고리즘 중 하나로, 배열에서 가장 큰 or 가장 작은 값을 찾아 현재 위치에 배치하는 과정을 반복하여 정렬된다.

 

순서는 다음과 같다.

 

1. 정렬되지 않은 부분에서 최솟값 or 최댓값 찾기

 

2. 현재 위치와 최솟 값 or 최대 값 교환

 

3. 다음 위치로 이동하며 반복


 

다음 그림과 같이 예시로 알아보자

5개의 정수 값을 가진 배열 Array가 존재한다.

이를 오름차순으로 왼쪽부터 최솟값을 찾아 정렬하고자 한다.

 


 

기본 형태

4 5 3 1 2

 


1회차

 

첫번 째 위치인 4를 기준

4 5 3 1 2

 

 

차례로 5, 3, 1, 2 와 비교

4 5 3 1 2

 

 

최솟값을 찾아 위치를 교환

4 5 3 1 2

 

 

1회차 완료

1 5 3 4 2

 


 

2회차

 

두번 째 위치인 5를 기준

1 5 3 4 2

 

 

차례로 3, 4, 2 와 비교

1 5 3 4 2

 

 

최솟값을 찾아 위치를 교환

1 5 3 4 2

 

 

2회차 완료

1 2 3 4 5

 

 

2회차만에 정렬되어 정렬된 배열은 다음과 같다.

1 2 3 4 5

전체 코드

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int [] arr = {6,4,2,1,3,5};
        selectionSort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }

    private static void selectionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        int minIndex;
        for(int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

 

 

구현은 쉽고 직관적이긴 하나,  선택 정렬은 앞서 말했듯 입력 배열에 관계없이(2회차에 정렬이 되었더라도)
외부 반복문에서 n -1 회, 내부 루프에서 n - 1, n - 2, ..., 1번 비교함으로
시간복잡도는 항상 O(n^2) 으로 비효율적이다. 

 

반응형
반응형

 

에라토스테네스의 체 는 소수를 찾는 쉽고 빠르게 찾을 수 있는 방법이다.

( 고대 그리수 수학자 에라토스테네스가 발견 )

 

알고리즘

다음과 같은 알고리즘을 따른다.

0 ~ 50 까지의 수를 찾고자 할때, 0과 1을 제외

 

1.  2부터 시작하여 2를 제외한 2의 배수를 모두 지운다.

  2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

 

2. 지워지지 않은 다음 숫자부터 1번과 같이 반복한다. ( 3을 제외한 3의 배수 지우기 )

  2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

 

3.  √50 = 7.071 이므로 구하는 수의 제곱근 이하의 소수, 즉, 7의 배수까지 제외하면 된다.

  2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

 

4. 제외 되지 않은 숫자가 소수

 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

 

Code

자바를 통해 다음과 같이 구현할 수 있다.

Boolean[] primeNumbers = new Boolean[number + 1]; // N이 0일 때, 0 ~ 100 까지 101개의 수
        primeNumbers[0] = false; // 1
        primeNumbers[1] = false; // 2

먼저 0 ~ 100까지의 101개의 배열을 생성해주고 0, 1은 제외 시킨다.

 

 // 모두 true로 초기화
 for (int i = 2; i <= number; i++) {
 	primeNumbers[i] = true;
 }

2부터 모두 소수라 가정하고 true로 지정한다. 

 

for (int i = 2; i <= Math.sqrt(number); i++) {
	if (primeNumbers[i] == false)
    	continue;
    for (int j = i + i; j <= number; j += i) {
    	primeNumbers[j] = false;
    }
}

에라토스테네스의 체 공식으로

1. 이미 제외시킨 숫자라면 다음 숫자

2. 제외시킨 숫자가 아니라면 그 수를 제외하고 배수를 false로 변환한다.

 

다음과 같은 결과를 얻을 수 있다.

 

전체 코드

import java.util.Scanner;

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

        System.out.print("2이상의 숫자를 입력해 주세요 : ");
        int N = scanner.nextInt();

        fintPrimeNumber(N);
    }

        private static void fintPrimeNumber(int number) {
        Boolean[] primeNumbers = new Boolean[number + 1]; // N이 0일 때, 0 ~ 100 까지 101개의 수
        primeNumbers[0] = false; // 1
        primeNumbers[1] = false; // 2

        // 모두 true로 초기화
        for (int i = 2; i <= number; i++) {
            primeNumbers[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (primeNumbers[i] == false)
                continue;
            for (int j = i + i; j <= number; j += i) {
                primeNumbers[j] = false;
            }
        }

        System.out.println();
        System.out.println(number + "이하의 소수 입니다.");
        
        for (int i = 0; i < primeNumbers.length; i++) {
            if (primeNumbers[i]) {
                System.out.print(i + " ");
            }
        }
    }
}
반응형

'알고리즘' 카테고리의 다른 글

플라비우스 요세푸스 순열  (2) 2025.02.28
[ 자료구조 ] 큐 ( Queue ) - JAVA  (0) 2025.02.26
스택 ( 자료구조 ) - JAVA  (0) 2025.02.04
[ 알고리즘 ] 선택 정렬  (2) 2024.12.12

+ Recent posts