가상메모리 요구페이징(demand paging)

지금까지의 메모라 관리 기법 방식은 프로세스 전체가 메모리 내에 올라와야 한다는 것을 전제로 하고 있다.

프로세스 전체가 메모리 내에 올라오지 않더라고 실행히 가능하도록 하는 기법을 가상메모리라고 한다.

가상메모리는 물리 메로리로부터 사용자 관점의 논리 메모리를 분리시켜 주 메모리를 균인한 크기의 저장 공간으로 구성된 엄청나게 큰 배열로 추상화 시켜준다.

따라서 작은 메모리를 가지고도 큰 가상 주소 공간을 제공한다.

 

  • 장점

    • 사용자 프로그램이 물리 메모리보다 커져도 된다. 즉, 메모리 크기의 제약으로부터 자유로워진다.
    • 각 사용자 프로그램이 더 작은 메모리를 차지하므로 더 많은 프로그램을 동시에 수행할 수 있다. 이에 따라 응답시간은 늘어나지 않으면서 CPU 이용률과 처리율이 높아진다.
    • 프로그램을 메모리에 올리고 스왑하는데 필요한 입/출력 횟수가 줄어든다. 따라서 프로그램들이 보다 빨리 실행된다.
    • 가상메모리 파일의 공유를 쉽게 해주고 공유 메모리 구현을 가능하게 한다.
    • 프로세스 생성을 효율적으로 처리할 수 있는 메커니즘도 제공한다.

  • 단점

    • 구현이 어렵고, 잘못 사용시 성능이 현저히 저하될 수 있다.

요구페이징

요구페이징은 필요한 프로그램만 메모리에 적재하는 방법으로 가상 메모리 시스템에서 많이 사용된다. 요구 페이징을 사용하는 가상메모리에서는 페이지들이 실행 과정에서 실제로 필요해질 때 적재 된다.

 

요구페이징은 일부 스와핑 기법과 유사하다. 프로세스를 실행하고 싶으면 메모리로 읽어 들이며 이때 전체 프로세스를 읽어오지 않고 lazy swapper를 사용한다. lazy swapper는 그 페이지가 필요하지 않는 한 메모리에 적재 되지 않는다.

 

스와퍼는 전체 프로세스를 관리하지만 페이저(pager)는 프로세스 내의 개별 페이지들을 관리한다. 요구 페이징과 관련해서는 스와퍼보다 페이저가 더욱 가깝다.

 

swap in 시 페이저는 프로세스가 다시 swap out되기 전에 실제로 사용 될 페이지들이 어떤 것인지 추측한다. 페이저는 프로세스 전체를 스왑인 하는 대신에 실제 피룡한 페이지들만 메모리로 읽어온다. 사용되지 않을 페이지를 메모리로 가져오지 않음으로써 시간 낭비와 메모리 공간 낭비를 줄일 수 있다.

 

페이저는 어느 페이지가 디스크에만 있고 어느 페이지가 메모리에 올라와 있는지 구별할 수 있어야 한다. 이대 유효/무효 비트 기법을 사용하여 비트가 유효하면 메모리에 있는 것을 의미하고 유효하지 않으면 메모리에 없거나(디스크에 있거나) 해당 페이지가 유효하지 않다는 것이다.

 

프로세스가 메모리에 없는 페이지를 접근하려 할 때 페이지 부재 트랩(page-fault-trap)을 발생시킨다. 페이징 하드웨어는 페이지 테이블을 이용한 주소 변환 과정에 무효 비트를 발견하고 운영체제에 트랩을 건다.

 

 

페이지 부재를 처리하는 과정

  1. 프로세스에 대한 내부테이블을 검사해서 그 메모리 참조가 유효/무효 인지 알아 낸다.
  2. 무효한 페이지에 대한 참조라면 프로세스는 중단된다. 유효한 참조인 경우 메모리에 없으면 디스크로부터 가져와야 한다.
  3. 빈 공간, 자유 프레임(free frame)을 찾는다.
  4. 디스크에 새로이 할당된 프레임으로 해당 페이지를 읽어 들이도록 요청
  5. 디스크 읽기가 끝나면 이 페이지가 메모리에 있다는 것을 알리기 위해 페이지 테이블을 갱신하며 프로세스가 유지되고 있는 내부테이블을 수정한다.
  6. 트랩에 의해 중단되었던 명령을 다시 수행하며 프로세스는 그 페이지가 항상 메모리에 있엇던 것처럼 간주하여 해당 페이지를 접근할 수 있다.

페이지가 적재되고 나면 프로세스는 수행을 계속 하는데 프로세스가 사용하는 모든 페이지가 메모리에 올라올 때 까지 필요할 때마다 페이지 부재가 발생 한다. 일단 필요한 모든 페이지가 적재되고 나면 더 이상 부재 오류가 발생하지 않는데 이것이 순수 요구 페이징(pure deman paging)이다.

 

모든 프로그램은 참조의 지역성(locality of reference)이라는 성질이 있어서 프로그램의 어느 한 특정 작은 부분만 한 동안 집중적으로 참조하는데 이러한 성질 때문에 요구 페이징은 만족할 만한 성능을 보인다.

locality of reference 참조 지역성

동일한 값 또는 해당 값에 관계뗀 스토리지 위치가 자주 액세스 되는 특성.
참조지역성의 3가지 기본형 : 시간, 공간, 순차 지역성

