String클래스의 + 연산

05 Mar 2020 | Java

String 클래스의 + 연산

백준 15651번 문제를 풀다가 코드 한줄로 복잡도 차이가 크게 나서 (특히 공간복잡도) 찾아본 내용을 정리한다.

사진을 보면 거의 공간복잡도가 2배 가까이 차이가 나는 것을 볼 수 있다.

그 이유를 아래 사진을 보며 알아보자.

###사진1

###사진2

차이점

위 사진을 보면 차이가 나는 것은 단 한 줄이다.

// arr[i]는 String 타입이다
  
// 사진 1
sb.append(arr[i] + " "); 
// 사진 2
sb.append(arr[i]);
sb.append(" ");

String은 immutable한 객체이므로 + 연산을 할 경우 컴파일러가 런타임에 StringBuilder 또는 StringBuffer로 append 한 후 새로운 String 객체를 반환한다. 이로 인해 + 연산을 할 때마다 메모리에 새로운 String 객체가 생성되어 더 많은 공간복잡도를 차지하게 되는 것이다.

ref. doc

Comment Read more

카잉 달력

04 Mar 2020 | Algorithm

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

public class BOJ_6064 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            String[] line = br.readLine().split("\\s");
            int m = Integer.parseInt(line[0]);
            int n = Integer.parseInt(line[1]);
            int x = Integer.parseInt(line[2]);
            int y = Integer.parseInt(line[3]);

            int tempX = x;
            int tempY = x;
            boolean ok = false;

            while (tempY <= m * n) {

                // 1. y != n
                // 2. y == n
                if ((tempY % n) == y || (tempY % n) == 0 && y % n == 0) {
                    System.out.println(tempY);
                    ok = true;
                    break;
                }


                tempY += m;
            }
            if (!ok)
                System.out.println(-1);
        }
    }
}

Comment Read more

프로세스 동기화(2)- 세마포어

27 Feb 2020 | OS

세마포어

세마포어란?

정수 값을 가지는 변수로서, 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 사용된다
P와 V 명령에 의해서만 접근가능하다
추상자료형으로서, P와 V 명령을 수행할 때 원자적으로 수행된다고 가정하고 사용한다

구현 방법

busy waitng
- 비효율적, 어느 프로세스가 먼저 임계 영역에 들어갈지 결정할 수 없다

P(S) {
     while S <=0; // 아무것도 하지 않음 (반복문)
     S--;
 }

 V(S) {
     S++;
 }

block/wake-up
- busy waiting을 개선한 방법

 P(S) {
     S--;
     if S < 0
         // 이 프로세스를 재움 큐에 추가 (잠 듦)
 }

 V(S) {
     S++;
     if S <= 0
         // 재움 큐로부터 프로세스를 제거 (깨어남)
 }

세마포어의 종류

Counting Semaphore
- 초기값은 가능한 자원 수로 정해진다
- 주로 resource counting에 사용한다
binary Semaphore
- 세마포어 값으로 0 또는 1을 가진다
- 주로 mutual exclusion (lock/unlock)에 사용한다

주의점

dead-lock 또는 starvation 발생 할 가능성이 존재하므로 사용시 유의해야한다

ref. KOCW

ref. wiki

Comment Read more

프로세스 동기화(1)

27 Feb 2020 | OS

Process Synchronization

공유 데이터의 동시 접근(nonatomic)은 데이터의 불일치 문제를 발생 시킬 수 있다 -> Race Condition
Race Condition을 막기 위해서는 concurrent process는 동기화 되어야 한다

Critical Section

공유 데이터에 접근하는 코드
프로세스 1의 ‘X=X+1’, 프로세스 2의 ‘X=X-1’

Critical Section Problem

하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어가 수 없어야 한다

Critical Section Solution

Mutial Exclusion (상호 배제)

프로세스 P(i)가 critical section을 수행 중이면 다른 모든 프로세스들은 critical section에 들어가서는 안된다

Progress (진행)

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다

Bounded Waiting (유한대기)

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다

turn variable 을 사용한다
- 상호배제조건은 만족하지만 진행조건은 만족하지 못한다
- 과잉양보 - 반드시 한번씩 교대로 들어가야한다.
- 특정 프로세스가 더 빈번히 critical section에 들어가야 한다면?
  특정 프로세스는 critical section에 접근하지 않는다면?

interest(flag) variable을 사용한다
- critical section에 들어가고 싶은 프로세스는 flag variable로 의사표현을 한다
- 상호배제조건은 만족하지만 진행조건은 만족하지 못한다
- 데드락 발생가능하다 ( 둘다 1행까지 수행 후 끊임 없이 양보한다 )

Peterson’s Algorithm을 사용한다

turn variable, flag variable 알고리즘을 합친 것
모든 조건을 충족하지만 busy waiting이 발생할 수 있다

Test & Set Lock을 사용한다

하드웨어적으로 Test&Set을 Atomic하게 수행하도록 지원한다
Test-and-Set(lock)이 호출되면 Atomic하게 lock의 값(0 또는 1)을 읽고 1로 set 해준다
lock의 초기값은 0이므로 처음 호출한 프로세스가 진입하고 작업이 완료되면 lock=0으로 set 해줘서 다른 프로세스가 critical section에 접근할 수 있도록 만들어준다