반응형
이번 글에서는 백준 28278번 문제를 통해
스택(자료구조)를 구현하고 활용해 보자.

문제 핵심

  • N : 명령의 수 ( 1 <= N <= 1,000,000 )
  • 명령 1 ~ 5 까지 주어진다.
  • 1. Push
  • 2. Pop
  • 3. Size
  • 4. IsEmpty
  • 5. Peek
  • 명령은 하나씩 주어진다.

풀이 과정

다음 문제는 스택을 구현하고 처리하는 과정이라고 할 수 있다.

 

1. 함수 구현하기

1 ~ 5의 명령어와 같이 스택에 필요한 함수들을 구현하자.

	private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    private static void push(int num) {
        list.addFirst(num);
    }

 

문제에 맞게 명령어들을 변형하여 함수를 구현하였다.

2. 구현한 함수 활용하기 ( Main 작성 )

  • 문제를 다음과 같이 풀었지만, 1 ~ 5의 단순한 숫자나 문자열로 처리할 경우 Switch문이 더 적합하며 범위 계산이나 null 값 계산 등이 아니라면 Switch문으로 처리하는 것이 좋아 보인다.
  • List 는 JAVA의 LinkedList<> 클래스를 활용하였다.
    • ArrayList or List를 활용해서 사용할 수 있기도 하지만, 미리 만들어두는 구조보다는 문제제목과 같은 자료구조에 맞춰서 사용하였다.
private static final LinkedList<Integer> list = new LinkedList<>();

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

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

 

 

스택 ( 자료구조 ) - JAVA

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

p-coding.tistory.com

 

백준에서는 여러 프로그래밍 언어 중 Java가 비교적 느린 편이기 때문에, 많은 사람이 속도 최적화에 집중하거나 단순히 문제를 해결하는 데만 초점을 맞춰 코드를 작성하는 경우가 많다. (물론 브론즈 ~ 실버 수준의 문제에서는 속도 차이가 크게 중요하지 않다.)

하지만 이러한 문제의 핵심은 스택을 직접 구현하고 이해하는 것에 있다.


예를 들어, 명령어가 4일 때 list.isEmpty() ? 1 : 0을 사용하면 간편하게 해결할 수 있다.
그러나 이는 LinkedList 클래스의 isEmpty() 메서드를 활용한 것이지,
우리가 구현해야 할 스택의 isEmpty()가 아니다.

비록 같은 기능을 수행하지만, 개념적으로 다른 의미를 가진다.


즉,
문제를 통과하는 것에만 집중하기보다는, 정확한 개념을 이해하고 접근하는 것이 더 중요하다.


전체 코드

물론 다음 코드도 완벽하지는 않다.

package org.example;

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 final LinkedList<Integer> list = new LinkedList<>();

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

        int num = Integer.parseInt(bufferedReader.readLine());
        StringTokenizer stringTokenizer;

        String command;

        for (int i = 0; i < num; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            command = stringTokenizer.nextToken();

            if (command.equals("1")) {
                push(Integer.parseInt(stringTokenizer.nextToken()));
            } else if (command.equals("2")) {
                stringBuilder.append(pop())
                        .append("\n");
            } else if (command.equals("3")) {
                stringBuilder.append(list.size())
                        .append("\n");
            } else if (command.equals("4")) {
                stringBuilder.append(isEmpty())
                        .append("\n");
            } else if (command.equals("5")) {
                stringBuilder.append(peek())
                        .append("\n");
            }

        }
        System.out.println(stringBuilder);
    }

    private static int isEmpty() {
        if (list.isEmpty()) {
            return 1;
        }
        return 0;
    }

    private static Integer peek() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.getFirst();
    }

    private static Integer pop() {
        if (list.isEmpty()) {
            return -1;
        }
        return list.removeFirst();
    }

    private static void push(int num) {
        list.addFirst(num);
    }
}
반응형
반응형
Integer와 Int 같은 정수형을 나타내는 자료형으로 볼 수 있다.
하지만 이는 객체와 기본형으로 다르게 같지만서도 다르다.
이번에는 그 차이를 알아보자.

