October 7, 2022

ER model - 3

ER model - 3 ER model - 1, ER model - 2 Relationship degree 관계에 참가하는 엔티티 타입의 수. 다음과 같다. Binary relationship: 두 엔티티 타입이 관계를 맺음. 가장 흔한 경우 Recursive relationship Ternary relationship Recursive(Unary) Relationship 한 개의 엔티티가 자기 자신과 관계를 맺음. 직원들은 최대 1명의 상사가 있고, 또한 직원은 최대 N명의 부하가 있는 경우 다음과 같이 표시. Ternary Relationship 3개의 엔티티가 관계를 맺음. 사람이 가게에서 물건을 사는 경우의 다음과 같이 표시.

October 6, 2022

ER model - 2

ER model - 2 ER model - 1 How to Represent Relationship 관계를 표현하는 제약 조건들. Cardinaltiy Ratio Constraint Participation Constraint Structual Constraint Cardinality Ratio Constarint 관계를 맺는 두 엔티티 타입에 대해, 한 엔티티가 얼마나 많은 다른 엔티티와 관련될 수 있는 지를 나타내는 제약 조건 1:1 : 두 엔티티 타입의 엔티티들이 각각 일 대 일 대응 1:N : 한 엔티티 타입의 엔티티가 다른 엔티티 타입의 여러 엔티티와 연관 됨. 역은 성립 X N:M : 한 엔티티 타입의 엔티티가 다른 엔티티 타입의 여러 엔티티와 연관 됨.

October 5, 2022

ER model - 1

ER model - 1 ER model이란 실제 세계의 정보들을 Entity, Attribute, Relation의 구조로 표현한 개념적 데이터 모델 Entity 단독으로 존재하는 객체. 엔티티들의 집합을 entity type이라고 하며 ER diagram에서 네모로 표시. Attribute 엔티티가 가지는 속성. ER diagram에서 원으로 표시. Key Attribute: 다른 객체들과 다른 고유한 값을 가진 attribute, 밑줄로 표시. Composite Attribute: Attribute들이 모여서 만들어진 attribute. Multi-valued Attribute: 여러 개의 값을 가지는 attribute, 두 개의 원으로 표시. Derived Attribute: 다른 attribute로 부터 계산되어저 나온 attribute.

August 22, 2022

Socket

Socket Host 네트워크에 연결된 모든 장치 중에서 IP를 할당받은 것 Process Host 내부에서 실행중인 프로그램. 다른 종단점에서 동작하는 프로세스는 message를 주고 받음으로써 동작함. Client / Server 연결을 시작하는 프로세스를 client, 연결을 기다리는 프로세스를 server라고 부름. P2P에도 해당 Socket 프로세스가 통신하기 위해 메시지를 보내거나 받는 소프트웨어 인터페이스. Application process와 transport-layer protocol 사이의 문 역할. Port (Number) 한 호스트 내에서 프로세스를 식별하기 위해 사용되는 번호. 웹 서버의 경우에는 80번을 사용한다. socket이 생성될 때 할당된다.

July 30, 2022

Process Synchronization

Process Synchronization Process Synchronization 이란 여러 process는 concurrent / parallel하게 실행됨. Process간 공유하는 데이터에서 무결성 문제가 생길 수 있음. Race Condition 여러 프로세스가 동일한 데이터를 concurrent하게 조작할 때, 실행 순서에 따라 결과가 달라지는 현상을 의미. 이런 문제가 생기지 않게 하기 위해 프로세스간의 동기화(synchronization)가 필요. Critical Section 프로세스간 공통 변수를 교환하거나, 테이블을 업데이트하거나, 파일을 쓰는 등의 역할을 하는 코드. 두 개 이상의 프로세스가 critical section에서 실행되면 안 되고, 이 문제를 critical section problem이라 명명.

July 7, 2022

DB Normalization

