![]()
속성업무에서 필요하는 성질,특징분리되지않는 최소 데이터단위ex)이름, 학번, 학과번호 엔터티 엔터티 속성 속성 특징주식별자에 함수적 종속성업무에 필요해야함1개의 값을 가짐(원자성) 속성분류속성의 특징에 따라기본속성: 업무에서 추출된 속성설계속성: 업무를 규칙화하기위해 만들어진 속성파생속성: 계산을 빠르게 하기위해 만들어짐 엔터티 구성방식에 따라PK:인스턴스를 식별FK:다른 엔터티와의 관계에서 포함일반속성: 엔터티에 포함되있지만 PK/FK가 아님 분해 여부에 따라단일속성: 이름, ID복합속성: 주소(시,구,동)다중값속성: 상품리스트 속성 명명규칙업무사용서술식 X약어X유일한명칭 도메인속성의 범위 관계엔터티간의 연관성 관계종류존재적관계:부서 and 사원행위적관계:고객 and 주문 관계구..
![]()
모델링현실세계의 비지늬스 프로세스와 데이터 요구사항을 "추상화", "구조화"한다. 모델링 특징단순화: 불필요한 세부사항 제거추상화: 간략하게명확화: 정확한 현상 모델링 유의점중복: 같은 정보를 저장하지 않도록 설계비유연성: 사소한 변화에 모델 변경 변화하면 안됨비일관성: 모순,상관되는 내용 없어야함, 데이터 중복없어도 발생가능 모델링 요소엔터티속성관계 모델링 3단계개념적 모델링: 핵심 엔터티를 추출논리적 모델링: 데이터 정규화 수행, 세부속성,식별자,관계 표현물리적 모델링: 물리적으로 생성 ERD 절차엔터티 도출, 그림엔터티 배출엔터티 관계 설정관계명관계 참여도관계 필수여부 엔터티현실세계에서 독립저긍로 식별 가능한 객체나 사물인스턴트로 이루어진 집합인스턴스는 속성값들로 이루어짐 엔터티 특징유일한 ..
![]()
최장 공통 문자열(Longest Common Subsequence)두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제다이나믹 프로그래밍을 통해 해결한다. ex) 백준 9252 LCS 2 https://www.acmicpc.net/problem/9252ACAYKPCAPCAK를 입력받았을때 dp 배열[0, 0, 0, 0, 0, 0, 0][0, 0, 1, 1, 1, 1, 1][0, 1, 1, 1, 2, 2, 2][0, 1, 2, 2, 2, 3, 3][0, 1, 2, 2, 2, 3, 3][0, 1, 2, 2, 2, 3, 4][0, 1, 2, 3, 3, 3, 4]import sysfrom collections import dequest1=[" "]st2=[" "]st1.ex..
![]()
✨서로소 집합(Disjoin-set)공통 원소가 없는 두개 이상의 집합 ✨유니온 파인드(Union-Find)서로소 집합에 대해 union,find 연산을 수행하는 알고리즘Union:두 개의 집합을 하나의 집합으로 병합Find:원소가 어떤 집합에 속해있는지를 판단 EX) 백준 1717 집합의 표현https://www.acmicpc.net/problem/1717 import syssys.setrecursionlimit(1000000)def getparent(n): if(dic[n]==n):return n else: dic[n]=getparent(dic[n]) return dic[n]def unionparent(a,b): n1=getparent(a)..
✨이진탐색(Binary Search)정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식 ✨Python 코드 def binarySearch(array, value, low, high): if low > high: return False mid = (low+high) / 2 if array[mid] > value: return binarySearch(array, value, low, mid-1) elif array[mid] ✨Python bisect 라이브러리import bisectbisect_left(literable, value) # 왼쪽 인덱스를 구하기bisect_right(literabl..
![]()
✨트리(tree) 트리 구조란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 최상위노드: 루트노드 자식없는 노드: 잎 노드 잎노드가 아닌 노드: 내부 노드 ✨트리순회 전위 순회(preorder traversal),중위 순회(inorder traversal),후위 순회(postorder traversal)로 나뉘어진다. ex) 백준 1991번 트리순회 https://www.acmicpc.net/problem/1991 import sys class Node(): def __init__(self,v,l,r): self.value=v if(l=='.'):self.left=None else:self.left=l if(r=='.'):self.r..
✨ 투 포인트(Two-Point Algorithm) 2개의 포인터를 이용하여 배열속 원하는 값을 찾을수있다. O(N)의 시간 복잡도를 가진다. ex) 백준 두 수의 합 https://www.acmicpc.net/problem/3273 import sys n=int(sys.stdin.readline().rstrip()) li=list(map(int,sys.stdin.readline().rstrip().split(" "))) correct=int(sys.stdin.readline().rstrip()) li.sort() left_p=0 right_p=n-1 count=0 while True: if(li[left_p]+li[right_p]==correct): #같을때 left_p+=1 count+=1 elif(..
![]()
✨깊이 우선 탐색(DFS, Depth First Search) 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘 ex)백준 알고리즘 수업 - 깊이 우선 탐색 2 https://www.acmicpc.net/problem/24480 import sys from collections import deque visited=[] need_visit=deque() N,M,R=map(int,sys.stdin.readline().rstrip().split(" ")) visited_dic={i:0 for i in range(1,N+1,1)} graph={i:[] for i in range(1,N+1,1)} #무방향이므로 a,b 서로의 인접노드 추가 for i in range(M): a,..
