문제

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

코드

def factorial(n):
    if n>0:
        return n*factorial(n-1)
    else: return 1

import sys
n=int(sys.stdin.readline())
cnt=0
res=factorial(n)
while True:
    if res%10==0:
        cnt+=1
        res//=10
    else: break
print(cnt)

문제 해결

팩토리얼 함수로 주어진 팩토리얼 값을 구한 후 10으로 나눠질 때마다 카운트를 세주면 된다

문제

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

코드

import sys, heapq
input = sys.stdin.readline

def insertNum(num):
    temp_right = 0
    temp_left = 0
    if len(left_max_heap)==len(right_min_heap):
        heapq.heappush(left_max_heap, [(-1)*num, num])
    else:
        heapq.heappush(right_min_heap, num)

    if right_min_heap:
        if left_max_heap[0][1] > right_min_heap[0]:
            temp_right = heapq.heappop(right_min_heap)
            temp_left = heapq.heappop(left_max_heap)[1]
            heapq.heappush(right_min_heap, temp_left)
            heapq.heappush(left_max_heap, [(-1)*temp_right, temp_right])

N = int(input())
left_max_heap = []
right_min_heap = []

for i in range(N):
    num = int(input())
    insertNum(num)
    print(left_max_heap[0][1])

문제 해결

<문제 로직>

1. leftHeap배열과 rightHeap배열이 있으면 (leftHeap과 rightHeap모두 힙정렬된 배열),

숫자를 차근차근 leftHeap과 rightHeap에 번갈아 가며 채워준다.

2. 이때 중간값은 무조건 leftHeap에서 제일 큰 숫자이다.

3. 만약 rightHeap에서 제일 작은 숫자가 leftHeap보다 작을 경우,

leftHeap의 제일 큰 숫자와 rightHeap의 제일 작은 숫자의 위치를 바꿔 준 후, leftHeap에서 제일 큰 숫자를 출력해준다.

<힙정렬을 사용하는 이유>

다른 숫자들의 정렬은 신경쓸 필요 없이, leftHeap에서는 가장 큰 숫자, rightHeap에서는 가장 작은 숫자만 비교하면 된다.

힙정렬을 사용하면, 가장 큰 숫자와 작은 숫자만 간단하게 비교할 수 있다.

leftHeap의 경우, 최대힙(max heap)을 사용하여 leftHeap[0]에 항상 제일 큰 숫자가 위치하게 하고,

rightHeap의 경우, 최소힙(min heap)을 사용하여 rightHeap[0]에 항상 제일 작은 숫자가 위치하게 한다.

문제

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

코드

import sys
input=sys.stdin.readline

data=[]
n,k=map(int, input().split())
for i in range(n):
    data.append(int(input()))

start, end=1, max(data)
while start<=end:
    need=0
    mid =(start+end)//2
    for i in range(n):
        need+=data[i]//mid
    if need>=k:
        start=mid+1
    else:
        end=mid-1
print(end)

문제 해결

이분탐색의 기본 문제이다.

start를 1, end를 가장 긴 길이로 설정후 

잘라진 랜선 개수가 n보다 많으면, mid 밑으로는 볼 필요가 없다.

만약 102cm 랜선을 2개로 자른다면, 50cm로 잘라도 2개, 51cm로 잘라도 2개다.

이 문제에서는 최대 랜선 길이를 구해야 하므로, end를 출력시켜야 한다.

문제

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