1. primitive type ( 기본형 )

  • 값 자체를 스택 메모리에 직접 저장하는 Primitive 즉, 원시적인 자료형이다. 
  • 별도의 정의가 필요없이 사용할 수 있으며 고정된 크기를 차지한다.
  • 메소드를 사용할 수 없으며 값을 직접 저장하기 때문에 null 을 저장할 수 없습니다.
자료형 데이터 형태 메모리 크기 표현 가능 범위
boolean 논리형 1byte true / false
char 문자형 2byte 유니코드
byte 정수형 1byte -128 ~ 127
short 2byte -32,768 ~ 32,767
int 4byte -2,147,483,648
~ 2,147,483,647
long 8byte -9,223,372,036,854,775,808
~ 9,223,372,036,854,775,807
float 실수형 4byte ±3.40282347E+38
(7자리 유효숫자)
double 1byte ±1.79769313486231570E+308
(15자리 유효숫자)

 

2. Wrapper Class ( 객체형 )

  • 값은 힙 메모리에 객체에 저장되고, 스택 메모리는 그 객체를 가리키는 주소값을 저장한다.
  • 참조형 데이터이기 때문에 추가적인 메모리가 소모된다.
  • 기본 상태는 null로 초기화 된다.
Wrapper Class 자료형
Boolean boolean
Character char
Byte byte
Short short
Integer int
Long long
Float float
Double double

 

3. 메모리 구조 예시 ( 정수 )

다음과 같은 코드를 적용할 때 그림과 같이 메모리에 할당된다.

int num = 10;
Integer num = Integer.valueOf(num);

 


차이점 요약

특징 Primitive Type Wrapper Class
저장 위치 스택 힙 + 스택
메모리 사용량 고정적 더 많은 메모리 필요
속도 비교적 빠름 비교적 느림
null 허용 불가능 가능
객체 메서드, 컬렉션 사용 여부 불가능 가능

 

 

Wrapper Class는 제네릭 형태로 자주 사용되며,
특히 List<Integer> 와 같은 컬렉션 프레임워크에서 흔히 활용된다.
간단한 코드에서는 당연하게 사용하지만,
방대한 코드 작성 시에는 메모리나 성능, 기능적 요소를 고려해야 한다.
이러한 상황에 닥쳤을 때 비로소 이유를 고민하기보다, 미리 원리를 이해하고 사용하면 더 효율적일 것이다.

 

반응형
반응형
이번 글에서는 백준 17103번 문제를 통해 소수 찾기 알고리즘인 에라토스테네스의 체를 활용,
이를 통해 소수를 찾고 짝수를 소수의 합으로 나타내보자.

문제 핵심

  • N : 짝수
    • 2 < N <= 1,000,000
  • 두 개의 소수의 합이다.
  • 순서만 다른 것은 같은 파티션이다.

풀이 과정

다음 문제는 소수를 먼저 찾아서 합을 구하면된다.

즉, 에라토스테네스의 체를 활용 소수를 효율적으로 구할 수 있다.

 

소수 찾기 ( 에라토스테네스의 체 ) - JAVA

에라토스테네스의 체 는 소수를 찾는 쉽고 빠르게 찾을 수 있는 방법이다.( 고대 그리수 수학자 에라토스테네스가 발견 ) 알고리즘다음과 같은 알고리즘을 따른다.0 ~ 50 까지의 수를 찾고자 할

p-coding.tistory.com

 

1. 소수 찾기

먼저 소수를 분별한다. ( max값을 찾아서 할 수 있지만 최대값 1,000,000인 점을 감안 미리 1,000,000까지 소수를 찾는다. )

    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

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

 

2. 골드 바흐 파티션 구성

1. 양쪽에서 숫자를 줄여가며 소수 체크를 한다. ( 이 때 양쪽에서 검사하기 때문에 절반만 사용한다. )

2. 둘 다 소수일 때 count를 증가시킨다.

3. count를 반환한다.

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }

 

 

 