1) 공간(spatial) 지역성 : 특성 클러스터들의 기억 장소들에 대해 참조가 집중적으로 이루어지는 경향으로, 참조된 메모리의 근처의 메모리를 참조.

2) 시간(temporal) 지역성 : 최근 사용되었던 기옥 장소들이 집중적으로 액세스 되는 경향으로, 참조했던 메모리는 빠른 시간에 다시 참조될 확률이 높다.

3) 순차(sequential) 지역성 : 데이터가 순차적ㅇ로 액세스 되는 경향. 프로그램 내의 명령어가 순차적으로 구성되어있다는 것이 대표적인 경우.

 

요구 페이징의 필수적인 요구 사항은 페이지 부재 오류 처리 후에 명령 처리를 다시 시작할 수 있어야 한다.

만약 페이지 부재가 명령 인출(instruction fetch)시에 발생 했다면 명령을 메모리로 읽어 온 후 다시 수행을 시도하면 된다.

 

요구 페이징은 컴퓨터 시스템의 성능에 중요한 영향을 미친다. 페이지 부재가 발생하지 않는 한 실질 접근 시간은 메모리 접근 시간과 같다. 그러나 페이지 부재가 발생하면 디스크로부터 관련되는 페이지를 읽어 온 뒤 필요한 워드를 접근해야 한다.

 

요구 페이징의 또 다른 특성은 스왑 공간의 관리이다. 스왑 공간에서의 디스크 입/출력은 일반적으로 파일 시스템에서의 입/출력보다 빠른데 그 이유는 스왑 공간은 파일 시스템보다 더 큰 블록을 사용하기 때문이고 또 스왑 공간과 입/출력을 할 때는 파일 찾기(lookup)나 간접 할당 방법 등은 사용하지 않기 때문이다.

 

저작자표시

'Computer Science > Operating System' 카테고리의 다른 글

프로세스 동기화 (Process Synchronization)  (1) 2019.04.17
CPU 스케줄러  (0) 2019.03.03
스케줄러 Scheduler  (0) 2019.02.23
프로세스, 쓰레드, 멀티프로세싱, 멀티쓰레드  (0) 2019.02.15

Operating System

 

프로세스 동기화

동기화(Synchronization)

  • 동기화의 필요성

은행의 1000원의 잔고가 남아있다고 가정하자.

내가 500원을 찾는 순간 동시에 어머니가 500원을 송금해 오셨다면? 우리는 1000원의 잔고를 예상한다.

Process A : incoming
Register1 = Balance
Register1 = Register1 + 500
Balance = Register1

Process B : outgoing
Register2 = Balance
Register2 = Register2 - 500
Balance = Register2

T0: Process A  Register1 = Balance										R1 = 1000
T1: Process A  Register1 = Register1 + 500						R1 = 1500
T2: Process B  Register2 = Balance										R2 = 1000
T3: Process B  Register2 = Register2 - 500						R2 = 500
T4: Process A  Balance = Register1										B = 1500
T5: Process B  Balance = Register2										B = 500

어떠한 데이터에 대해 동시 작업이 일어났을 경우 처리순서에 상관없이 원하는 결과값을 얻기 위해 동기화가 필요하다.

동기화의 목적은 Data Consistency(데이터 일관성)을 보장해주는 것이다.

 

유저 동기화는 critical section

커널 동기화는 mutex / semaphore

 

Critical Section

멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역.

임계구역은 시간이 지나면 종료되며, 어떤 프로세스가 임계구역에 접근하기 위해서는 지정된 시간만큼 대기해야 한다.

이때 쓰레드나 프로세스가 배타적인 사용권을 보장받기 위해 세마포어 같은 동기화 메커니즘이 사용된다.

한 프로세스 내의 쓰레드 사이에서만 동기화가 가능. 유저 객체(커널에서 제공하는 객체가 아니다.)

 

임계구역 문제를 해결하기 위한 3가지 조건

  1. Mutual Exclusion(상호배제) : 임계구역에는 무조건 하나의 프로세스
  2. Progress(진행) : 임계구역이 비었으면 어느 프로세스가 들어갈지 적절히 선택한다
  3. Bounded Waiting(한정 대기) : 기아 상태를 방지하기 위해, 한 번 들어갔다 나온 프로세스는 다음에 들어갈때 제한을 준다.

 

동기화 방법

 

상호배제 (MUUual EXclusion)  뮤텍스.

공유데이터가 하나의 프로세스에 의해 독점적으로 사용되는 원칙

entry section
		
		critical section
		
exit section

프로세스는 critical section에 들어가기 전에 entry section 단계에서 출입을 허가받아야한다.

critical section 오직 하나의 프로세스만 존재하도록 한다.

동시프로그래밍 환경(멀티 프로세스 및 멀티 쓰레드 같은)에서 공유 불가능한 자원 처리 (critical section과 구분)

DB의 프로그램에서는 자동적인 부가기능으로 지원되지만, OS의 경우는 사용자의 요구에 따라 지원된다.

장점 혼란이없고 간단하다.

단점 read/write 두 처리 모두 대기한다.

write는 대기하는게 맞지만, read는 데이터를 변화시키지 않으므로 상관없다.

하지만 상호배제는 read도 대기해야한다.

→ 해결법