import sys
a, b, c= map(int, sys.stdin.readline().split())
#분할정복의 아이디어 
def DaC(a, b):
    if b==1:
        return a%c

    tmp=DaC(a, b//2)

    if b%2==0:
        return tmp*tmp%c
    else:
        return tmp*tmp*a%c

print(DaC(a,b))

문제

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

안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어.

(뚜벅 뚜벅)

얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터볼~

(펑!) 헐랭... 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가...ㅜㅠ

(터벅터벅)

어? 누구지?

오박사 : 나는 태초마을의 포켓몬 박사 오민식 박사라네. 다솜아, 포켓몬을 잡을 때는, 일단 상대 포켓몬의 체력을 적당히 바닥으로 만들어놓고 몬스터 볼을 던져야 한단다. 자, 내 포켓몬 이상해꽃으로 한번 잡아보렴. 포켓몬의 기술을 쓰는 것을 보고 포켓몬을 줄지 안줄지 결정을 하겠네. 자 한번 해보아라. 다솜아.

이다솜 : 이상해꽃이라...음.. 꽃이니깐 왠지 햇빛을 받아서 공격을 할 것 같은데... 음... 이상해꽃! 햇빛공격!!!

(꼬렛이 이상해꽃에게 공격을 받아 체력이 25 감소했다.)    가라! 몬스터 볼!!!    (꼬렛을 잡았습니다.)    야호! 신난다. 꼬렛을 잡았다.

오박사 : 오우!! 방금 쓴 공격은 솔라빔이라고 하네.. 어떻게 공격을 한 건가? 솔라빔이란 공격에 대해서 공부를 한 건가?

이다솜 : 꽃이니깐 왠지 햇빛을 제대로 받으면 광합성을 해서 음.. 그냥 그럴 것 같아서요 ☞☜

오박사 : 다른 아이들은 넝쿨채찍이나, 나뭇잎 공격을 하는데, 다솜이는 역시 뭔가 다르구나. 그럼 나와 함께 연구소로 가자꾸나. 내가 포켓몬을 한 마리 줄 테니, 너의 꿈을 펼쳐보아라. 꿈은 이루어진단다.

이다솜 : 네! 오박사님, 고마워요.ㅜㅜ

오박사 : 가자. 나의 연구소는 너의 옆집의 아랫집이란다. 같이 가도록하자. 지금 포켓몬을 주마.

이다솜 : 네. 야호!!

'

오영식 : 어? 오박사님 얘는 누구인가요?

오박사 : 얘는 너의 라이벌이 될 친구 이다솜이라고 하네. 자, 포켓몬을 한 마리 골라보도록 해봐라 다솜아. 레이디퍼스트 네가 먼저 골라봐라.

이다솜 : 저는 생각해둔 포켓몬이 있어요. 피카츄 골라도 될까요?

오박사 : 그래 여기 피카츄가 한 마리 있단다. 피카츄를 가져가거라.

오영식 : 그럼 저는 이브이를 가져가겠어요. 그럼 나중에 보자 이다솜.

이다솜 : 그럼 꼬렛을 다시 잡으러 가야겠다. 영식아, 그리고 민식박사님 빠잉!

이다솜 : 피카츄 공격!

가라 몬스터 볼!

이다솜 : 야호! 신난다. 꼬렛을 잡았다!!!!!

이다솜 : 그럼! 일단 사천왕을 이기고 오겠어!

이다솜 : 여기가 사천왕과 대결하려면 가야하는 곳인가..

경비원 : 사천왕과 대결을 하려면, 마을의 체육관 리더를 이겨서 배지를 8개를 모아야 한다네... 배지를 모아서 오도록 하게

이다솜 : 잉ㅠㅜ... 그럼 배지부터 모아야 하는구나ㅠㅜㅠㅜ 나쁘당 그냥 좀 봐주지..

<1 년 후>

그동안의 줄거리 : 이다솜은 일단 상록 숲의 체육관 리더에게 도전을 했다. 하지만 상록숲 체육관의 리더는 실종된 상태. 따라서 회색마을부터 도전하기로 했다. 체육관의 리더를 이기면서, 로켓단을 해체시키기도 하고, 여러 가지 사건도 있었다. 결국 전설의 포켓몬도 잡고, 이제 사천왕을 이기려고 도전하기로 했다. 사천왕은 모두 가볍게 이기고, 이제 마지막 라이벌 오!영!식! 이다.

오영식 : 훗. 1년 전의 그 이다솜이 사천왕을 이기고 현재 포켓몬 마스터인 나에게 덤벼? 어디 한번 덤벼보시지.

이다솜 : 헐랭... 나를 우습게보네.... 한번 두고 보시지! 그럼 대결이닷!

이다솜 : 휴... 이겼다.

오영식 : 내가 지다니 분하다. ㅜㅜ

오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

이게 오박사님이 나에게 새로 주시려고 하는 도감이야. 너무 가지고 싶다ㅠㅜ. 꼭 만점을 받아줬으면 좋겠어!! 파이팅!!!

코드

import sys
input=sys.stdin.readline
n, m=map(int, input().split())
dic={}
dic2={}

for i in range(n):
    name=input().strip()
    dic[name]=(i+1)
    dic2[i+1]=name

for i in range(m):
    action=input().strip()
    if action.isdigit()==True:
        print(dic2[int(action)])
    if action.isalpha()==True:
        print(dic[action])

문제해결

문제가 길어서 그렇지 딕셔너리를 이용하면 복잡한 문제를 쉽게 해결할 수 있다.

입력 받은 값이 정수인지 확인하는 isdisit()함수와 문자인지 확인하는 isalpha() 함수를 이용하면

생각보다 쉽게 코드작성을 할 수 있다.

문제

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

코드

import sys
input=sys.stdin.readline

e, s, m= map(int, input().split())

year=s
if e==15: e=0
if s==28: s=0
if m==19: m=0

while True:
    if year%15==e and year%28==s and year%19==m:
       print(year)
       break
    else: year +=28

문제 해결

브루트포스 알고리즘을 활용하여 주어진 조건을 만족하는 가장 빠른 연도를 출력하면 된다.

여기서 제일 중요한 부분은 (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)이 이렇게 범위를 갖기 때문에 

주의해서 문제를 풀어야한다. 

문제

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

import sys
input=sys.stdin.readline

dp=[0]*((10**6)+1)

n=int(input())
for i in range(2, n+1):
    dp[i]=dp[i-1]+1
    if i%2==0:
        dp[i]=min(dp[i], dp[i//2]+1)
    if i%3==0:
        dp[i]=min(dp[i], dp[i//3]+1)

print(dp[n])

Semaphore

• semWait : Process 를 Block 시킬 수 있는 명령어이다.
• semSignal : 내가 아니라 Queue에 있는 프로세스를 Ready로 옮겨 실행할 수 있게 해준다.

Semaphore는 Critical Section뿐 아니라, 많은 동기화 문제에 사용된다.
↳ 특히 Critical Section을 다룰 때는 무조건 초기 세마포 변수 값을 1로 설정해야 한다!

• Race Condition : 실행 순서에 따라 결과가 어떻게 될지 모르는 상황
  → 여러 프로세스가 Critical Section 을 동시 접근할 때 발생한다.

어느 위치에 semWait과 semSignal를 사용할지 잘 선택해야 한다.

Mutual Exclusion Using Semaphore

하늘색 네모 부분은 해당 프로세스가 Blocked Queue 에서 대기하고 있다는 의미이다.

세마포 방과 문에 비유하기

step1

여러 프로세스들이 Critical Section에 진입하려고 문에 서 있다고 가정해보자.

step2

Process 2가 먼저 문을 열고 Critical Section에 들어가서 문을 닫아버리고 s 값을 0으로 바꾼다.
이후 접근하는 프로세스들은 s 값이 음수가 되기 때문에 Blocked Queue에 들어가서 대기하게 된다.

• s <= 0 : 문이 닫힌 상태
• s > 0 : 문이 열린 상태

step3

Process2가 Critical Section 실행을 마친 후,
나갈 때 semSignal 명령어를 통해 대기하던 프로세스를 문 안으로 데려온다.
s > 0 (s == 1) 이되면, 문이 다시 열리는 것을 의미한다.

Semaphore는 좋은 도구인가?

1. Mutual Exclusion O
2. Deadlock X
3. Livelock X
4. Busy-Waiting X
5. Starvation △
   • Strong Semaphore X (Queue 순서대로 진행)
   • Weak Semaphore O

Binary Semaphore Primitives

지금까지 진행했던 Semaphore 는 Counting Semaphore 이다.
Binary Semaphore는 Semaphore 값을 0 아니면 1만 설정 가능하다.

Binary Semaphore는 작은 group의 문제들을 해결할 수 있다.

semWaitB

Binary Semaphore 에서는 Semaphore 값 S가 0이 되면 무조건 Block을 시킨다.
→ 몇 개가 block 되어 있는지는 알 수 없다.

semSignalB

Queue에서 프로세스를 꺼낼 때 Semaphore 값 S를 보고는 몇개의 프로세스가 Queue에 있는 지 알 수 없다.
⇒ Queue 자체를 확인한다. → isEmpty()

Buffer

Producer Process

데이터를 생성해서 Buffer에 쓴다.

Consumer Process

Buffer에서 데이터를 읽어서 작업한다.

Producer Process와 Consumer Process는 한 번에 하나만 Buffer에 접근할 수 있다!

위의 버퍼를 I/O Buffer라고 가정하자.
Memory Data → I/O buffer → I/O Device 출력

두 Producer Process 가 동시에 버퍼에 접근하여 데이터를 쓸 수 있고, 두 Concumer Process가 동시에 버퍼에 접근하여 데이터를 출력할 수 있다.
이렇게 프로세스가 동시에 버퍼에 접근하는 문제는 Critical Section 해결 방법과 동일하게 해결할 수 있다!

동시 buffer 접근 문제

Critical Section 해결 방법과 동일하게 해결할 수 있다!

Buffer가 비어 있는 문제

Consumer Process 가 Buffer에서 데이터를 가져갈 수 없다.

Buffer의 크기 제한

Producer Process 가 Buffer에 데이터를 쓸 수 없다.

⇒ Buffer의 크기 문제를 해결해야 한다!

Producer/Consumer Problem

1. 보통의 상황:
   • Producer는 데이터를 생성하고 buffer 에 데이터를 놓는다.
   • Consumer 는 buffer에서 item을 가져간다.
   • 오직 한번에 하나의 Producer나 Consumer만 buffer에 접근할 수 있다.
2. 문제:
   Producer가 꽉찬 buffer에 데이터를 추가하지 못하거나 Consumer가 비어있는 buffer에서 데이터를 가져가지 못하는 상황

Bounded Buffer

처음엔 버퍼가 비어 있다.

In

Producer Process가 다음에 Data를 쓸 위치

Out

Consumer Process가 다음에 Data를 읽을 위치

in > out

out > in

위의 그림에서 아래 그림으로 바뀌는 동안, Producer 는 b[5] 부터 한바퀴를 돌아 b[2]까지 데이터를 쓴 것이고, Consumer는 b[4]까지 데이터를 읽은 것이다.

Buffer 가 비었을 때?

in == out → 데이터가 빈 것이라고 볼 수 있다.

Buffer 가 꽉찼을 때?

in == out → 데이터가 꽉 것이라고 볼 수 있다.

⇒ 그렇다면 어떻게 Buffer가 비고 꽉찼는지 구분할 수 있을까?
↳ 버퍼가 꽉차기 전에 버퍼 하나를 비워둔다.

⇒ 즉, in == out-1 → 버퍼가 꽉 찼다고 인식한다.

Funcions in a Bounded Buffer

Producer

• (in + 1) % n == out → Buffer가 가득찬 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에 데이터 값을 넣고 in값을 하나 증가시킨다.

Consumer

• in == out → Buffer가 빈 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에서 데이터를 읽고 out 값을 하나 증가시킨다.

Busy-Waiting O & Buffer 1개 낭비

좋은 Solution이 아니다.
⇒ Semaphore 를 이용해서 해결하자

Bounded Buffer using Semaphores

• semWait : 상황에 따라 프로세스를 기다리게 한다.
• semSignal : 상황에 따라 기다리고 있던 프로세스를 풀어준다.

프로세스가 기다려야 하는 상황 3가지

1. Producer Process의 입장에서 buffer가 가득 찼을 때
2. Consumer Process의 입장에서 buffer가 비었을 때
3. Producer Process와 Consumer Process가 Critical Section에 진입할 때 → 한 번에 하나만 접근해야하므로 기다려야 한다.

Producer Process, Consumer Process, Critical Section 의 Blocked Queue를 하나로 관리하지 않는다.
⇒ 3개의 Queue에서 3개의 Semaphore를 관리해야 한다.

Semaphores Logic

1. 프로세스가 기다려야 하는 상황을 생각해야 한다. (n개)
2. n → 같은 Queue에서 기다려도 되는 프로세스들인지 판단하여 필요한 Queue의 개수를 판단한다.

Semaphore를 사용한 Buffer 관리 코드

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        semWait(e);
        semWait(s);
        append();
        semSignal(s);
        semSignal(n); // 버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.
    }
}
void consumer()
{
	while(true) {
    	semWait(n);
        semWait(s);
        take();
        semSignal(s);
        semSignal(e); // 버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.
        consume();
    }
}
void main()
{
	parbegin(producer, consumer); // 여러개의 producer들과 consumer 들이 함께 작업한다.
}

producer()

semSignal(n)의 의미:
버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.

consumer()

semSignal(e)의 의미:
버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.

즉, Producer와 Consumer는 서로 blocked 된 프로세스를 깨워준다.

Semaphore를 사용한 Buffer Logic

세개의 Semaphore 를 사용한다.
→ n, e, s
⇒ Semaphore 값이 어떻게 변하는지 알아야 한다.

s

Critical Section 처리 Semaphore

Critical Section에 여러 프로세스가 들어가려고 대기하면, s 값이 음수가 될 수 있다.

e

초기값: 버퍼의 크기

어느 순간 버퍼에 있는 빈칸의 수

• e > 0: 쓸 수 있는 버퍼의 수
• e <= 0: 버퍼가 꽉차, 버퍼에 데이터를 쓰기 위해 Blocked queue에서 대기 중인 Producer Process의 수

n

초기값: 0

어느 순간 버퍼에 있는 데이터의 개수

• n > 0: 읽을 수 있는 데이터의 수
• n <= 0: 버퍼가 비어있어, 버퍼의 데이터를 읽기 위해 Blocked queue에서 대기 중인 Consumer Process의 수

n+e

버퍼의 크기 (단, n > 0, e > 0 ⇒ blocked queue에 프로세스가 대기 중이지 않은 경우만 성립한다.)

n == 0 → 버퍼가 비었다.
e == 0 → 버퍼가 가득 찼다.

Q. 코드 순서를 변경할 때, 문제가 발생할 수 있다.

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        /*순서 교체*/
        semWait(s);
        semWait(e);
        /*순서 교체*/
        append();
        semSignal(s);
        semSignal(n); // 버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.
    }
}
void consumer()
{
	while(true) {
    	/*순서 교체*/
        semWait(s);
        semWait(n);
        /*순서 교체*/
        take();
        semSignal(s);
        semSignal(e); // 버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.
        consume();
    }
}
void main()
{
	parbegin(producer, consumer); // 여러개의 producer들과 consumer 들이 함께 작업한다.
}

코드 순서를 변경할 때, 숫자 값의 변화는 없어도, Deadlock이 발생할 수 있다.
semWait(e) ↔ semWait(s) 이나 semWait(n) semWait(s) 를 바꾸는 경우 문제 발생

1. buffer가 어떤 상황일 때 어떤 순서로 producer와 consumer가 도착했을 때 Deadlock이 발생하는가?
   → 2가지 case가 존재한다.
2. 시스템이 Semaphore 제공 X → hardware instruction으로 구현해야 한다.
   → hardware instruction으로 buffer 문제 해결이 가능한가?
   → 가능하다면, 어떻게 구현해야하는가? swap&compare, exchange가 몇 개 필요한가?