뒤집어진 사과집

접근

n의 최대값이 500이기 때문에 그냥 n x n인 2차원 배열을 만들어도 됐겠지만, 전부 사용한다면 모를까 반은 비어있을 예정이기 때문에 메모리가 낭비되는게 거슬렸다. 그래서 코드는 조금 복잡해지더라도 n의 길이를 가지는 1차원 배열 2개를 만들어서 윗줄부터 하나씩 내려갈 때, 현재 계산하는 줄(cur)과 윗줄까지 계산한 결과(prev)를 담도록 했다. 이러면 낭비되는 메모리도 줄일 수 있을 뿐더러, 차지하는 공간이 n^2에서 n*2로 줄어들게 되기 때문에 n이 커질수록 더 이득일 것이라 생각했다. 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] prev = new int[n+1];
        int[] cur = new int[n+1];
        int answer = 0;

        for(int i = 0;i < n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++) {
                int val = Integer.parseInt(st.nextToken());

                if(j == 0) cur[j] = prev[j] + val;
                else cur[j] = Math.max(prev[j-1] + val, prev[j] + val);

                answer = Math.max(answer, cur[j]);
            }
            int[] tmp = prev;
            prev = cur;
            cur = tmp;
        }
        System.out.println(answer);
    }
}

접근

dp[i]에는 i번째 자리까지 고려했을 때 가장 컸던 연속합을 저장하도록 한다. 따라서 연속적으로 수를 더해 나가다가 그 합이 되려 작아지는 경우에는 값을 재설정해줬다. 질문 게시판은 반례를 올려주시는 분들이 많아서 애용하는 편인데, 1912번 문제에 해당하는 반례를 모아서 작성해준 분이 계셔서 링크를 남긴다.
https://www.acmicpc.net/board/view/44227 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n];
        int[] dp = new int[n];

        for(int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int sum = dp[0] = arr[0];

        for (int i = 1; i < n; i++) {
            sum = Math.max(sum + arr[i], arr[i]);
            dp[i] = Math.max(dp[i-1], sum);
        }

        System.out.println(dp[n-1]);
    }
}

접근

이번주 스터디에서는 알고리즘을 정한 후 문제를 골랐기 때문에 DP로 접근해야 한다는 사실을 알고 풀었지만, 모르고 문제를 푼다면 내 나름의 판단 근거는 실행 시간이다. 뭔가 복잡해보이는데 제한 시간이 1초 이내로 짧다면 DP일 가능성이 높다고 생각한다. 

각설하고 문제로 돌아가면, 사용되는 숫자가 1~3로 3가지밖에 없어서 10, 50, 100원으로 나누던 동전 문제와 유사하다는 느낌을 받았다. n의 최댓값이 10으로 매우 작으므로 숫자 2부터 하나씩 계산하면 될 것 같다. 사용 가능한 최대 숫자가 3이기 때문에 3번마다 규칙이 보이길 바라면서 개수를 세어봤다. 그런데 나는 합을 나타낼 때 수를 '1개' 이상 사용해야 한다는 조건을 제대로 읽지 못해서 시간을 많이 낭비했다..ㅎㅎ 무조건 합(+)이 들어가야 한다고 생각했는데 역시 문제를 잘 읽자.. 

n = 1) 1가지

1

n = 2) 2가지

2 / 1+1

n = 3) 4가지

3 / 2+1, 1+2

n = 4) 7가지

3+1, 1+3, 2+2 / 2+1+1, 1+2+1, 1+1+2 / 1+1+1+1

숫자 n에 따른 경우의 수를 저장하는 배열을 dp[]라고 할 때, 위 규칙을 보면 dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 식을 유추해볼 수 있다. 이 방법대로 코드를 구현하자. 참고로 dp[5] = 13, dp[6] = 24... 으로 성립하는걸 알 수 있다. 이렇게 되는 이유는,

4 = 1 + 3 (3을 만들 수 있는 경우의 수)

   = 2 + 2 (2를 만들 수 있는 경우의 수)

   = 3 + 1 (1을 만들 수 있는 경우의 수)

가 되기 때문

코드

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

public class Main {
    static int MAX_VALUE = 11;

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

        // n이 작으므로 매번 동일한 연산을 하지 않도록 미리 수행했음
        int[] dp = new int[MAX_VALUE];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for(int i = 4;i < MAX_VALUE;i++)
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];

        // 테스트케이스별 결과 출력
        int tc = Integer.parseInt(br.readLine());
        for(int t = 0; t < tc; t++){
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n]).append("\n");
        }

        System.out.println(sb);
    }
}

개요

정의

• 애플리케이션이 시작될 때, 최초 한 번만 메모리를 할당하고(static) 그 메모리에 인스턴스를 만들어 사용하는 디자인 패턴
• 즉, 객체의 인스턴스가 오직 ‘하나’만 생성됨
• 인스턴스가 필요할 때 똑같은 것을 새로 만들지 않고 기존의 인스턴스를 활용하는 것
• 생성자가 여러 번 호출되어도 실제로 생성되는 객체는 하나임
  • 자바에서는 생성자를 private로 선언해 다른 곳에서 생성하지 못하도록 방지