kernel자체가 하나의 커더란 critical section의 역할을 하는 것.

[Spin lock]

0 : critical section가 비어있다. 사용 가능 .

1 : critical section안에 다른 프로세스가 들어와 있는것.

Spin lock이 1일 경우 다음 수행을 기다리는 프로세스는 lock을 계속 돌게된다.

exit section에 의해 프로세스가 처리되었는지를 인식해 spin lock을 조정한다.

장점 : "조금만 기다리면 바로 쓸 수 있는데 굳치 context switching을 해서 부하를 줄 필요가 있나?"

스핀락을 잘 사용하면 context switching을 줄여 효율을 높일 수 있다.

 

[Sleep lock] — 세마포어

lock이 1일 경우 기다리던 프로세스는 sleep을 하게 되는 것.

critical section내에 프로세스의 작업이 끝나게 되면 sleep중인 프로세스를 깨워 처리하게 된다.

 

—두개의 차이

프로세스가 exit section에 도착했을때.

spin lock은 lock으로 접근해 1로 바꾼다 : waiting process가 항시 대기하며 값이 바뀌기를 기다리고 있으므로 lock만 바꿔주면 된다.

sleep lock은 sleeping process를 깨운다.

 

But, 동시에 2개 이상의 프로세스가 접근하면 상호배제 불가.

A와 B가 동시에 접근해서 lock 이 0인걸 확인했다.

A는 0을 1로 바꿨고, B는 read만 수행하고 context switching이 발생했다.

B는 다음 작업이 수행하게 될때 이미 read 했기때문에, 다시 확인하지 않고(A가 1로 바꿔놨는데 0인줄 알고) 데이터에 접근한다.

해결방법 : read/write를 하나의 명령어로 만들어 놓는다.

 

피터슨의 알고리즘

상호배제를 위한 병렬프로그래밍 알고리즘. 

do{
  flag[me] = true; //임계 구역 사용을 원함 
  turn =! me; //me 프로세스의 차례가 아님 
  while(flag[me]&&turn =! me); //me 프로세스가 사용을 원하지만, 턴은 아니면 대기  
  **critical section**
  flag[me]=false; //임계구역 사용이 끝나면 폴스로 바꿔준다. 
  **remainder section**
} while(true);

그러나 프로세스가 많이 몰리면 계속 while문을 대기해야 하는데 이를 busy waiting(바쁜 대기)상태라고 부른다.

 

세마포어(Semaphore)

critical section, mutex는 동기화에 있어서 동시에 하나의 쓰레드만 실행되게 하지만, 세마포어는 지정된 수만큼의 쓰레드가 동시에 실행되도록 동기화하는 것이 가능.

  • 임계구역에 들어가기 전 스위치를 사용중으로 놓고 들어간다.

  • 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠때까지 기다린다.

  • 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.

  • 임계구역이 잠겼는지 직접 점검하건, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

  • 세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up신호를 받으면 큐에서 나와 임계구여에 진입.

  • 함수 P는 임계구역 들어가기전에 수행 / V는 나올때 수행

  • 2개의 공유자원을 가지고 3개의 프로세스가 작업할 때 (Rs=2;)

    1. 프로세스 P1은 RS 값을 1 감소시키고 임계구역에 진입한다.
    2. 프로세스 P2도 RS 값을 1 감소시키고 임계구역에 진입한다.
    1. P3은 RS가 0이므로 대기.
    1. P1이 작업을 마치고 V()를 실행하면 RS값은 1이 되고 wake_up신호가 프로세스 P3에게 전달
    1. P3 임계구역 진입

  • 문제점

    세마포어를 잘못 사용하면 임계구역을 보호할 수 없다.

    (1) P() - P() : wake_up신호가 발생하지 않아 무한대기에 빠진다.

    (2) V() - P() : 상호배제가 보장되지 않는 경우

     

MUTEX vs Semaphore

세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다. 뮤텍스는 상태가 0,1 뿐인 binary 세마포어

세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 진다.

뮤텍스는 1개만 동기화가 되지만 세마포어는 하나 이상의 동기화를 할 수 있다.

 

ex ) 변기가 3개가 있는 화장실에서

각각의 변기 앞에 3줄로 줄을 선다 —> 뮤텍스

화장실 문 앞에 한줄로 줄을 선다 —> 세마포어

 

데드락(DeadLock: 교착상태)

프로세스들이 서로 작업을 진행하지 못하고 영원히 대기상태로 빠지는 현상.

프로세스 사이에 할당된 자원의 충돌로 인하여 발생하게 된다.

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태.

cf) starvation - OS가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

교착상태 - 자연적으로 일어나는 문제

 

데드락은 한 시스템 내에서 다음의 네가지 조건이 동시에 성립할 때 발생한다.

아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 교착 상태를 해결할 수 있다.

  • 상호배제 (Mutual exclusion)

    한 번에 한 프로세스만 사용 가능

  • 점유대기(Hold and wait)

    최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

  • 비선점(No preemption)

    빼앗을 수 없다.

  • 순환대기(Circular wait)

    프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

 

데드락 처리

  1. 예방

    교착상태 발생조건 중 하나를 제거하면서 해결 -> 자원 낭비가 심하다

  2. 회피

    은행원 알고리즘

    • 프로세스가 자원을 요구할 때 , 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피.
    • 안정상태면 자원 할당, 아니면 다른 프로세스들이 자언을 해지할때까지 대기.

 

