티어 : Silver 2 시간 제한 : 1 초 메모리 제한 : 256 MB 알고리즘 분류 : 다이나믹 프로그래밍
문제
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10,30, 10,20, 20,10} 이고, 길이는 3이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.
예제 입출력
Algorithm
가장 긴 감소하는 부분 수열은 가장 긴 증가하는 부분 수열을 이용 dp[i] : i번째 원소를 마지막으로 하는 부분 증가수열의 길이 1. 입력 받는 수열을 reverse 2. 가장 긴 증가하는 부분 수열 찾기
Code
N = int(input())
A = list(map(int, input().split()))
# 수열 reverse
A.reverse()
dp = [1] * N
for i in range(1, N):
for j in range(i):
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
티어 : Silver 2 시간 제한 : 1 초 메모리 제한 : 256 MB 알고리즘 분류 : 다이나믹 프로그래밍
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10,20, 10,30, 20,50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입출력
Algorithm
dp[i] : i 번째 원소를 마지막으로 하는 부분 증가 수열의 최대 길이 1. 리스트를 이중 for문으로 돌면서 자신보다 작은 index에 값이 작은 수가 몇 개 있는지 확인 ➝ i : 1 ~ N-1, j : 0 ~ i 2. j번째 원소가 i번째 원소보다 작으면 i번째 dp Table의 값과 j번째 dp Table의 값 + 1 중 큰 값으로 dp Table 갱신
Code
N = int(input())
A = list(map(int, input().split()))
dp = [1] * N
for i in range(1, N):
for j in range(i):
if A[j] < A[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
티어 : Silver 3 시간 제한 : 1 초 (추가 시간 없음) 메모리 제한 : 512 MB 알고리즘 분류 : 다이나믹 프로그래밍
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
예제 입출력
Algorithm
dp[i] : 1, 2, 3의 합으로 i를 만들 수 있는 개수 dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
Code
T = int(input())
for _ in range(T):
n = int(input())
dp = [0]*(11)
dp[1] = 1
dp[2] = 2
dp[3] = 4
for i in range(4, n+1):
dp[i] = dp[i-3]+dp[i-2]+dp[i-1]
print(dp[n])
티어 : Silver 4 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 자료 구조, 문자열, 스택
문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
출력
출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
예제 입출력
Algorithm
1. ( 모양인 경우 리스트에 해당 문자 append 2. ) 모양인 경우 리스트에서 pop 2.1. pop이 불가능하면, 마지막에 리스트에 뭔가 남아있으면 NO 반환 2.2. 마지막에 리스트에 아무것도 없으면 YES 반환
Code
T = int(input())
for _ in range(T):
string_ = list(input())
list_ = []
flag = False
for chr in string_:
# ( 모양인 경우 리스트에 해당 문자 append
if chr == '(':
list_.append(chr)
else: # ) 모양인 경우 리스트에서 pop
if len(list_) == 0: # 리스트에서 pop이 불가능한 경우
flag = True
break
list_.pop()
# 마지막에 리스트에 뭔가 남아있으면 NO 반환
if flag or len(list_) > 0:
print('NO')
else:
print('YES')
상호 배제(Mutual Exclusion) : 여러 Process/Thread가 동시에 한 자원에 접근하지 못하도록 막는것
점유와 대기(Hold and Wait) : Process/Thread가 자원을 점유한 상태로 다른 자원을 점유하기 위해 대기하는 것
비선점(Nopreemption) : Process에서 자원을 할당 받으면 작업을 완료할 때까지 System에서 Process의 제어를 뺏을 수 없음
순환 대기(Circular Wait) : 점유와 대기를 하는 형태로 Cycle에 갇혀 빠져나갈 수 없는 상태
3. 교착 상태 해결법
: 교착 상태의 해결법으로는 교착 상태 예방, 교착 상태 회피, 교착 상태 탐지 및 복구, 교착 상태 무시가 있다.
3.1. 교착 상태 예방
: 교착 상태 필요 조건 중 하나를 거부하는 방식으로 예방하는 방법이다.
교착 상태는 발생하지 않으면 좋지만, 교착 상태가 발생하지 않는 환경을 만들어버린다면 자원을 효율적으로 사용할 수 없다.
e.g., 필요 조건 중 점유와 대기 조건을 거부해 한 Process가 자신이 필요한 자원을 모두 사용할 수 있을 때만 작업을 시작한다면 자원을 효율적으로 사용할 수 없다.
3.2. 교착 상태 회피
: 교착 상태를 인정하고 피해가는 방법으로 자원을 요청할 때마다 System의 상태를 판단하고 회피하는 전략을 사용한다.
☞ Overhead가 심하다.
e.g., 은행원 Algorithm
은행원 Algorithm : System을 안전 상태/불안전 상태(교착 상태가 발생할 가능성이 있는 경우)로 구분하고 불안전 상태일 때는 대기하고 안전 상태일 때만 자원을 빌려주는 Algorithm으로 할당한 자원 수 고정, Process 수 고정, 제한된 시간 안에 자원 반납 등의 많은 조건이 필요하다. ☞ 현실에서는 자원이 동적으로 왔다갔다해 현실적으로는 불가능한 Algorithm이다.
3.3. 교착 상태 탐지 및 복구
: 교착 상태가 발생한 것 같을 때 탐지하고 복구하는 방법으로 교착 상태가 자주 발생하는 System에서 일반적으로 사용하는 방법이다.
☞ 교착 상태 회피에 비해 Overhead가 적다.
교착 상태 탐지 : 교착 상태 존재 여부 및 교착 상태에 연관된 Process와 자원을 알아내는 전략을 사용하며 교착 상태의 4가지 필요 조건 중 순환 대기 존재 여부에 초점을 맞춰 교착 상태를 탐지한다. ☞ 탐지 Algorithm도 회피 Algorithm과 마찬가지로 Overhead가 있으므로 얼마나 자주(주기적으로, 자원 즉시 할당 여부에 따라, CPU 이용률에 따라 등) 탐지 Algorithm을 호출하는지가 관건이다. e.g., 자원 할당 그래프 소거
교착 상태 복구 : 순환 대기를 깨서 교착 상태로부터 회복하는 방식이다. e.g., 순환 대기가 깨질 때까지 Process 종료, 순환 대기에 포함된 Process 제어권 뺏고 Rollback ☞ 희생양이 될 Process는 남은 수행 시간, 자원 유형의 수 등 Systemp마다 다른 기준의 우선순위에 따라 결정된다. e.g., MySQL의 경우 Transaction Timeout시 교착상태이든 아니든 가장 작은 Transaction을 Rollback하며 Transaction의 크기는 삽입, 업데이트, 삭제된 행 수에 의해 결정된다.
Race Condition(경쟁 조건) : 여러 Process/Thread가 동시에 같은 Data를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황
Synchronization(동기화) : 여러 Process/Thread를 동시에 실행해도 공유 Data의 일관성을 유지하는 것
Critical Section(임계 영역) : 공유 Data의 일관성을 보장하기 위해 한 번에 하나의 Precess/Thread만 진입해 실행가능한 영역
Mutual Exclusion(상호 배제) : 공유 Data의 일관성을 보장하기 위해 한 번에 하나의 Process/Thread만 진입해 실행할 수 있도록 하는 Algorithm
1. Mutual Exclusion을 보장할 수 있는 방법
: Lock을 사용한다.
// 실제 동작 Code가 아닌 개념 이해를 돕기위한 Code 입니다.
do{
acquire lock // 여러 Process/Thread가 Lock을 획득하기 위해 경합
critical section // Lock을 획득한 단 하나의 Process/Thread만이 Critical Section에 들어가 실행
release lock // Critical Section에서의 실행을 마치면 Critical Section을 빠져나오며 Lock 반환
reminder section
} while(TRUE)
Mutual Exclusion을 보장하는 상호 배제 기법으로는 Spin Lock, Mutex, Semaphore가 있다.
2. Spin Lock
: Lock을 획득할 수 있을 때까지 Lock 획득을 반복해서 시도하는 방식
☞ Lock을 획득하기 전까지 Lock이 다른 Process/Thread에 의해 선점되었는지 확인하는 것 자체가 CPU Cycle을 잡아먹는 일이기 때문에 CPU를 낭비한다.
Single Core에서는 Spin Lock으로 Lock이 반환되기를 계속 기다리더라도 Lock을 획득하기 위해서는 이미 누군가 획득한 상태인 Lock을 반환해야하는데 이는 결국 Context Switching이 필요하다. ☞ Single Core에서의 Spin Lock은 이점이 없다.
Multi Core에서는 Spin Lock으로 Lock이 반환되기를 기다리다가 Thread 1이 Lock을 반환하자마자 Thread 2가 Lock을 획득하므로 Context Switching이 일어나지 않는다.
2.1. 동작 예제
// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.
volatile in lock = 0; // global -> 여러 Thread가 동시에 Lock에 접근 가능
// 여러 Thread가 호출할 함수
void critical(){
while(test_and_set(&lock) == 1); // 여러 Thread가 while loop를 통해 Lock을 획득하려 시도
... critical section // Lock 획득에 성공한 하나의 Thread가 Critical Section에 들어와 실행
lock = 0 // Critical Setcion에서 수행 완료 후 Lock 반환
}
// 실제 TestAndSet()의 동작 원리를 간단히 구현한 함수
// 공유되는 Lock에 대해 Lock의 원래 저장값을 반환하고 Lock 값은 1로 변경
int test_and_set(int* lockPtr){
int oldLock = *lockPtr; // 원래 가지고 있던 Lock 값 가져오기
*lockPtr = 1; // Lock 값을 1로 변경
return oldLock; // 원래 가지고 있던 Lock 값을 반환
}
2.2. 동작 과정
Thread 1이 먼저 수행된 후 Thread 2가 수행되는 경우
1. Thread 1의 test_and_set()의 반환값 = 0 (원래 Lock은 0으로 초기화 되어있었기 때문) 이므로 while loop 탈출해 Critical Section에서 작업을 수행한다.
☞ test_and_set()을 호출했으므로 Lock은 1로 변경된다.
2. Thread 2의 test_and_set()의 반환값 = 1 (1번 과정에서 Thread 1에 의해 Lock이 1로 변경되었기 때문) 이므로 while loop에 갇힌다.
☞ test_and_set()을 호출했으므로 Lock은 계속 1로 갱신된다.
3. Thread 1이 Critical Section에서 작업을 마치고 Lock을 반환한다.
☞ Lock이 0이 된다.
4. Thread 1이 Lock을 반환함과 동시에 Thread 2의 test_and_set() 반환값 = 0 (3번 과정에서 Thread 1에 의해 Lock이 0으로 변경되었기 때문) 이 되므로 while loop 탈출해 Critical Section에서 작업을 수행한다.
☞ test_and_set()을 실행했기 때문에 Lock은 1로 변경된다.
5. Thread 2가 Critical Section에서 작업을 마치고 Lock을 반환한다.
☞ Lock이 0이 된다.
∴ test_and_set()을 통해 Thread 1과 Thread 2가 Critical Section 안에서 동시에 작업을 수행할 수 없다. (= 상호 배제)
① 실행 중간에 간섭받거나 중단되지 않는다. ② 같은 Memory 영역에 대해 동시에 실행되지 않는다. ☞ 2개 이상의 Process/Thread에 의해 동시에 호출된다고 해도 CPU Level에서 알아서 먼저 하나 실행시킨 후 실행이 끝나면 이어서 다른 하나를 실행시키는 방식으로 동기화시켜 실행된다.
3. Mutex
: Lock이 다른 Process/Thread에 의해 획득된 상태라면 Lock이 반환될 때까지 Queue에서 대기하는 방식
☞ CPU Cycle을 불필요하게 낭비하는 것을 최소화한다.
3.1. 동작 예제
// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.
Class Mutex{
int value = 1; // 이 값을 획득해야 Lock을 획득할 수 있다. (공유되는 Data)
// value를 변경할 때 Critical Section 안에서 변경하지 않으면 Race Condition이 발생할 수 있다.
int guard = 0; // Critical Section에 포함되어있는 value를 변경하기 위해 사용되는 변수
}
Mutex::lock(){
while(test_and_set(&guard)); // value 값 변경 전 guard를 획득하기 위해 여러 Process/Thread가 경합
// guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
if (value == 0){ // 누군가 value를 이미 획득한 상태라면
현재 Thread를 Queue에 넣는다; // 작업을 잠시 멈추고 쉬고 있을테니 Lock이 풀리면 깨워달라며 Queue에 들어간다.
guard = 0; & go to sleep // Process/Thread를 Queue에 넣고 guard 변경(guard 반환)
}
else{ // value를 획득할 수 있으면
value = 0; // value 획득하고 value를 0으로 갱신(value 획득한 상태를 표시)한다.
guard = 0; // value 변경 후 guard 0으로 갱신(guard 반환)
}
Mute::unlock(){
while(test_and_set(&guard)); // value 변경 전 여러 Process/Thread가 guard를 획득하기 위해 경합
// guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
if (Queue에 하나라도 대기 중이라면){
그 중 하나를 깨운다;
}
else{ // 대기중인 Process/Thread가 하나도 없으면
value = 1; // value를 1로 갱신(value 반환)
}
guard = 0; // value 변경 혹은 Queue에서 Process/Thread 꺼낸 후 guard 0으로 갱신(guard 반환)
}
mutex -> lock(); // 여러 Process/Thread가 Lock을 획득하기 위해 경합
... critical section // Lock을 획득한 하나의 Process/Thread가 Critical Section에 들어가 작업 수행
mutex -> unlock(); // Critical Section에서 작업을 마친 후 Lock 반환
Multi-Core 환경이고 Critical Section에서의 작업이 Context Switching보다 빨리 끝난다면 Spin Lock이 Mutex보다 더 이점이 있다.
Mutex와 Spin Lock의 Context-Switching
Mutex는 잠들고 깨는 과정(Queue에 넣고 빼는 과정)에서 Context Switching이 발생한다.
Spin Lock은 잠들고 깨는 과정(Queue에 넣고 빼는 과정)이 없기 때문에 Context Switching이 발생하지 않는다.
4. Semaphore
: Signal Mechanism을 가지는, 하나 이상의 Process/Thread가 Critical Section에 접근 가능하도록 하는 방법
4.1. 종류
Binary Semaphore(이진 세마포어) : 한 번에 1개의 Process/Thread만 Critical Section에 접근할 수 있다. ☞ Mutual Exclusion을 보장한다.
Counting Semaphore : 한 번에 value개의 Process/Thread만 Critical Section에 접근할 수 있다.
4.2. 동작 예제
// 실제 동작 Code가 아닌 개념 이해를 돕기 위한 Code입니다.
Class Semaphore{
// 한 번에 value개의 Process/Thread가 Critical Section에 접근할 수 있다.
int value = 1; // value를 획득해야 Lock을 획득할 수 있다. (공유되는 Data)
// value를 변경할 때 Critical Section 안에서 변경하지 않으면 Race Condition이 발생할 수 있다.
int guard = 0; // Critical Section에 포함되어있는 value를 변경하기 위해 사용되는 변수
}
Semaphore::wait(){
while(test_and_set(&guard)); // value 변경 전 guard를 획득하기 위해 여러 Process/Thread가 경합
// guard를 취득한 하나의 Process/Thread만 value 변경 Logic을 수행한다.
if (value == 0){ // 이미 누군가 value를 획득한 상태라면
현재 Process/Thread를 Queue에 넣는다; // Process/Thread가 일을 잠시 멈추고 쉬고 있을테니 Lock이 풀리면 깨워달라며 Queue에 들어간다.
guard = 0; & go to sleep; // Process/Thread를 Queue에 넣은 후 guard 변경(guard 반환)
}
else{ // value를 획득할 수 있다면
value -= 1; // value 획득한 후 value를 1 감소(value 획득한 상태를 표시)
guard = 0; // value 변경 후 guard 0으로 갱신(guard 반환)
}
}
Semaphore::signal(){
while(test_and_set(&guard)); // value 변경 전 guard 획득하기 위해 여러 Process/Thread가 경합
// guard를 획득한 하나의 Process/Thread만 value 변경 Logic을 수행
if (Queue 안에 하나라도 대기 중이라면){
그 중에 하나를 깨워 준비시킨다;
}
else{ // 대기중인 Process/Thread가 하나도 없으면
value += 1; // value 1 증가(value 반환)
}
guard = 0; // value 변경 혹은 Queue에서 Process/Thread 꺼낸 후 guard 0으로 갱신(guard 반환)
}
Semaphore -> wait(); // 여러 Process/Thread가 Lock을 획득하기 위해 경합
... critical section // Lock을 획득한 하나의 Process/Thread가 Critical Section에 들어가 작업 수행
semaphore -> signal(); // Critical Section에서 작업을 마친 후 Lock 반환