장점

• 메모리 낭비 방지
  • 객체는 생성할 때마다 새로운 메모리 영역을 할당받아야 함
  • 한 번의 new를 통해 객체를 생성하기 때문에 고정된 메모리 영역을 사용
• 이미 생성된 인스턴스를 활용하여 객체 로딩 시간이 줄어들며 속도 성능 향상
• 전역으로 사용되기 때문에 다른 인스턴스들이 접근 가능하여 클래스 간 데이터 공유가 용이
• 도메인 관점에서 인스턴스가 절대적으로 한 개만 존재하는 것을 보증하고 싶은 경우에 사용

활용

• 주로 공통된 객체를 여러 개 생성해서 사용해야 하는 상황에 많이 사용됨
• DB의 커넥션 풀, 스레드풀, 캐시, 로그 기록 객체 등
• 안드로이드 앱에서도 각 Activity들이나 클래스마다 주요 클래스들이 하나하나 전달하는게 번거롭기 때문에 싱글톤 클래스를 만들어 어디서든 접근하도록 설계함

단점

• 테스트가 어려움
  • 정적 필드는 한번 할당되면 프로그램이 종료되기 전까지 계속 살아있게 됨
  • 각 테스트는 독립적(다른 테스트에 영향을 미치지 않아야) 하는데, 한번 싱글톤 객체가 만들어지면 자원이 공유됨
    → 인스턴스의 상태를 매번 초기화해야 함
  • 일반적으로 인터페이스가 아닌 클래스를 통해 구현되는 싱글톤은 mock으로 대체할 수 없으므로 단위 테스트가 까다로워짐
  • 이를 해결하기 위해 주로 의존관계 주입(DI)를 사용하며, 이 경우 보통 DI 프레임워크가 싱글톤 객체의 생성을 제어함
• “개방-폐쇄 원칙(OCP)” 위배 가능성
  • 객체 지향 설계 원칙(SOLID) 중 기존의 코드를 변경하지 않으면서, 기능을 추가할 수 있도록 설계되어야 한다는 원칙
  • 싱글톤 인스턴스를 여러곳에서 많이 공유할 경우 다른 클래스들 간의 의존도가 높아지면서 객체 간의 독립성을 지향하는 원칙에 어긋남 → 유지보수가 어려워짐
• 멀티 스레드 동시성 문제
  • 동기화가 제대로 이루어지지 않으면 경쟁 상태(race condition)가 될 수 있음
  • 인스턴스가 2개가 생성될 수도 있는 것

⇒ 유연성이 많이 떨어지는 패턴이라고 할 수 있음

종합

• 싱글톤 패턴은 안티 패턴으로 불릴 만큼 단독으로 사용한다면 객체 지향에 위반되는 사례가 많음
• 애플리케이션의 한 곳에서만 사용될 모듈을 싱글톤으로 구현할 경우, 해당 인스턴스가 제대로 gc되지 않는다면 끝까지 메모리를 차지하고 있기 때문에 적절한 경우에 사용할 필요가 있음(남용x)
• 스프링 컨테이너같은 프레임워크의 의존성 주입(DI)를 통해 모듈 간의 결합을 느슨하게 만들 수 있음

예제

아래 방법들은 모두 Lazy Initialization에 해당한다. 모두 처음부터 싱글톤 변수에 초기화를 시키지 않고, getInstance() 메소드를 통해 필요로 할 때(게으르게) 인스턴스를 생성하고 있다.

일반적인 방식

• 단일 스레드에서는 전혀 문제가 없는 방식

public class Car {
	// 메모리에 static으로 최초에 한번만 생성
	private static Car instance;
	
	private Car() {}

	// 외부에서 멤버로 선언된 instance를 가져올 수 있는 메서드
	public static Car getInstance(){
		if(instance == null){
			instance = new Car();
		}
		return instance;
	}
}

/************************************/

public class Test {
	// 인스턴스 사용 요청
	Car car = Car.getInstance();
}

동시성 문제 해결 방식

1. 지연 초기화(Lazy Initialization) + synchronized

• synchronized 동기화를 활용해 스레드를 안전하게 만듦
• 하지만 synchronized는 큰 성능저하를 발생시키므로 권장하지 않는 방법

public class Car {
	private static Car instance;
	
	private Car(){}

	public static synchronized Car getInstance(){
		if(instance == null){
			instance = new Car();
		}
		return instance;
	}
}

2. 더블 체크 락킹(Double-checked Locking)

• 조건문으로 인스턴스의 존재 여부를 확인한 이후 synchronized를 통해 동기화를 시켜 인스턴스를 생성
• 스레드를 안전하게 만들면서, 처음 생성 이후에는 synchronized를 실행하지 않기 때문에 1번 방법보다 성능이 좋음
• 프로그램 구조가 그만큼 복잡해지고 비용 문제가 발생

public class Car {
	private static volatile Car instance;

