#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
stack<int> st;
int a;
cin >> a;
string str;
int temp;
while (a--) {
cin >> str;
if (str == "push") {
cin >> temp; //***
st.push(temp);
}
else if (str == "pop") {
if (st.empty()) {
printf("-1\n");
}
else {
printf("%d\n", st.top());
st.pop();
}
}
else if (str == "size") {
printf("%d\n",st.size());
}
else if (str == "empty") {
if (st.empty() == 0) {
printf("0\n");
}
else {
printf("1\n");
}
}
else if (str == "top") {
if (st.empty()) {
printf("-1\n");
}
else {
printf("%d\n",st.top());
}
}
}
}
하지만 파이썬으로 코딩을 준비하게 되면서 알고리즘 기초 문제를 다시 접하면서 만난 문제입니다.
이건 너무 쉽다고 생각해 쉽게쉽게 작성해가고 있었습니다.
📌 기본 Logic은 stack 이라는 class 를 구현하고 if-elif 문으로 각각의 case에 맞게 처리하자 였습니다.
#10828
class stack:
def __init__(self): # 스택 객체 생성
self.items = []
def push(self, item): # 스택 요소 추가 push(.append())
self.items.append(item)
def pop(self): # 스택 요소 삭제 pop()
if self.items == []:
return -1
return self.items.pop()
def top(self): # 스택 맨 앞 요소 리턴
if self.items == []:
return -1
return self.items[-1]
def isEmpty(self): # 스택이 비었는지 확인(비었으면 True 리턴)
if not self.items:
return 1
return 0
stk =stack()
num = int(input())
for i in range(num):
a = input()
if a == "top":
print(stk.top())
elif a== "pop":
print(stk.pop())
elif a=="size":
print(len(stk.items))
elif a=="empty":
print(stk.isEmpty())
else:
b = a.split(" ")
stk.push(b[1])
이런 식으로 작성하니 시간초과가 떴습니다..!!!😵💫
시간초과 날 구석이 없는데 어떻게 시간초과 가 나는지 의문이었고 그래서 구글에 " 파이썬 시간초과 " 를 검색해보았고
로직의 worst time 의 문제가 아니라면 input() 사용을 바꿔 보라는 글을 확인했습니다.
입력값을 받아 저장해하는 경우 input() 으로 구현하시는 분들이 많으실텐데 sys 라는 파이썬의 표준 라이브러리를 사용하면 훨씬 빠른 시간에 적은 메모리를 사용하여 입력 받을 수 있답니다!
import sys
변수 = sys.stdin.readline()
2. 배열에 원소 추가할 때 인덱스로 접근하기
배열에 원소를 추가하면 보통 빈 배열을 만들고 append 로 추가할 때가 많은데, 이 경우 입력 받을 개수(N)를 알고있다면 N 만큼 배열을 초기화해두고 인덱스로 각자 접근해서 저장하는 것이 효율이 좋습니다.
## 7의 배수 10개 저장하기
# 수정 전
arr = []
for num in range(1, 11):
arr.append(num * 7)
# 수정 후
arr = [0 for _ in range(10)]
for num in range(1, 11):
arr[num] = num * 7
3. 줄바꿈을 출력해야하는 경우 문자열로 바꿔 출력하기
줄바꿈이 자주 반복된다면 print()보다 '\n' 사용하는 것이 좋습니다. 그렇기 때문에 문자열 변수에 정답을 저장해놓고 한 번에 출력하는 것이 효율에 좋습니다.
# [1, 2, 3, 4]를 줄바꿈으로 하나씩 출력하기
# 1
# 2
# 3
# 4
# 수정 전
arr = [1, 2, 3, 4]
for n in arr:
print(n)
# 수정 후
answer = ""
for n in arr:
answer += str(n) + '\n'
print(answer)
4. 재귀 깊이 늘려주기
파이썬은 기본적으로 재귀호출을 1000번으로 제한하고 있기 때문에 더 많은 재귀를 요구할때는 재귀깊이를 늘려주어 사용해야합니다!
import sys
sys.setrecursionlimit(1000000) #1000000번 재귀가 가능하도록 변경하기
5. queue 로 구현할 때 리스트보다 deque 사용하기
Python 에서는 리스트보다 collections.deque 모듈을 사용하는 것이 더 빠르기 때문에 Queue 를 통해 문제를 해결해야하는 상황이 있다면 deque 를 사용하는 것이 시간이 단축됩니다!
# 수정 전
queue = []
for i in range(N):
queue.append(i)
for i in range(N):
print(queue[-1])
queue.pop(-1)
# 수정 후
from collections import deque
queue = deque()
for i in range(N):
queue.append(i)
for i in range(N):
queue.popleft()
📌한 개의 정수를 입력받을 때
import sys
a = int(sys.stdin.readline())
😨 그냥a = sys.stdin.readline()하면 안되나요? 👉sys.stdin.readline()은 한줄 단위로 입력받기 때문에, 개행문자가 같이 입력 받아집니다. 만약3을 입력했다면,3\n이 저장되기 때문에, 개행문자를 제거해야 합니다. 또한, 변수 타입이 문자열 형태(str)로 저장되기 때문에, 정수로 사용하기 위해서 형변환을 거쳐야 합니다.
이전에 배웠었던 instructor 와 department 스키마를 combine한 schema가 있다고 가정해보자.
우리는 이전에 배웠던 스키마가 더 좋은 스키마라고 알고있다. 그러면 지금 이 big_instructor 스키마를 어떨때 decomposition 하는 것이 맞는지 그리고 어떻게 decompositon 하는 것이 맞는지에 대해 알아보려고한다.
그전에 잠시 functional dependency에 이야기해보자.
💡Functional Dependency
관계형 데이터베이스의 설계에서 중복된 데이터가 최소화되도록 데이터베이스의 구조를 결정하는 것을 정규화 (normalization)라고 한다. 정규화된 데이터베이스가 그렇지 않은 데이터베이스에 비하여 더욱 효율적으로 데이터에 대한 연산을 수행할 수 있는 것은 매우 당연한 것이다. 이러한 데이터베이스의 정규화 과정에서 'Functional Dependency'이라는 개념은 매우 중요하게 이용된다.
Functional Dependency은 수학에서의 함수와 같이 두 필드의 집합이 many-to-one 관계로 사상되는 것을 말한다. 즉, 함수와 같이 어떠한 값을 통해 종속 관계에 있는 다른 값을 유일하게 결정할 수 있다는 것이다. 데이터베이스에서의 함수 종속성을 더욱 명확하게 정의하면 다음과 같다.
어떤 테이블 RR에 존재하는 필드들의 부분집합을 각각XX와YY라고 할 때,XX의 한 값이YY에 속한 오직 하나의 값에만 사상될 경우에 "YY는XX에 함수 종속 (YYis functionally dependent onXX)"이라고 하며,XX→YY라고 표기한다.
예를 들어, 테이블에 [생일]과 [나이]라는 필드가 존재할 경우에 [나이] 필드는 [생일] 필드에 함수 종속이다. 즉, 생일을 알고 있다면, 나이에 대한 필드를 참조하지 않거나, 아예 필드를 유지하지 않아도 나이를 결정할 수 있다. 데이터베이스 설계 단계에서 함수 종속 관계에 있는 필드를 찾는다면, 그 만큼 중복된 데이터를 줄일 수 있다. 그러므로, 데이터베이스 설계 단계에서 각 정보들 간의 함수 종속 관계를 찾는 것은 매우 중요하다.
중복이 일어난 현상 자체를 금지하는 것이 아닌 어떤 relation이 적법한 지 정의하는 constraint를 Functional Dependencies이라고 하는 것이다. 즉 현상에 집중하는 것이 아니라 Rule에 집중한다고 보면 된다.
- Functional Dependencies require that the value for a certain set of attributes determines uniquely the value for another set of attributes. ( 어떤 attributes set은 다른 attributes set을 uniquely 하게 결정한다. )- A functional dependency is a generalization of the notion of a key. (f-d 는 일종의 key 의 개념의 일반적인 형태 == key 는 일종의 functional dependecy 이다. ) >> key에 속하는 attribute가 relation 에 있는 모든 다른 값을 결정하기 때문에 functional dependency의 일종이라고 할 수 있다.
+ Use of Functional Dependencies
: 모든 functional dependencies의 set을 "F" 라고 가정할 때, F는 두 가지로 사용될 수 있습니다.
(1) 어떤 relation 을 검사하기 위해 F 사용
(2) 사전에 relation을 정의시에 모든 F를 만족해야 생성이 가능하게 하기 위해 F 사용
Functional Dependency의 특징
Trivial : 만약 b가 a 에 속하는 속성일 때, a->b 는 trivial하게 만족한다고 볼 수 있다.
Closure : 주어진 FD 속성에서 Trivial 한 속성을 제외하고 추론을 통해 얻을 수 있는것을 closure한다고 한다.
>> 주어진 FD에서 유도할 수 있는 모든 FD를 closure 라고 하는 것.
>> closure한 속성과 trivial한 속성을 모두 합쳐놓은 집합을 F+ 라고 하고 F+ 는 F 의 superset이다.
+ F+를 구하는 과정은 O(2^n)time
Armstrong's Axioms
reflexivity: 만약 Y가 X의 부분집합이면, X→Y이다. ( Trivail 속성 )
augmentation: 만약 X→Y이면, XZ→YZ이다.
transitivity: 만약 X→Y이고 Y→Z이면, X→Z이다.
three rules are sound and complete
( 위의 규칙 세 개를 통해 나온 것은 언제나 true 이고, 3개의 규칙만 있으면 closure에 포함되어야하는 모든 FD 찾을 수 있다.)
union: 만약 X→Y이고 X→Z이면, X→YZ이다.
decomposition: 만약 X→YZ이면, X→Y이고 X→Z이다.
pseudotransitivity: X->Y 이고, YZ->A 이면 XZ -> A 이다.
잠시 functional dependency 에 대한 설명을 적었다. 다시 big_instructor의 내용으로 돌아와보자.
이 스키마에는 dept_name 이 정해지면 building 과 buget이 무엇인지 결정된다.
따라서 "Functional Dependency" 는
dept_name ---> building, budget 이라고 선언할 수 있다.
이때 dept_name 은 candidate key 가 아니기 때문에 key 가 가지고 있는 unique한 속성을 지킬 필요가 없어져서
building과 budget이 중복될 수 있음을 시사한다. 이럴때 decomposition은 필요한 것이다.
Lossy Decomposition
decomposition 시에 가장 조심해야할 부분은 원래 스키마에서 decomposition한 스키마들을 다시 조인할 시에 원래 테이블에 있던 정보와 동일해야한다. 만약 동일하지 않고 쓸데 없는 정보가 추가되는 현상을 "Lossy Decompositon" 이라고 한다.
즉 위의 사진처럼 decomposition 한 테이블을 조인한다면 name attribute 를 통해 조인을 하게되고, name은 key 의 역할을 할 수 없어서 원래 테이블과 동일한 테이블을 만들어내지 못합니다. 즉, "lossy decomposition" 이 일어났다고 보면 됩니다.
💡Lossless-join Decomposition
위에서 설명했던 lossy decomposition 과 반대되는 개념의 용어가 바로 "Lossless-join Decomposition" 이다.
다시 말해 decomposed 된 relationdmf 다시 join 했을 때 원래 relation이 나오는 것을 뜻한다.
💡1NF = First Normal Form
1NF는 각 로우마다 컬럼의 값이 1개씩만 있어야 합니다. 이를 컬럼이원자값(Atomic Value)를 갖는다고 합니다. 예를 들어, 아래와 같은 경우 Adam의 Subject가 Biology와 Maths 두 개 이기 때문에 1NF를 만족하지 못합니다.
즉, 추가적으로 이전에 배웠던 E-R Diagram에서 multi valued는 1NF를 만족하지 못함을 알 수 있습니다.
위의 정보를 표현하고 싶은 경우 이렇게 한 개의 로우를 더 만들게 됩니다. 결과적으로 1NF를 함으로써 데이터 redundancy는 더 증가하였습니다. 데이터의 논리적 구성을 위해 이 부분을 희생하는 것으로 볼 수 있습니다.
하지만 이렇게 atomic 하게 바꾸면 student age의 중복 값이 생긴 것을 확인할 수 있습니다. 즉 만약 student가 key 의 역할을 하고 있었다면 key 역할을 상실하게 되는 것을 확인할 수 있습니다.
즉 1NF는 Domain의 값이 atomic 해야하고 그
의미는 모든 테이블의 각각의 key를 가지고 있다는 의미와도 같음을 확인할 수 있습니다.
앞으로 우리가 배우는 모든 relation(=table) 들은 1NF는 무조건 만족해야한다고 가정하면서 나가겠습니다.!
추가적으로
Atomicity는 우리가 도메인의 요소들을 어떻게 사용하느냐에 달려있습니다.
예를 들어 주민번호를 주민번호 그 자체로만 사용한다면 atomicity를 만족하지만 생년월일의 정보만 사용하게된다면 divide를 해야하므로 non-atomicity 의 속성임을 확인할 수 있습니다.
따라서 주어진 정보를 application 입장에서는 그대로 이용하는 것이 좋습니다. 정보를 쪼개려고 한다면 Database 측면에서는 multivalue라고 인식하고 non atomicity이기 때문입니다.
>> Doing so is a bad idea : leads to encoding of information in application program rather than in the database.
💡BCNF ( Boyce-Codd Normal Form )
앞서 1NF : all domains are atomic == every relation should have a key 의 조건을 만족하는 것이었다.
BCNF는 1NF의 속성을 다 만족해야함과 동시에 " key를 제외한 다른 attribute는 FD를 통해 또 다른 attribute를 결정하면 안된다 " 라는 조건도 만족해야한다. 즉 FD 에. a->b 가 만족한다는 Rule 이 있다면 "a" 는 반드시 relation의 superkey 여야하는 것이다.
따라서 위에서 봤던 예제인 big_instructor에서 dept_name -> building, budget 의 rule은 big_instructor의 테이블이 BCNF를 만족하지 못하게 하는 것이다. ( dept_name이 super key 가 아니기 때문에..)
정리하면 BCNF가 되기 위해선
1. a-> b is trivial ( b는 a 에 포함)
2. a is super key for R
💡Decomposing a Schema into BCNF
스키마가 위에 언급했던 조건들을 위배한다면 조건들을 만족하여 BCNF를 만족하는 테이블을 만들기위해 decomposition을 해야합니다.
decompose 방법은 다음과 같습니다.
BCNF을 만족하지 않는 조건이 F 에서 a->b 라고 할 때
( a union b ) ( R - ( b - a ) )
위의 두 개의 테이블로 decomposition 하면 됩니다.
앞에서 계속 언급했던 예제로 한번 decomposition을 해본다면
dept_name -> building, budget 때문에 big_instructor가 BCNF 가 아니었다 따라서
a = dept_name, b = building, budget
R1 : ( a union b ) = ( dept_name, building, budget )
각각은 BCNF를 만족하고 Lossless join decomposition 인지만 확인한다면 제대로 된 분배였을 것입니다.
lossless 인지는 뒤에서 설명하도록 하겠습니다. 그전에
💡 BCNF and Dependency Preservation
어떤 attribute 관계에 대해 FD 를 사용자가 정의하고, table 을 decomposition 한 상태일 때,
각각의 relation만 가지고 (join을 하지 않은 상태 ) 모든 FD를 검사할 수 있는 상황을 " Dependency Preservation " 이라고 한다.
BCNF는 항상 Dependency Preservation을 만족하지는 않는다. 왜냐하면 조건들이 너무 까다로워서 decomposition 이 많이 일어나고, 따라서 FD를 검사하기 위해서는 테이블간의 join이 불가피한 상황이 일어날 수 있기 때문이다.
따라서 BCNF를 만족할 것이냐 Dependency Preservation을 만족할 것이냐 기로에 서있을때,
Dependency Preservation을 만족하는 것을 "3NF " 라고 한다.
💡3NF
trivial 하고 dependency preservation 을 만족하는 것
또 다른 말로
Transitivity Dependecy 가 없는 것이라고도 할 수 있다.
Transitivity Dependecy 는 a->b 이고 b->c 일때 a->b->c 의 관계가 성립하고 그때 a->c 를 알 수 있다.
즉 가운데에 있는 b를 통해 a->c 의 관계가 성립되는 것을 말한다. 만약 b 가 없이 a->c 의 관계가 성립한다면
transitivity dependency 가 성립하지 않고 3NF를 만족한다고 보면된다.
ex1
F = { ID -> dept_name, dept_name -> building, budget }
ID -> dept_name -> building, budget 으로 id -> building budget
즉, dept_name 이 없다면 관계가 성립하지 않기때문에 transitivity dependency를 만족한다.
다른 말로는 3NF는 만족하지 않는 것.
ex2
F = { dept_name, s_id -> i_id, i_id-> dept_name}
dept_name, s_id ->. i_id -> dept_name 이지만 i_id 가 없다고 하더라도 dept_name, s_id -> dept_name 은 trivial 관계로 설명 가능하다. 즉 transitivity dependency 는 성립하지 않고, 3NF 는 성립한다고 볼 수 있는 것.
Goals of Normalization
each relation scheme is in good form
the decomposition is a lossless-join decomposition
preferably, the decomposition should be dependency preserving.
세마포어를 사용하기에는 사용자 입장에서 코딩하기가 어렵다 보니 보다 쉬운 monitor가 도입된 계기를 만들었다.
monitior
응용프로세서가 효과적으로 호출할 수 있도록 하는 동기화 메커니즘
a high-level abstractionthat provides a convenient and effective mechanism for process synchronization
semaphore 사용 시 일어날 수 있는 상황
>> Mutual Exclusion property is violated
: mutex의 값을 증가시키는 signal 함수만 호출되어서
critical section에 여러 개의 process 가 들어와서 mutual exclusion을 위배한다.
>> Deadlock occurs
: mutex의 값을 감소시키는 wait 함수만 호출되어서
어떤 프로세스도 critical section 에 들어갈 수 없고 프로세스들 모두가 wait 함수에서
빠져나오지 못해 deadlock 이 걸리는 상황이 발생한다.
GOAL : Only one process at a time can be active within the monitor
Monitor는 class 와 매우 유사하게 구현하고 있다.
Critical Section에 1개의 process 만 들어오게 하기 위해서 즉 mutual exclusion 을 만족하기 위해서
class에
Condition Variable 추가
Wait, Signal 추가 >> condition variable에 접근할 수 있는 함수
Condition Variable하나의 프로세스만 active하고, 다른 프로세스는 기다리게 하도록 도입된게 condition 변수 입니다. condition 변수가 있어야 mutual exclusion 을 보장할 수 있습니다. condition 변수에 접근이 가능한 함수는 오직 wait 과 signal 함수만 가능합니다.
wait() 세마포어의 wait 함수는 while을 문을 만족해야 suspend 상황이 발생하지만 Monitior의 wait 함수는 호출되면 무조건적인 suspend 상황을 발생시킵니다. 즉 wait 함수를 호출한 프로세스는 컨디션 변수를 기다리는 큐에 insert 되도록 합니다.
singal() signal 함수는 wait 함수에 의해 큐에서 기다리고 있는 프로세스를 깨우는 함수입니다.
Monitor Code
1. 공유 변수 busy 는 처음에 false라서 처음 진입하는 프로세스는 조건문에 걸리지 않아 바로 critical section 에 즉 resource에 접근이 가능합니다.
2. 이후 이 프로세스는 busy 를 true로 바꿉니다.
3. 두번째로 오는 프로세스는 if 문에 걸려서 wait 함수를 호출합니다
>> mutual exclusion 속성 보장을 위해.
위에 사진처럼 monitor는 구현되어 있지만. 사용자는 옆에 사진처럼 함수만 호출하면 되는 아주 편리한 기능을 제공합니다.
즉 acquire() 를 통해 resource를 확보하고,
release()를 통해 리소스를 놓아 줍니다.
💡Liveness
Monitor를 사용 시에 synchronization을 지키기 위해 가장 중요한 함수는 wait 함수 입니다.
즉, 두 번째로 오는 프로세스는 첫 번째 프로세스가 critical section에 있으면 기다리게 됨.
wait 함수를 잘못 사용하게되면 프로세스가 아예 progress를 안하게 되는데 이것을 "DeadLock" 이라고 한다.
"deadlock"은 어떤 경우에도 빠져나갈 수 없는 경우를 말하며 이를 "indefinite block" 이라고도 한다.
💡Deadlock
two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes
즉, 두 개 이상의 프로세스가 무한정 수행이 안되는 경우를 의미한다.
1. S와 Q를 1로 초기화 ( == binary semaphore)
2. p1이 wait(Q)를 호출 Q=0 으로 바뀜
3. Context Switch 돼서 P0 가 wait(S)를 호출해서 S가 0으로 바뀜.
4. 다시 context switch 되어 p1이 wait(s) 호출 시에 s=0이므로 밑으로 수행 안됨 즉 wait 함수 빠져나가지 못한다.
5. p0에서도 wait(q) 호출 시 빠져나가지 못함.
두 개의 프로세스 다 wait함수 빠져나가지 못해 deadlock
+ starvation : indefinite blocking. A process may never be removed from the semaphore queue in which it's suspended
deadlock과의 공통점은 무한정으로 waiting하는 것.
💡Bounded buffer problem
Producer / Consumer process가 따로 있고,
공유 변수는 circular queue로 구현
mutex는 producer와 consumer 모두 circular queue에 접근하기에 필요하다.
Binary mutex의 값이 1이나 0인 경우
counting mutex의 값에 제약 조건 없이 정수 값을 가짐.
ch 3장 에서는 Synchronization을 위해 Spin Lock 을 사용했었음.
Counting 의 경우에는 full 함수는 producer가 차있는 갯수를 나타내고 empty 함수는 비어있는 슬롯의 개수를 나타냅니다.
Full 0으로 초기화 / empty 는 N으로 초기화
Producer : empty가 0이라면 wait(empty) 에 진입
Consumer : full이 0이라면 wait(full) 에 진입
1. 버퍼의 크기를 체크하는 것은 wait(empty)로
2. producer가 critical section에 진입했다면 consumer는 진입하지 못하게 설정하기 위해 wait(mutex)로 관리한다.
cf. critical section은 여기서 버퍼를 채우는 영역이다.
3. critical section에서는 buffer에 item을 추가한다.
4. signal(mutex)로 mutex 값을 1로 바꾸고 consumer도 c-s에 진입 가능하게 해준다.
5.signal(full)을 호출로 buffer에 한 개 추가됐다고 설정해준다.
1. wait(full) : buffer에 차 있는 것이 없다면 waiting
2. wait(mutex) : producer가 critical section 에 진입해 있다면 mutex의 값은 0으로 consumer는 waiting
3. signal(mutex)
4. signal(empty) : buffer에 있는 아이템을 사용했기에 비어있는 공간이 늘어났다고 설정해준다.
>> Dining-Philosophers Problem
: 다섯 명의 철학자가 같이 밥을 먹는데 젓가락이 철학자 사이에 하나씩 있고 서로 share한다고 가정한다. 한 사람이 젓가락을 사용하면 옆 사람을 기다려야하는 상황이다.
다섯 명의 동기화를 위해서 spinlock 사용은 복잡하여 semaphore 변수를 사용한다.
chopstick[5]는 다 1로 초기화.
chopstick[i]는 본인 기준 왼쪽 젓가락
chopstick[ (i+1) % 5 ] 는 오른쪽 젓가락
둘 중 하나라도 wait 문을 빠져나오지 못한다면 젓가락 사용 불가.
두 개를 다 확보했더라면
// eat
식사가 끝나면 왼쪽.오른쪽 젓가락에 대한 signal 함수를 호출
semaphore 값 1증가 다른 철학자 식사 가능
문제점 : Deadlock
다들 첫 번째 line인 왼쪽 젓가락을 가지고 있고, 오른쪽 젓가락의 available을 기다리면 아무도 식사 못하는 deadlock 상황.