DB Normalization Functional Dependency 관계형 데이터베이스 R의 attribute로 이루어진 집합 X, Y와 R 내의 모든 튜플 t에 대해, t[X]의 값이 정확히 한 개의 t[Y]의 값과 연결된다고 하자. 이 때 X는 Y를 함수적으로 결정한다고 하고, Y는 X에 함수적으로 종속되어 있다고 한다. X → Y로 표기함. 즉, t1[X] = t2[X] ⇒ t1[Y] = t2[Y] Superkey Superkey는 다음 조건을 만족하는 attribute 집합. Superkey → {Every attribure} Candidate Key Minimal한 superkey. Attribute를 하나 이상 지울 경우 더 이상 superkey가 아님.

July 15, 2021

BOJ 14003

BOJ 14003 문제 설명 문제: 백준 14003 이 문제는 어떤 수열이 주어졌을 때 그 수열 내의 가장 긴 증가하는 부분 수열과 그 길이를 구하는 문제입니다. 수열의 길이는 최대 $10^6$이므로 $O(N^2)$ 알고리즘으로는 풀기 힘듭니다. 사전 지식 $O(N^2)$ 으로 가장 긴 증가하는 부분 수열의 길이 구하기 가장 긴 증가하는 수열을 영어로 Longest Increasing Subsequence, 줄여서 LIS라고 부르겠습니다. 또한 입력으로 주어진 수열을 $A_i$ (i는 1 이상 N 이하, N은 수열 A의 길이)라고 표시하겠습니다.

June 26, 2021

BOJ 3955

BOJ 3955 문제 설명 문제: 백준 3955 이 문제는 주어진 자연수 K, C에 대해서 $KX_K + 1 = CX_C$가 되는 자연수 $X_K, X_C$를 찾는 문제, 더 정확히는 $X_C$를 찾는 문제입니다. $K, X_K, C, X_C$는 각각 사람의 수, 각 사람이 받는 사탕 수, 사탕의 수, 사탕 봉지의 수를 나타냅니다. 위 방정식의 해를 구하기 위해 베주 항등식과 확장 유클리드 호제법을 이용합니다. 사전 지식 베주 항등식 베주 항등식을 설명하기 전에, 주어진 식을 다음과 같이 아주 조금만 변경해 봅시다.

May 12, 2021

BOJ 15997

BOJ 15997 문제 설명 문제 : 백준 15997 이 문제는 네 개의 나라가 리그 식으로 경기를 진행하고, 각 경기마다 승패 할 확률이 주어집니다. 각 나라는 승리 시 3점, 무승부 시 각 1점을 얻고, 점수가 높은 두 나라가 진출할 경우 각 나라가 진출할 확률을 구하는 문제입니다. 4C2 = 6이므로, 총 6번의 경기에 대한 승패 확률이 주어집니다. 알고리즘을 세워 푸는 문제라기보다는 구현 능력을 요구하는 문제입니다. 사전 지식 이 문제는 알고리즘을 요구하는 문제는 아니기 때문에 사전 지식은 거의 필요 없습니다.

May 4, 2021

BOJ 2623

BOJ 2623 문제 설명 문제 : 백준 2623 이 문제는 주어진 순서에 따라 번호들을 정렬시키는 문제, 더 정확히는 그래프를 위상 정렬(topological sort)시키는 문제입니다. 일반적인 위상 정렬 문제이지만, 이 문제에서는 정렬시키는 방법이 존재하지 않을 수도 있습니다. 사전 지식 이 문제를 풀기 위해서는 위상 정렬에 대한 내용과 C++에서 graph를 구현하는 방법에 대한 지식이 필요합니다. 위상 정렬에 대한 추가적인 설명은 참고 자료들을 확인해보시면 좋을 것 같습니다. 위상 정렬 위상 정렬이란 유향 그래프에서, 정점 u에서 v로 가는 간선이 있으면, u가 v 앞에 오도록 정점들을 배열하는 것을 의미합니다.