	private Car(){}

	public static Car getInstance(){
		if(instance == null) {
			synchronized (Car.class){
				if(instance == null){
					instance = new Car();
				}
			}
		}

		return instance;
	}
}

• volatile을 사용하는 이유
  • 컴파일러가 최적화라는 명목으로 연산의 순서를 변경(reordering)할 수 있기 때문
  • A 스레드에서 4번을 실행하여 객체를 위한 메모리 공간을 할당하고 참조를 instance에 저장한 후 싱글톤 객체의 생성자에서 내부 상태 초기화가 이루어지고 있다고 해보자. 이때B 스레드에서 1번을 실행할 경우 null이 아님을 확인하고 초기화 중인 객체 참조를 그대로 반환할 수도 있다. 따라서 외부에서 올바르게 초기화되지 않은 객체의 상태를 관찰할 수 있다는 것이다.
  • "객체의 초기화가 완전히 끝난 다음에 그 객체에 대한 참조가 instance에 저장되는 것이 아니라는 점"에 유의해야 한다. 실제로는 동기화 블록 내부에서 컴파일러로 인해 재배열이 일어나므로 다르게 동작할 수도 있다(단일 스레드에서는 개발자 입장에서 결과가 동일하다). volatile 키워드를 사용하면 필드에 값을 쓸 때 위와같은 재배열이 일어나지 않도록 컴파일러에게 지시하는 것이 가능하다. 

if (instance == null) { // (1)
	synchronized (Singleton.class) { // (2)
		if (instance == null) { // (3)
			instance = new Singleton(); // (4)
		} // (5)
	} // (6)
} // (7)
return instance; // (8)

3. 요청 시 초기화 홀더(Initialization-on-demand holder)

• 내부에 Holder 클래스를 두어 JVM의 클래스 로더 매커니즘과 클래스가 로드되는 시점을 이용
• JVM의 클래스 초기화 과정에서 보장되는 원자적 특성을 이용
• final을 사용해서 다시 값이 할당되지 않도록 만듦
• 실제로 가장 많이 사용되는 일반적인 방식이라고 함
  

public class Car {
	private Car() {}
 
	private static class Holder {
		public static final Car INSTANCE = new Car();
	}
 
	public static Car getInstance() {
		// Class가 로딩되며 초기화가 진행. 이 시점에서 thread-safe 보장
		return Holder.INSTANCE;
	}
}

• Holder.INSTANCE 부분에서 thread-safe가 되는 이유 
  • 클래스나 인터페이스 타입 T는 아래 작업들이 처음 일어나기 직전에 초기화됨
    1. T가 클래스이고 T의 인스턴스가 생성될 때
    2. T에 선언된 정적 메서드가 호출될 때
    3. T에 선언된 정적 필드가 할당될 때
    4. T에 선언된 정적 필드가 사용될 때(상수 변수가 아닌 필드)
  • Holder 클래스에 선언된 정적 필드인 INSTANCE가 사용될 때 Holder 클래스의 초기화가 일어남
  • 위 예시에서는 런타임에 getInstance()를 호출하여 Holder.INSTANCE 를 사용하기 전에, 클래스로더를 통해 Holder 클래스의 초기화가 일어나게 됨
  • 그와 동시에 Holder 클래스의 초기화 단계에서 정적 필드 INSTANCE의 초기화는 단 한 번만 일어남

4. 열거형(Enum)

• 열거형에 열거형 상수를 통해 정의된 인스턴스 이외의 인스턴스는 존재하지 않음
  (열거형을 명시적으로 인스턴스화하려고 시도하면 컴파일 에러가 발생)
• 직렬화(Serialization)가 가능
• Reflection API를 통해 인스턴스를 만드려는 시도를 무력화 가능
• 열거형은 다른 클래스를 상속받을 수 없으므로, 클래스 상속이 필요하다면 사용 불가능

public enum Singleton {
	INSTANCE;
 
	public static Singleton getInstance() {
		return INSTANCE;
	}
}

final class Singleton extends Enum<Singleton> {
	public static final INSTANCE = new Singleton();
}

References

• 싱글톤(Singleton) 패턴이란?
• [디자인 패턴] 싱글톤 패턴(Singleton Pattern) 정리 및 예제
• 싱글톤 패턴(Singleton pattern) | ‍ Tech Interview - Gyoogle
• 디자인 패턴. 싱글턴 패턴(Singleton pattern)
• 싱글톤 패턴(Singleton pattern)을 쓰는 이유와 문제점
• 싱글톤 패턴(Singleton Pattern) : 멀티 스레드 환경에서의 문제점

새해를 맞아서 기술 블로그를 시작해보려 하는데 

네이버 블로그조차도 운영해본 적이 없다보니 아직 많이 어색하다..

원래는 개인 노션에만 모든걸 정리했었는데 프로젝트나 공부 내용이 다 섞여서 관리가 좀 힘들더라

그래서 나도 찾기 편하고 남들한테 조금이라도 도움이 될 수 있을까 싶어서 블로그에 도전..!