식사하는 철학자 문제

철학자가 스테이크를 먹기 위해 양옆의 포크를 동시에 들어야한다.

해결책

  • n명이 앉을 수 있는 테이블에서 철학자를 n-1명 앉힌다.
  • 한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용
  • 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용

 

 

—> Synchronization을 구현하는 것은 사용자의 필요성에 의해 각자에게 맡겨진 것이다.

어떠한 1명이 실수로 잘못 구현하면 심각한 문제 발생. —> 해결방안 : 모니터

 

모니터

  • 시스템 호출과 같은 개념. 인터페이스만 제공한다
  • 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
  • 모니터는 요청받은 작업을 모니터 큐에 저장한후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.
  • 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고, 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.

 

 

 

 

저작자표시

'Computer Science > Operating System' 카테고리의 다른 글

가상메모리(virtual memory)와 요구페이징(demand paging)  (1) 2019.04.19
CPU 스케줄러  (0) 2019.03.03
스케줄러 Scheduler  (0) 2019.02.23
프로세스, 쓰레드, 멀티프로세싱, 멀티쓰레드  (0) 2019.02.15

문제보기 >> [BOJ] 16235 : 나무재테크



Comment

문제 그대로 구현했다.

우선순위큐를 사용할때 팝하는 과정에서 내 의지와 다르게 팝될 수 있으므로 주의 ..**

우선순위큐 사이즈만큼 팝하고, 다시 애드 할때에는 새로운 큐에 담은 후 옮겨줘야한다

 

 

1
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
//BOJ :: 16235 나무재테크
//2019-04-13
 
public class Main16235_나무재테크 {
    private static int[][] A;
    private static int N,K;
    private static PriorityQueue<pair> trees;
    private static int[][] Y;
    private static int[] dy = {-1,-1,-1,0,0,1,1,1};
    private static int[] dx = {-1,0,1,-1,1,-1,0,1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        A = new int[N + 1][N + 1];
        Y = new int[N + 1][N + 1];
 
        trees = new PriorityQueue<>();
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= N; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
                Arrays.fill(Y[i], 5); // 양분 초기값
            }
        }
 
        for (int i = 0; i < M; i++) {// 나무정보
            st = new StringTokenizer(br.readLine(), " ");
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken()); // 나무 나이
            trees.add(new pair(y, x, z));
        }
        //////// input
 
        treeInvestment();
        
        System.out.println(trees.size());
    }
 
    public static void treeInvestment() {
        ArrayList<pair> die = new ArrayList<>();
        ArrayList<pair> breed = new ArrayList<>();
        for (int year = 0; year < K; year++) {
            // 봄
            int tsize = trees.size();
            PriorityQueue<pair> newpq = new PriorityQueue<>();
            for (int i = 0; i < tsize; i++) {
            
                pair p = trees.poll();
                int py = p.y;
                int px = p.x;
 
                if (Y[py][px] < p.age) {// 양분이 내 나이보다 적으면 죽는다.
                    die.add(new pair(py,px,p.age));
                    continue;
                }
                
                Y[py][px] -= p.age; // 나이만큼 양분 먹기
                newpq.add(new pair(py, px, p.age+1));
                
                if((p.age+1)%5==0) {//나이가 5의 배수면 
                    breed.add(new pair(py,px,p.age+1));
                }
            }
            trees = new PriorityQueue<>(newpq);
 
            // 여름
            for(pair p : die) {
                int py = p.y;
                int px = p.x;
                
                Y[py][px] += p.age/2;
            }
            die.clear();
        
            //가을
            for(pair p : breed) {
                int py = p.y;
                int px=p.x;
                for(int i=0;i<8;i++) {
                    int ny = py+dy[i];
                    int nx = px+dx[i];
                    
                    if(ny<1 || ny>N || nx<1 || nx>N) continue;
                    
                    trees.add(new pair(ny,nx,1));
                }
            }
            breed.clear();
            
            //겨울 
            for(int i=1;i<=N;i++) {
                for(int j=1;j<=N;j++) {
                    Y[i][j] += A[i][j];
                }
            }
        
        }//year term 
    
        return;
 
    }
 
    static class pair implements Comparable<pair> {
        int y;
        int x;
        int age;
        public pair(int y, int x, int age) {
            super();
            this.y = y;
            this.x = x;
            this.age = age;
        }
        @Override
        public int compareTo(pair o) {
            return this.age - o.age;
        }
    }
}
 
 cs
저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 17281 :: ⚾ 야구  (2) 2019.06.05
[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
[BOJ] 1938 통나무 옮기기  (0) 2019.04.05
[SWEA] 2383. 점심식사 시간  (5) 2019.04.04

문제 >> [BOJ] 15685. 드래곤 커브



전형적인 시뮬레이션 문제.


방향의 규칙에 대해서 생각해보며 풀었습니다. 


→  ↑ ← ↓  순서로 드래곤커브가 진행된다는 것을 발견하였고, 순서대로 배열에 넣어 인덱스를 활용해 방향을 전환했습니다.



문제에서 주어진 예시를 보면 ,


시작 방향이 오른쪽 일때,


0세대 

 →  


1세대

 →   ↑ 


2세대

 →   ↑ ← ↑


3세대

 →   ↑ ← ↑ ← ↓ ←  ↑


순서로 진행하고 있고, 이들의 규칙은 다음과 같습니다.


1. 이전 세대의 방향들은 LILF로 팝한다.


2. 방향을 회전해서 진행하여 상단에 push하고 원래의 방향을 하단에 add한다.


예시 )


