백준 감소하는 수(줄어드는 수)

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

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

접근 방식

최초엔 n까지 범위의 수를 생각했는데, 잘못 생각한 것이였고, 앞자리부터 점점 감소하는 수의 모든 경우의 수 중 몇번째인지 n으로 입력받아 찾는 문제

구현 방법

• 감소하는 수에 대해 모든 조합을 찾은 후 정렬해 수행
• 이 때 최대 수의 범위까지 1씩 더해가며 찾는 것이 아닌, 값이 들어갈 수 있는 범위에 대해서만 찾기

⇒

• 9876543210 까지가 최대 수
• 재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
• 기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
• 재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
• for문이 다 돌면 재귀호출 시행

풀이

package Baekjoon.gold;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class p1174 {

    static Stack<Long> st = new Stack<>();
    static ArrayList<Long> al = new ArrayList<>();

    static int count = 0;
    static int n;
    static StringBuilder sb = new StringBuilder();

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

        n = Integer.parseInt(br.readLine());

        /*
         0, 1, 2, 3, 4, 5, 6, 7, 8, 9
         10 | 20, 21 | 30, 31, 32 | 40, 41, 42, 43 | 50, 51, 52, 53, 54 |
         60, 61, 62, 63, 64, 65 | 70, 71, 72, 73, 74, 75, 76 |
         80, 81, 82, 83, 84, 85, 86, 87 | 90, 91, 92, 93, 94, 95, 96, 97, 98 |
         210 |320, 321, 310 | 410, 420, 421, 430, 431, 432
         */

        //9 -> 8 7 6 5 4 3 2 1 0
        //8 -> 7 6 5 4 3 2 1 0
        //7 -> 6 5 4 3 2 1 0
        //6 -> 5 4 3 2 1 0
        //5 -> 4 3 2 1 0
        //4 -> 3 2 1 0
        //3 -> 2 1 0
        //2 -> 1 0
        //1 -> 0

        // 10 20 21 30 31 32
        //9876543210 까지가 최대 수
        //재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
        //기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
        //재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
        //for문이 다 돌면 재귀호출 시행

        if(n <= 10){
            System.out.println(n-1);
            return;
        }
        recur(10);
        List<Long> list = al.stream().sorted().collect(Collectors.toList());

        long result = -1;
        if(list.size() >= n){
            result = list.get(n-1);
        }

        System.out.println(result);
    }

    private static void recur(long nowNum){
        for(long i = 0; i < nowNum; i++){
            count++;
            st.push(i);
            st.forEach(sb::append);
            al.add(Long.valueOf(sb.toString()));
            sb.setLength(0);
            recur(i);
            st.pop();
        }
    }
}

후기

최초에 문제를 잘못 읽었고, 이후엔 전체 탐색을 효율적으로 하기위한 노력(가지치기)을 하는 데 시간을 많이 썼음

AtomicInteger.class의 메서드를 탐방하다 발견하게 된 native 키워드 탐방

@IntrinsicCandidate
public final native boolean compareAndSetInt(Object o, long offset, int expected, int x);

native 키워드는 Java에서 네이티브 코드를 사용해 자바 코드로는 직접 수행하기 어려운 작업을 해결하기 위해 사용됨. Java는 기본적으로 플랫폼 독립성을 목표로 설계된 언어지만, 외부에 작업 수행을 맡기기도 한다.

native 키워드의 역할 및 특징

운영체제, 하드웨어 종속작업 처리

Java는 플랫폼 독립성을 가진 언어이지만, 운영 체제나 하드웨어에 종속적인 작업을 처리해야할 때 C/C++로 작성된 네이티브 코드를 호출해 운영 체제의 API나 하드웨어를 직접 제어해야 한다.

• 예:
  • 파일 시스템 접근 (FileInputStream, FileOutputStream)
  • 네트워크 소켓 관리
  • 그래픽 처리를 위한 GUI 라이브러리 (AWT/Swing)
  • 시스템 시간 가져오기 (System.currentTimeMillis())
  • concurrent(동시성) 관련 코드

성능 최적화

Java는 일반적으로 JVM 위에서 동작하므로 C/C++로 작성된 네이티브 코드에 비해 약간의 오버헤드가 존재. 특히, 자바의 네이티브 메서드는 속도가 중요한 저수준 작업에서 성능을 극대화하기 위해 사용.

• 예:
  • AtomicInteger와 같은 CAS (Compare-And-Swap) 연산은 C/C++로 구현된 네이티브 코드를 호출하여 고성능을 보장.
  • arraycopy()는 배열 복사를 네이티브 코드로 처리하여 높은 속도를 보장.

하드웨어 제어