미리 찾아둔 소수를 활용하고 반복문을 효율적으로 사용하면 비교적 쉬운 문제이다.
1,000,000 이하의 소수는 미리 생성해도 처리 가능하지만,
숫자가 매우 커질 경우에는 입력값의 최대값을 기준으로 소수를 구하는 것이 더 효율적이다.

이번 문제는 두 수의 합이 N이 되어야 하므로, 다음과 같은 방식이 적합하다.다만, 이전에 선택 정렬 문제에서 사용한 인덱스를 활용한 방식으로 데이터를 저장하는 방법도 고려할 수 있다.

 

전체 코드

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

public class Main {

    private static boolean[] isPrime;

    public static void main(String[] args) throws IOException {
        solve();
    }

    private static void solve() throws IOException {

        sieveOfEratosthenes(1000000);

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        for(int i = 0;i<N;i++){
            int num = Integer.parseInt(bufferedReader.readLine());
            String result = String.valueOf(findGBPartitions(num));
            stringBuilder.append(result)
                    .append("\n");
        }

        System.out.println(stringBuilder);
    }


    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

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

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }
}

 

반응형
반응형

 

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

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

 

알고리즘

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

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
반응형

문제

JLabel을 활용하여 "Love Java"를 출력하고, "Love Java" 글자 위에 마우스를 올려 마우스 휠을 위로 굴리면 글자가 작아지고, 아래로 굴리면 글자가 커지도록 프로그램을 작성하라. 폰트 크기는 한 번에 5픽셀씩 작아지거나 커지도록 하고, 5픽셀 이하로 작아지지 않도록 해라.

 

소스 코드

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Main7 extends JFrame{
	public Main7() {
		setTitle("마우스 휠을 굴려 폰트 크기 조절");
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		Container c = getContentPane();
		c.setLayout(new FlowLayout());
		
		JLabel la = new JLabel("Love Java");
		la.addMouseWheelListener(new MouseWheelListener() {
			public void mouseWheelMoved(MouseWheelEvent e) {
				int n = e.getWheelRotation();
				int size = la.getFont().getSize();
				if(n<0&&size>5) {
					la.setFont(new Font("Arial",Font.PLAIN,size-5));			
				}
				else {
					la.setFont(new Font("Arial",Font.PLAIN,size+5));
				}
			}
		});
		c.add(la);
		setSize(500,500);
		setVisible(true);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main7();
	}

}
반응형
반응형

문제

클릭 연습용 스윙 응용프로그램을 작성하라. "C"를 출력하는 JLabel을 하나 만들고 초기 위치를 (100, 100)으로 하고, "C"를 클릭할 때마다 컨텐트팬 내에 랸덤한 위치로 움직이게 하라.

 

소스 코드

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Main6 extends JFrame{
	public Main6() {
		setTitle("클릭 연습 용 응용프로그램");
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		Container c = getContentPane();
		
		c.setLayout(null);
		
		JLabel l = new JLabel("C");
		l.setSize(10,10);
		l.setLocation(100, 100);
		
		c.add(l);
		
		l.addMouseListener(new MouseAdapter() {
			public void mouseClicked(MouseEvent e) {
				int x = (int)(Math.random()*250);
				int y = (int)(Math.random()*250);
				l.setLocation(x, y);
			}
		});
		
		setSize(300,300);
		setVisible(true);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main6();
	}

}
반응형
반응형

문제

JLabel 컴포넌트로 "Love Java"를 출력하고, 키 리스너를 작성하여 + 키를 치면 폰트 크기를 5픽셀씩 키우고, - 키를 치면 폰트 크기를 5픽셀씩 줄이는 스윙 응용프로그램을 작성하라. 5픽셀 이하로 작아지지 않도록 하라.

 