1세대

 →   ↑ 


nowQ : (상) ↑   → (하) 


LILF로 pop


  ↑   회전 후 ==> ← 


(회전된 방향을 상단에 푸시, 원래방향 하단에 애드)

nextQ : (상)   ←  ↑   (하) 


-----------------------------------


nowQ : (상)  → (하) 


LILF로 pop


   →  회전 후 ==> ↑ 


(회전된 방향을 상단에 푸시, 원래방향 하단에 애드)

nextQ : (상)   ↑  ←  ↑ →  (하) 


-----------------------------------

상단부터 팝하면 2세대가 완성되는 것을 확인할 수 있습니다.


2세대

 →   ↑ ← ↑



설명처럼 상단과 하단 모두에 삽입 하기 위해 덱을 사용해 구현했습니다.




<<java>>

1
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
//BOJ :: 15685 드래곤커브
//2019-04-08
public class Main {
    static int[] dy = { 0, -1, 0, 1 };
    static int[] dx = { 1, 0, -1, 0 }; // 오 상 왼 하
    private static boolean[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 드래곤 커브의 개수
        map = new boolean[103][103];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
 
            bfs(x, y, d, g);
        }
 
        
        int ans =0;
        for(int i=0;i<100;i++) {
            for(int j=0;j<100;j++) {
                if(map[i][j]&&map[i+1][j]&&map[i][j+1]&&map[i+1][j+1]) {
                //    System.out.println(i+" "+j);
                    ans++;
                }
            }
        }
        System.out.println(ans);
 
    }
 
    public static void bfs(int x, int y, int d, int generation) {
        Deque<Integer> now = new LinkedList<>();
 
        Deque<Integer> next = new LinkedList<>();
        map[y][x]=true;
        int ny = y+dy[d];
        int nx = x+dx[d];
        if(ny<0 || ny>100 || nx<0 || ny>100) return;
        map[ny][nx]=true;
        y=ny;
        x=nx;
        now.add(getNextdir(d));
        if(generation==0) return;
        int g = 0;
        while (!now.isEmpty()) {
            g++;
            int size = now.size();
 
                for(int i=0;i<size;i++) {
                    int dir = now.pop();
                    ny = y+dy[dir];
                    nx = x+dx[dir];
                    if(ny<0 || ny>100 || nx<0 || ny>100) break;
                    
                    map[ny][nx] = true;
                    
                    int nd = getNextdir(dir);
                    
                    next.push(nd);
                    next.add(dir);
                    y=ny;
                    x=nx;
            }
 
            if(g==generation) return;
            now.clear();
            now = new LinkedList<>(next);
            next.clear();
//            y=ny;
//            x=nx;
        }
 
    }
    public static int getNextdir(int d) {
        if(d==3) return 0;
        else return d+1;
    }
 
    static class pair {
        int y;
        int x;
        int dir;
 
        public pair(int y, int x, int dir) {
            super();
            this.y = y;
            this.x = x;
            this.dir = dir;
        }
    }
}
 
cs




<<C++>>

1
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <queue>
#include <deque>
using namespace std;
 
int n,generation;
int dx[] = {0,-1,0,1};
int dy[] = {1,0,-1,0};
bool map[101][101] = {false};
deque<int> dq;
 
void dragon_curve(int nx,int ny, int g){
    
    queue<int> q;
    
    if(g == generation) return;
    
    int dq_size = dq.size();
    
    for(int i=0;i<dq_size;i++){
        int a = dq.front();
        dq.pop_front();
        q.push(a);
    }
    
    for(int i=0;i<dq_size;i++){
        int d = q.front();
        q.pop();
        dq.push_back(d);
        
        int nd = (d+1)%4;
        
        nx += dx[nd];
        ny += dy[nd];
        
        if(nx <0 || nx >100 || ny<0 || ny>100) continue;
        
        map[nx][ny]= true;
        dq.push_front(nd);
    }
    
    dragon_curve(nx,ny,g+1);
}
 
void count_box(){
    int cnt = 0;
   
    for(int i=0;i<=99;i++){
        for(int j=1;j<=100;j++){
            if(map[i][j] && map[i][j-1] && map[i+1][j] && map[i+1][j-1])
                cnt++;
        }
    }
    printf("%d\n", cnt);
}
 
int main(){
    scanf("%d",&n);
    
    int x,y,d;
    for(int i=0;i<n;i++){
        scanf("%d %d %d %d",&y,&x,&d,&generation);
        while(!dq.empty()) dq.pop_front();
        
        map[x][y] = true;
        x += dx[d];
        y += dy[d];
        map[x][y] = true;
        dq.push_front(d);
        
        dragon_curve(x,y,0);
    }
    
    count_box();
    
    return 0;
}
 
