일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 백준
- 리눅스
- 파이썬
- 동적프로그래밍
- linux
- 순열
- 네트워크
- 프로그래머스
- dp
- OS
- 코딩 테스트
- 구글 킥스타트
- 브루트포스
- nlp
- PYTHON
- 그래프
- AI
- BFS
- DFS
- 프로그래밍
- 동적 프로그래밍
- 알고리즘
- 코딩
- 코딩테스트
- 딥러닝
- google coding competition
- kick start
- CSS
- 킥스타트
- 운영체제
- Today
- Total
목록CS 기초 (60)
오뚝이개발자
Domain types char(n) : 길이 n의 string varchar(n) : 최대 길이 n의 string int : 정수형 변수 numeric(p,d) : fixed point number, 전체 p digit, 소수점 이하 d digit(ex. numeric(3,1) 변수에는 25.1 저장 가능) float(n) : floating point number, 최소 n digit Integrity constraints란? 테이블에 부적절한 자료가 입력되는 것을 방지하기 위해 테이블을 생성할 때 각 컬럼(혹은 속성)에 대해 정의하는 규칙 More generally) DB에 추가되는 변동사항이 data consistency를 잃게 만들지 않도록 하는 제약조건 Integrity constraints(..
관계형 데이터 모델이란? 논리적인 relation 구조로 구성 사용자는 원하는 데이터(what)만 명시하고 어떻게(how) 찾을 것인지를 명시할 필요 X DB의 physical level과 logical level을 구분 -> 데이터 독립성 향상 + 단순한 구조 용어 정리 Relation : 2차원 구조의 테이블로 된 정보저장 형태 관계형 모델에서 DB는 이러한 relation이 여러개 모여있는 것 Attribute : 테이블에서 데이터들의 속성값(ID, name, dept_name, salary) attribute value는 atomic 해야 함(예컨대, 전화번호라면 지역번호로 split하면 X, 그 자체로 non-atomic하게 다루어야 함) Tuple(=Record) : 테이블에서 하나의 행 Do..
File system에서 DB로의 전환 파일시스템의 문제점 Redundancy(중복) : 각 파일마다 필요한 (중복되는)데이터를 각각 가지고 있어야 함 Inconsistency(비일관성) : 데이터에 변경사항이 생기면 각 파일을 모두 수정해야 하고, 이 과정에서 data inconsistency가 발생할 수 있다. Data isolation(데이터 추가, 검색의 문제) : 데이터가 여러 파일에 산재하고, 파일마다 양식이 달라 일률적인 검색,추가 작업이 어렵다. Difficulty in accessing data : 기존의 파일시스템은 기존의 프로그램 용도에 맞게 제작되므로 다른 프로그램 개발 시에는 다시 DB 작업을 해야 함 DB 시스템의 등장 목적은? 위와 같은 파일시스템의 문제를 해결하기 위해 DB ..
BFS(너비우선탐색)는 DFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. BFS는 큐로 구현할 수 있다. BFS는 최단거리를 찾는데 많이 이용된다. BFS는 다음과 같은 알고리즘으로 작동한다. 큐에서 하나의 노드를 꺼낸다. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 큐에 삽입한다. 아래와 같은 그래프가 있을 때, 이를 BFS로 탐색한다고 해보자. 노드를 방문할 때 해주어야 할 것이 두가지가 있는데 하나는 방문처리를 하는 것(그래프에선 빨강색으로 표시)이고 또 다른 하나는 큐에 넣어주는 것이다. 시작노드 1번을 큐에 넣고 방문처리한다. 큐에서 노드 1을 뺀다.(뺀 노드는 위쪽에 표시하였다.) 1과 연결된 노드 중 아직 방문하지 않은 2,3 노드를 큐에 넣고 방문처리한다. 큐에서 2를..
DFS(깊이우선탐색)는 BFS와 함께 그래프를 탐색하는 알고리즘 중 하나이다. DFS는 스택으로 구현할 수 있다. 하지만, 스택을 사용하지 않고도 재귀로 충분히 구현이 가능한데 컴퓨터에서 함수 호출의 과정이 스택으로 구현되는 것을 생각해보면 이해가 될 것이다. DFS, BFS 모두 인접행렬과 인접리스트 두 가지로 구현할 수 있다. 인접행렬로 구현할 경우 특정 item에 접근해 연결성 여부를 검사하는 것은 빠르지만 무조건 O(n^2)만큼의 메모리가 필요하다. 연결리스트를 사용한 인접리스트로 구현하는 경우 메모리 사용을 줄일 수 있지만 특정 item에 접근해 연결성 여부를 검사하는 과정이 좀 느릴 수 있다. 하지만 데이터가 많지 않은 경우 접근에 필요한 시간이 많이 소요되는 것은 아니므로 연결리스트를 사용해..
Dynamic programming이란? 일반적으로, 분할정복 알고리즘과 유사하게 큰 문제를 더 작은 문제로 나누어 푸는 기법(역시 최적해를 찾는데 사용되는 경우가 많다.) 결정적인 차이점은 다음과 같다. 동적 프로그래밍의 경우 작은 문제들이 반복된다.(피보나치의 경우 f(5)를 구하기 위해선 f(4),f(3)이 필요한데 f(4)를 구하기 위해 f(3)이 다시 필요하다.) 동적 프로그래밍의 경우 작은 문제들의 답이 항상 같다는 것이다. 따라서, 위의 경우처럼 반복되는 계산을 줄이기 위해 메모이제이션(Memoization)을 사용 실제로 피보나치 수열을 구하는 함수를 구현할 때, 재귀로 구현하게 되면 반복되는 계산으로 인해 수가 커지면 실행시간이 아주 오래 걸리지만, 동적 프로그래밍으로 구현하면 금방 해결..
Greedy algorithm이란? 매 의사결정마다 정해둔 조건에 따라 가장 좋아보이는 답을 선택하는 것 Greedy algorithm(탐욕알고리즘)은 어디에 쓰이나? 주로 특정 제한조건(Constraints)을 만족해야 하는 상황에서의 최적화 문제에 사용 예) machine scheduling, bin packing, minimum spanning tree(MST) MST란? Spanning tree란 그래프의 모든 노드를 포함하는 트리이다. 이 때, MST란 edge의 가중치 합의 최소인 spannig tree이다. Shortest path problem(추후 자세히 포스팅) 다익스트라 알고리즘(Single source all destination) MST(각 방법별로 추후 자세히 포스팅) Krusc..
Divide and conquer(분할정복)이란? 다음의 세 단계를 거치는 알고리즘이다. Divide : large problem을 small subproblem으로 분할 Conquer : recursive하게 각 subproblem을 푼다 Combine : subproblem의 답을 조합해 large problem의 답을 구한다. D&C 사용 예시 [8,2,6,3,9,1,7,5,4,2,8] 리스트 내에서 최솟값, 최댓값을 찾는 문제는 다음과 같이 풀 수 있다. 먼저 large set을 두 그룹으로 나누고, 나누어진 그룹에서 다시 두 그룹으로 나누고....이러한 과정을 풀기에 아주 단순한 small set이 될 때까지 반복한다. 즉, set의 원소 갯수 n이 2개 이하가 될 때까지 하는 것이다.(분할) ..