소스 코드

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class Main5 extends JFrame{
	public Main5() {
		setTitle("+,-키로 폰트 크기 조절");
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		Container c = getContentPane();
		
		JLabel label = new JLabel("Love Java");
		label.setFont(new Font("Arial",Font.PLAIN,10)); // Arial 폰트로 10픽섹 크기
		Font f = label.getFont();

		c.setLayout(new FlowLayout());
		
		c.addKeyListener(new KeyAdapter() {
			public void keyPressed(KeyEvent e) {
				int size = f.getSize();
				if(e.getKeyCode() == KeyEvent.VK_ADD || e.getKeyCode()==KeyEvent.VK_EQUALS) { // 전자는 숫자패드의 + 후자는 Shift와 함께쓰는 버튼입니다.
					label.setFont(new Font("Arial",Font.PLAIN,size+5));
				}
				// 플러스와 동일
				else if((e.getKeyCode() == KeyEvent.VK_MINUS || e.getKeyCode() == KeyEvent.VK_SUBTRACT) && size > 5) {
					label.setFont(new Font("Arial",Font.PLAIN,size-5));
				}
			}
		});
		
		c.add(label);
		
		setSize(300,200);
		setVisible(true);
		
		c.setFocusable(true);
		c.requestFocus();
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main5();
	}

}
반응형
반응형

문제

JLabel을 활용하여 "Love Java"를 출력하고 왼쪽 화살표 키(<Left> 키)를 입력할때마다 "ove JavaL", "ve JavaLo", "e JavaLov"와 같이 한 문자씩 왼쪽으로 회전하는 프로그램을 작성하라.

 

소스 코드

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Main4 extends JFrame{
	public Main4() {
		setTitle("Left 키로 문자열 이동");
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		Container c = getContentPane();
		
		JLabel label = new JLabel("Love Java"); 
		c.setLayout(new FlowLayout());
		
		c.addKeyListener(new KeyAdapter() {
			public void keyPressed(KeyEvent e) {
				if(e.getKeyCode() == KeyEvent.VK_LEFT) {  
					label.setText(label.getText().substring(1) + label.getText().charAt(0));
				}		
			}
		});
		
		c.add(label);
		
		setSize(300,100);
		setVisible(true);
		
		c.setFocusable(true);
		c.requestFocus();
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main4();
	}

}
반응형
반응형

문제

JLabel을 활용하여 "Love Java"를 출력하고 왼쪽 화살표 키(<Left> 키)를 입력할 때마다 "avaJ evoL"와 "Love Java"를 번갈아 출력하는 스윙 프로그램을 작성하라

 

소스 코드

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;

public class Main3 extends JFrame{
	public Main3() {
		setTitle("Left 키로 문자열 교체");
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		Container c = getContentPane();
		
		JLabel label = new JLabel("Love Java"); 
		c.setLayout(new FlowLayout());
		
		c.addKeyListener(new KeyAdapter() {
			public void keyPressed(KeyEvent e) {
				if(e.getKeyCode() == KeyEvent.VK_LEFT) {  
					if(label.getText().equals("Love Java")) {
						label.setText("avaJ evoL");
					}
					else if(label.getText().equals("avaJ evoL")) {
						label.setText("Love Java");	
					}
				}		
			}
		});
		
		c.add(label);
		
		setSize(300,100);
		setVisible(true);
		
		c.setFocusable(true);
		c.requestFocus();
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main3();
	}

}
반응형
반응형

문제

컨텐트팬의 배경색은 초록색으로 하고 마우스를 드래깅하는 동안만 노란색으로 유지하는 스윙 응용프로그램을 작성하라.

 

소스 코드

import javax.swing.*;
import java.awt.event.*;
import java.awt.*;

public class Main2 extends JFrame{
	public Main2() {
		setTitle("드래깅동안 YELLOW...");
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		
		Container c = getContentPane();
		Panel p = new Panel();
		p.setBackground(Color.green);
		
		p.addMouseMotionListener(new MouseAdapter() {
			public void mouseDragged(MouseEvent e) {
				p.setBackground(Color.yellow);
			}
		});
		p.addMouseListener(new MouseAdapter() {
			public void mouseReleased(MouseEvent e) {
				p.setBackground(Color.green);
			}
		});
		c.add(p);
		
		setSize(300,200);
		setVisible(true);
	}
	public static void main(String[] args) {
		new Main2();
		
	}

}

 

반응형

+ Recent posts