cs


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 16236 : 아기상어  (0) 2019.06.05
[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 1938 통나무 옮기기  (0) 2019.04.05
[SWEA] 2383. 점심식사 시간  (5) 2019.04.04
[SWEA] 1949. 등산로 조성  (0) 2019.04.01

문제 >> [BOJ] 1938. 통나무 옮기기




저는 기본적으로 통나무의 위치를 가운데 좌표와 모양(세로/가로)의 정보로 파악했습니다.

  1. 출발 통나무와 도착 통나무의 위치를 저장.

  1. bfs로 진행

** 4차원의 visit 배열

  • 통나무 모양에 따라서

  • 5가지 행위에 대해서



1
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
 
//BOJ :: 1938 통나무 옮기기     
public class Main1938_통나무옮기기2 {
    private static char[][] map;
    private static boolean[][][][] visit;
    private static int N;
    private static ArrayList<pair> nowLog;
    private static ArrayList<pair> destLog;
    private static log end;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        nowLog = new ArrayList<>();
        destLog = new ArrayList<>();
 
        map = new char[N][N];
        visit = new boolean[5][2][N][N];
 
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'B')
                    nowLog.add(new pair(i, j));
                if (map[i][j] == 'E')
                    destLog.add(new pair(i, j));
 
            }
        } //// input
 
        Collections.sort(nowLog);
        Collections.sort(destLog);
        int type;
        if (nowLog.get(0).y == nowLog.get(1).y) type = 2; else type = 1;
        log start = new log(nowLog.get(1).y, nowLog.get(1).x, type, 0);
 
        if (destLog.get(0).y == destLog.get(1).y) type = 2; else type = 1;
        end = new log(destLog.get(1).y, destLog.get(1).x, type, 0);
        System.out.println(bfs(start));
    } // end of main
 
    static int[] dy = { -1, 1, 0, 0, -1, -1, 1, 1 };
    static int[] dx = { 0, 0, -1, 1, -1, 1, -1, 1 }; // 상하좌우//대각선
 
    public static int bfs(log start) {
 
        Queue<log> q = new LinkedList<>();
        q.add(start);
        // visit[][start.type-1][start.y][start.x] = true;
        while (!q.isEmpty()) {
            log now = q.poll();
            int y = now.y;
            int x = now.x; // 통나무의 mid 정보
            int type = now.type;
            int cnt = now.cnt;
            // 종료조건 확인
            if (y == end.y && x == end.x && type == end.type) {
                return cnt;
            }
 
            for (int i = 0; i < 5; i++) {
                if (i == 4) { // 회전
                    boolean isPossible = true;
                    // 회전할 수 있는 범위 확인.
                    for (int chk = 0; chk < 8; chk++) {
                        int ny = y + dy[chk];
                        int nx = x + dx[chk];
                        if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || map[ny][nx] == '1') {
                            isPossible = false;
                            break;
                        }
                    }
                    if (!isPossible) continue;
                    int ntype;
                    if (type == 1) ntype = 2;
                    else ntype = 1;
                    if (!visit[i][type - 1][y][x]) {
                        q.add(new log(y, x, ntype, cnt + 1));
                        visit[i][type - 1][y][x] = true;
                    }
 
                } else if (i < 4) {// 상하좌우 이동
                    int ny = y + dy[i];
                    int nx = x + dx[i];
                    if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || map[ny][nx] == '1'
                            || visit[i][type - 1][ny][nx])
                        continue;
                    if (type == 1) { // |
                        int topY = ny - 1;
                        int bottomY = ny + 1;
                        if (topY < 0 || bottomY > N - 1 || map[topY][nx] == '1' || map[bottomY][nx] == '1') continue;
                    } else { // -
                        int leftX = nx - 1;
                        int rightX = nx + 1;
                        if (leftX < 0 || rightX > N - 1 || map[ny][leftX] == '1' || map[ny][rightX] == '1') continue;
                    }
                    visit[i][type - 1][ny][nx] = true;
                    q.add(new log(ny, nx, type, cnt + 1));
                }
            }
        }
        return 0;
    }
 
    static class log {
        int y;
        int x;
        int type; // 1 : | // 2: -
        int cnt;
        public log(int y, int x, int type, int cnt) {
            super();
            this.y = y;
            this.x = x;
            this.type = type;
            this.cnt = cnt;
        }
    }
 
    static class pair implements Comparable<pair> {
        int y;
        int x;
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
        @Override
        public int compareTo(pair o) {
            if (o.x == this.x)
                return o.x - this.x;
            else if (o.y == this.y) {
                return o.y - this.y;
            }
            return -1;
        }
    }
}
cs


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 16235 : 나무재테크  (1) 2019.04.13
[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
[SWEA] 2383. 점심식사 시간  (5) 2019.04.04
[SWEA] 1949. 등산로 조성  (0) 2019.04.01
[BOJ] 1805. 나무자르기  (4) 2019.03.22

문제 보기 >> [SWEA] 2383. 점심식사 시간





1. 입력을 받을때 사람의 위치와 계단의 위치를 각각의 ArrayList에 저장.



2. whichStair(int len) 메소드 - 중복순열

각각의 사람이 어떤 계단을 이용할 것인지 중복순열 코드를 돌려서 모든 케이스를 다 확인할 수 있게 한다.

중복순열이 완성되면, 우선순위큐에 데이터를 add.


우선순위 큐의 타입으로 pair2 클래스를 선언해서 사용했다.

**pair2 클래스

각 사람에 대해 할당된 시간과 이용할 계단, 그리고 상태를 저장하기 위한 클래스.

status ==> -1 : 계단에 도착하기 전 // 0 : 계단에 도착은 했지만 대기중. // 1 : 계단에 올라가 있음.  

하단 pair2 클래스 선언 부분에서 Compare부분을 보면, 기본적으로 시간이 짧은 순으로 정렬되고 시간이 같을땐 status를 기준으로 정렬했다. 

이 compare는 우선순위큐에서 정렬되는 기준을 정하기 위함이다.

같은 시간내에서 계단에 올라가 있는 사람을 먼저 pop 하기위해서 시간이 같을때에는, status가 큰 수를 우선적으로 정렬되도록 했다.



3. goStair() 메소드

각각의 사람이 어떤 계단을 사용할것인지 완성이 되었다면, goStair() 메소드에서 실제로 계단에 보내본다.

inStair 배열은 각각의 계단을 몇명의 사람이 이용하고 있는지 카운트해주는 배열이다.


우선순위큐(pq)에서 시간이 짧은사람(계단에 있는사람->대기->도착 순으로 pop) 부터 확인해본다.

가장 바깥 while문은 시간에 대한 while문이다 min이 1씩 증가한다.

min이 일정 시간일때 안쪽 while을 돌면서 해당 시간인 사람을 pop 해서 검사한다.


status 가 1이 아니면 아직 계단을 이용하지 못한 사람이고, 그 중 -1이면 이제 계단에 도착한 사람이므로 계단 이용전 필수 대기시간인 +1을 더 해준다.

시간과 상태를 갱신해 다시 pq에 add해주고 계단이용자수를 증가시켜준다.

** 여기서 ntime이 의미하는 것은 시작점부터 계단까지 시간 + 대기시간 + 계단 이용시간이다.

즉, 계단 이용이 끝날때까지는 큐에서 나올 수 없다.


만약 계단이 포화상태라 갈수 없다면 시간만 +1 해주고, status는 0으로 다시 add한다.



status가 1이면 계단에 올라있는 상태에서 시간이 다 지난것을 의미하기 떄문에 해당 inStair을 감소시켜주고 큐에 다시 add 하지 않는다.


4. q가 비게되면 최소값을 갱신해준다.



1
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
//SWEA :: 2383 점심 식사시간 
//2019-04-04
public class Solution2383_점심식사시간 {
    private static int[][] map;
    private static int N, ans;
    private static ArrayList<pair> ppl;
    private static ArrayList<pair> stair;
    private static int[] set;
    private static PriorityQueue<pair2> pq;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            ppl = new ArrayList<>();
            stair = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 1)
                        ppl.add(new pair(i, j));
                    if (map[i][j] > 1)
                        stair.add(new pair(i, j));
                }
            } /// input
            set = new int[ppl.size()];
            ans = Integer.MAX_VALUE;
            whichStair(0);
 
            System.out.println("#" + tc + " " + ans);
        } // end of tc
    }// end of main
 
    public static void whichStair(int len) {
        if (len == ppl.size()) { // 사람의 명수만큼 계단 고르기 --> 중복순열
            // System.out.println(Arrays.toString(set));
            pq = new PriorityQueue<>();
            
            for (int i = 0; i < len; i++) {
                int py = ppl.get(i).y;
                int px = ppl.get(i).x;
                int sy = stair.get(set[i]).y;
                int sx = stair.get(set[i]).x;
                int t = Math.abs(py - sy) + Math.abs(px - sx);
                pq.add(new pair2(t, set[i], -1));
            }
            goStair();
            return;
        }
 
        for (int i = 0; i < stair.size(); i++) {
            set[len] = i; // 인덱스 저장
            whichStair(len + 1);
        }
    } // end of whichStair
 
    public static void goStair() {
        /*
         * pair2의 status -1: 계단에 도착 전 0: 계단에 도착은 했지만 대기중. 1:계단에 올라가 있음
         */
        int min = 0;
        int[] inStair = new int[stair.size()]; // idx번째 계단에 몇명의 사람이 있는지 확인.
        while (!pq.isEmpty()) {
            min++;
 
            while (!pq.isEmpty()) {
                pair2 front = pq.peek();
                if (front.time != min)
                    break;
                pq.poll();
                int mystair = front.stair;
                if (front.status != 1) { // 계단 아직 안감.
                    //계단을 내려갈 수 있나?
                    if (inStair[mystair] < 3) { // 갈 수 있으면
                        int ntime = 0;
                        if (front.status == -1) { //계단에 최초 도착이면 1분 대기한다.
                            ntime = front.time + 1 + map[stair.get(mystair).y][stair.get(mystair).x];
                        } else if (front.status == 0) { //이전에 도착해 대기하고있었으면 바로 계단에 간다.
                            ntime = front.time + map[stair.get(mystair).y][stair.get(mystair).x];
                        }
                        pq.add(new pair2(ntime, front.stair, 1));
                        inStair[mystair]++;
                    } else { // 계단이 포화 상태라 갈 수 없다면.
                        pq.add(new pair2(front.time + 1, front.stair, 0));
                    }
                } else { // front.status == 1//계단에 있는 상태.
                    inStair[mystair]--;
                }
            }
        }
        ans = ans > min ? min : ans;
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    } // end of pair
 
    static class pair2 implements Comparable<pair2> {
        int time;
        int stair;
        int status;
 
        public pair2(int time, int stair, int status) {
            super();
            this.time = time;
            this.stair = stair;
            this.status = status;
        }
 
        @Override
        public int compareTo(pair2 o) {
            // TODO Auto-generated method stub
            if (this.time == o.time) {
                return o.status - this.status;
            } else {
                return this.time - o.time;
            }
        }
 
    }
}// end of class
cs