Java는 추상화된 언어로, 하드웨어를 직접 제어하는 데 적합하지 않다. 하지만 네이티브 코드를 사용하면 Java 프로그램이 특정 하드웨어 장치를 제어하거나 센서 데이터를 읽을 수 있다.

• 예:
  • 임베디드 시스템에서 Java와 네이티브 코드를 조합해 사용.
  • 특정 하드웨어 기능 호출.

멀티스레딩 및 동기화

Java는 스레드 관리와 동기화 관련 기능을 제공하지만, JVM의 성능을 극대화하거나 플랫폼 종속적인 동기화 메커니즘을 사용하기 위해 네이티브 메서드가 필요할 수 있다.

• 예:
  • Thread.sleep()와 같은 메서드는 네이티브 코드를 통해 구현되어 운영 체제의 스레드 관리 기능을 호출.
  • AtomicInteger의 compareAndSet() 같은 원자적 연산은 하드웨어 명령을 활용한 네이티브 코드로 구현.

멀티스레드 문제 예시 - 은행 계좌 잔액 갱신 문제

class BankAccount {
    private int balance = 100;

    public void withdraw(int amount) {
        if (balance >= amount) { // 조건 검사
            balance -= amount;  // 잔액 갱신
        }
    }
}

의도된 동작

1. 스레드 A가 50을 출금.
2. 스레드 B가 50을 출금.
3. 결과적으로 잔액은 0이 되어야 함.

문제 상황

• 스레드 A와 스레드 B가 동시에 withdraw(50) 메서드를 호출하면, 잔액 조건 검사와 갱신 작업이 중첩될 수 있음.
• 이로 인해 두 스레드가 잔액 조건을 동시에 검사한 후, 동시에 출금을 진행.
• 결과적으로, 잔액이 50으로 잘못 계산됨.

**정상적인 단일 스레드 실행**

-------
스레드 A 실행:
[검사] 잔액: 100 >= 50  -> True
[갱신] 잔액 -= 50       -> 잔액: 50

**멀티스레드에서의 충돌**
스레드 A 실행:                          스레드 B 실행:
[검사] 잔액: 100 >= 50  -> True        [검사] 잔액: 100 >= 50  -> True
[갱신] 잔액 -= 50       -> 잔액: 50    [갱신] 잔액 -= 50       -> 잔액: 50

결과: 두 스레드가 모두 출금을 완료했지만, 최종 잔액은 50으로 계산됨 (잘못된 결과).

멀티스레드 환경의 위험 요소

1. Race Condition (경쟁 상태)
   • 여러 스레드가 동시에 동일한 자원에 접근하고 이를 수정할 때, 실행 순서에 따라 결과가 달라질 수 있음.
   • 예: 위의 은행 계좌 예제에서 스레드 간 동기화가 없을 경우 발생.
2. Deadlock (교착 상태)
   • 두 스레드가 서로 자원을 기다리며 무한히 대기하는 상황.
   • 예: 스레드 A가 자원 1을 점유하고 자원 2를 기다리는 동안, 스레드 B는 자원 2를 점유하고 자원 1을 기다림.
3. Data Corruption (데이터 손상)
   • 여러 스레드가 동일한 메모리 위치를 수정하면, 결과값이 예기치 않게 손상될 수 있음.
   • 예: 공유 데이터 구조의 상태가 불완전하거나 잘못된 상태로 유지됨.
4. Thread Interleaving (스레드 중첩 실행)
   • 스레드가 실행 중에 문맥 교환(Context Switching)으로 인해 실행 흐름이 중첩됨.
   • 예: 스레드 A와 B가 교차 실행되며 연산이 중간 상태에서 중단됨.

해결 방법

1. 동기화 사용

• synchronized 키워드: 공유 자원에 한 번에 하나의 스레드만 접근하도록 보장.
• ReentrantLock: 더 세밀한 락 제어 가능.

public synchronized void withdraw(int amount) {
    if (balance >= amount) {
        balance -= amount;
    }
}

2. 원자적 연산 사용

• Java의 AtomicInteger 또는 AtomicLong과 같은 클래스 사용.
• 내부적으로 CAS(Compare-And-Swap)를 활용하여 동기화 문제를 해결.

import java.util.concurrent.atomic.AtomicInteger;

class BankAccount {
    private AtomicInteger balance = new AtomicInteger(100);

    public void withdraw(int amount) {
        balance.addAndGet(-amount); // 원자적 연산
    }
}

3. 동시성 제어 도구

• CountDownLatch, Semaphore, CyclicBarrier 등 사용.
• 특정 조건에서 스레드의 실행을 제어하여 동기화 문제를 방지.