저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 15685. 드래곤 커브  (5) 2019.04.09
[BOJ] 1938 통나무 옮기기  (0) 2019.04.05
[SWEA] 1949. 등산로 조성  (0) 2019.04.01
[BOJ] 1805. 나무자르기  (4) 2019.03.22
[BOJ] 14502 : 연구소  (2) 2019.03.12

문제 >> [SWEA] 1949. 등산로 조성






1
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
mport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
//SWEA :: 1949 등산로조성
//2019-04-01
public class Solution1949_등산로조성 {
    private static int[][] map;
    private static boolean[][] visit;
    private static int N;
    private static int K;
    private static ArrayList<pair> top;
    private static int bottom;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken()); // 최대 K만큼 한 번 지형을 깎는다
 
            map = new int[N][N];
            top = new ArrayList<>();
            int max = -1;
            bottom = 21;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (max < map[i][j]) {
                        max = map[i][j];
                        top.clear();
                        top.add(new pair(i, j));
                    } else if (max == map[i][j]) {
                        top.add(new pair(i, j));
                    }
                    bottom = bottom > map[i][j] ? map[i][j] : bottom;
                }
            } ////// input
 
            ans = -1;
            for (pair p : top) {
                visit = new boolean[N][N];
                dfs(p.y, p.x, 1, false);
 
            }
 
            System.out.println("#" + tc + " " + ans);
        } // end of tc
    }// end of main
 
    static int[] dy = { -1, 1, 0, 0 };
    static int[] dx = { 0, 0, -1, 1 };
    static int ans;
 
    private static void dfs(int y, int x, int len, boolean cut) {
        // cut이 true 면 공사를 했다.
 
        visit[y][x] = true;
 
        ans = ans < len ? len : ans;
 
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny > N - 1 || nx < 0 || nx > N - 1 || visit[ny][nx])
                continue;
            if (map[ny][nx] < map[y][x]) {
                dfs(ny, nx, len + 1, cut);
            } else { // 같거나 높으면
                if (!cut) { // cut이 false면 아직 공사를 안한 상태
                    for (int k = 1; k <= K; k++) {
                        int tmp = map[ny][nx];
                        map[ny][nx] -= k;
                        if (map[ny][nx] < map[y][x])
                            dfs(ny, nx, len + 1, true);
                        map[ny][nx] = tmp;
                    }
                }
            }
            visit[ny][nx] = false;
        }
 
    }
 
    static class pair {
        int y;
        int x;
 
        public pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
 
    }
}
cs

dfs와 약간의 백트래킹을 이용해 풀었습니다 ~~~~~

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[BOJ] 1938 통나무 옮기기  (0) 2019.04.05
[SWEA] 2383. 점심식사 시간  (5) 2019.04.04
[BOJ] 1805. 나무자르기  (4) 2019.03.22
[BOJ] 14502 : 연구소  (2) 2019.03.12
[BOJ] 17070 : 파이프 옮기기 1  (0) 2019.03.12
문제 >> [BOJ] 1805. 나무자르기




1
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
51
52
53
54
55
56
57
58
59
60
61
62
jaimport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
//BOJ :: 1805 나무자르기
//2019-03-22
 
public class Main2805 {
    static int N;
    static long[] arr;
    static long M,ans;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());//나무 수
        M = Long.parseLong(st.nextToken());//상근이가 필요한 나무의 길이
        
        ans = Long.MIN_VALUE;
        arr = new long [N];
        st = new StringTokenizer(br.readLine(), " ");
        long maxh = Long.MIN_VALUE;
        
        for(int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            maxh = maxh<arr[i]? arr[i] : maxh;
        } 
        /////////////////input
        
        bsearch(0, maxh);
        System.out.println(ans);
        
        
    }
    static boolean flag = false;
    public static void bsearch(long start, long end) {
        //if(flag) return;
        if(start>end) {
            return ;
        }
        
        long mid = (start+end)/2; //현재 절단기 높이
        
        //종료조건
        long sum = 0;
        for(int i=0;i<N;i++) {
            long tmp = arr[i]-mid;
            sum += ((tmp>0)? tmp : 0);
        }
        //sum이 M보다 작으면 높이를 낮춘다.
        //sum이 M보다 크면 높이를 높인다.
        if(sum>=M) {
            ans = ans < mid? mid:ans;
            bsearch(mid+1, end);
        }
        else if(sum<M) {
            bsearch(start, mid-1);
        }
        return;
    }
}
 
cs


모든 데이터 타입을 long 으로 해주어야 합니다 

저작자표시

'Algorithm Problem Solving' 카테고리의 다른 글

[SWEA] 2383. 점심식사 시간  (5) 2019.04.04
[SWEA] 1949. 등산로 조성  (0) 2019.04.01
[BOJ] 14502 : 연구소  (2) 2019.03.12
[BOJ] 17070 : 파이프 옮기기 1  (0) 2019.03.12
[SWEA] 1761 : 프로세서 연결하기  (0) 2019.03.08

+ Recent posts

티스토리툴바