연속 부분 수열의 합? : 비어 있지 않는 숫자 배열에서 합이 최대가 되는 연속된 부분수열 구간의 합 아래와 같은 정수 배열이 있을 때, -2 -3 4 -1 -2 1 5 -3 4부터 5까지의 연속된 구간의 합은 7로 다른 부분 배열의 합보다 항상 크다. 이처럼 연속적인 부분 수열의 최대 합을 구하는 것이 이 문제의 목표이다. 1) 완전 탐색(Brute Force) : 가능한 모든 경우의 수를 조사해 찾는 알고리즘 👉 배열의 인덱스를 0부터 시작해 한 단계씩 나아가면서 중간값을 사용해 결과를 낸다. 먼저, 고려해야 할 부분은 크기가 1인 부분 수열의 합 현재까지 구한 답에 현재 배열의 인덱스 값을 더해서 끝내는 경우 현재까지 구한 값을 버리고 현재 인덱스 값으로 다시 시작하는 경우 현재 값과 현재까지 만든..
CS
1. 벨만 포드 : 그래프 상의 한 정점으로부터 다른 모든 정점들까지의 최단 경로를 구하는 알고리즘 - single-source 최단경로 알고리즘 - 가중치가 음수인 경우도 적용 가능 - 가중치가 사이클을 이루는 경우 불가능 - 시간 복잡도 O(nm) (최악의 경우 최대 n개의 정점, n-1개의 간선) - 동작과정 - 가장 가까운 노드를 탐색해 한 단계 거칠 때마다 최단 거리를 확정해 나감. - (n-1)번 반복해 모든 노드 간의 최단 거리를 완화해 나감. s에서 u까지의 최단 경로가 다음과 같다고 가정하자. 처음에는 모두 upper[] 상태 시작노드인 s는 upper[s] = dist [s] = 0 이다. 모든 간선을 탐색해 relaxation 과정을 반복한다. upper[a]
Sliding Window 란? 고정된 크기의 윈도우가 이동하면서 윈도우 내의 데이터를 이용해 문제를 풀어가는 알고리즘 배열, 리스트의 요소의 일정 범위의 값을 비교할 때 유용한 알고리즘이다. def maxSum(arr,k): n = len(arr) # length of arr if n 주어진 arr에서 더해서 최대가 되는 값 찾기 참고 https://www.thecrazyprogrammer.com/2017/05/sliding-window-protocol-program-c.html
1. 관계 데이터 모델 · 관계형 데이터베이스의 모델 · 모든 데이터는 릴레이션(≒테이블)으로 표현 2. 용어 1) 릴레이션 : 릴레이션 스키마 + 릴레이션 인스턴스 2) 릴레이션 스키마 · 속성들의 집합, 릴레이션의 논리적 구조 · 시간에 따라 불변 · 릴레이션 스킴 / 내포 3) 릴레이션 인스턴스 · 일정 시점에서의 투플(tuple)들의 집합 · 시간에 따라 가변 4) 투플(tuple) · 속성에 해당하는 데이터의 모임 5) 속성(attribute) · 단순 속성 : 단일값, 관계형 데이터베이스에 사용 · 복합 속성 : 단순 도메인의 결합, 하나의 속성으로 취급 (ex-DATE : YEAR, MONTH, DAY의 결합) · 속성값은 분해할 수 없는 원자 값 6) 도메인(domain) · 속성이 취할 ..
1. 데이터베이스 시스템 1) 데이터베이스 시스템의 구성요소 · 데이터베이스(DB) : 스키마 + 실제 데이터 · 데이터베이스 관리 시스템(DBMS) - 소프트웨어 · 데이터베이스 언어(DB language) · 데이터베이스 사용자(User) · 데이터베이스 관리자(DB Administrator) · 데이터베이스 컴퓨터(H/W) · 데이터베이스 도구(Tool/Utility) 2. 스키마(Schema) 1) 스키마 · 데이터베이스 = 스키마 + 실제 데이터 · DB 내 데이터 구조, 관계, 제약조건에 대한 명세 · 관점에 따라 스키마는 달라질 수 있음 ⇝ 응용 프로그램 관점 ⇝ 조직 및 기관 관점 ⇝ 물리적 저장 장치 수준의 관점 2) 3단계 스키마 구조 · 외부 스키마(External Schema) : ..
1. 파일을 이용한 데이터 1) 문제점 · 데이터의 중복 · 응용 프로그램이 기대하는 물리 구조 ex) 도서관리 프로그램용 학생 데이터파일과 학생상담 프로그램용 데이터 파일이 있을 때, 서로의 정보가 다르면 일관성 X 특정 프로그램의 포맷이나 필드, 타입, 길이 등이 다를 수 있다. · 데이터 종속성 - 파일 내부 구조에 응용프로그램이 영향을 받음 - 파일 구조를 바꾸면 정상 수행 되지 않음 · 데이터 중복성 - 동일한 내용의 데이터가 중복 관리 · 중복으로 인한 문제점 - 데이터 일관성 상실 - 보안성 취약 - 경제성 취약 - 데이터 무결성 취약 2) DBMS의 적용 3) DBMS의 필수 기능 · 데이터 정의 기능(DDL) - 사용할 데이터의 구조를 정의할 수 있어야 함 - 일관성 문제해결, 디스크 낭..
1. 정보와 데이터 1) 데이터(data) · 실세계에서 관찰된 사실(값) · 숫자, 문자, 문자열, 텍스트, 이미지로 표현 2) 정보(information) · 상황에 따라 적절한 결정을 할 수 있게 하는 지식 ex) 온도, 습도 기압 : 데이터 ↓ 일기예보 : 정보 2. 정보 시스템 1) 정의 · 조직체 활동에 필요한 데이터를 수집, 조직, 저장 · 데이터 처리를 통해 의사 결정에 유용한 정보 생성 2) 명칭 · 경영 정보 시스템 · 군사 정보 시스템 · 행정 정보 시스템 · 인사 정보 시스템 · 의사 결정 지원 시스템 - 데이터 웨어 하우스 - 데이터 마이닝 · 지식 관리 시스템 · 학사 행정 시스템 ⇛ 사용 목적, 용도에 따라 명칭이 달라짐 3) 작업 방식 · 배치 처리(batch processi..
1. DAG : Directed Acyclic Graph DAG란? 사이클이 존재하지 않는 방향 그래프 예를 들면, 라면을 끓이는 순서 어느 작업이 하나의 작업의 선행작업이 되는 경우, 자신으로 돌아올 수 없다. 👉 작업의 우선순위를 표현할 때 2. 위상정렬 우선순위를 표현하기 위해 사용 -> 노드들을 순서화하는 것 작업의 순서를 표현, 순서 유일 X 왼쪽에서 오른쪽으로 향하도록 한다. 1) 위상정렬을 통한 해결 방법 indegree(들어오는 차수)가 0인 노드를 선택한다. -> 차수가 같다면, 어느 노드를 선택해도 무방 -> indegree가 0인 노드를 모두 큐에 삽입 2. indegree가 0인 노드 중 선택된 노드와 그 노드와 연결된 에지를 제거 -> 큐에서도 선택된 노드 삭제 3. 1~2번 과정..
1. 깊이우선순회 DFS 출발 노드 s에서 시작 현재 노드를 visited로 표시하고, 인접한 노드 중 unvisited 노드가 존재하면 노드로 향한다. (즉, leaf 노드에 도달하는 것과 같음) 2번을 반복 unvisited인 이웃 노드가 존재하지 않는 동안 직전 노드로 돌아간다. 2번을 반복 출발 노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. 자세하게 설명하면, 1에서 시작해 unvisited인 노드 중 3을 방문한다. 다음, 3과 인접한 노드 중 unvisited 노드 7을 방문한다. 7과 인접한 노드 중 unvisited 노드 8을 방문한다. 8과 인접한 unvisited인 이웃노드가 존재하지 않기 때문에 이전 노드인 7로 돌아간다. 노드 7 또한 unvisited인 이웃노드가 없으므로..
1. 그래프 순회(Graph Traversal) 순회란 ? 그래프의 모든 노드를 방문하는 일 BFS(너비우선순회) DFS(깊이우선순회) 1) BFS L0 = {s} (s : 출발노드) L1 = L0의 모든 이웃 노드 L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 . . Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 의 순서로 노드를 방문한다. 👉 level-order travasal 방식 - 큐를 이용한 너비우선순회 ① s가 1인 노드부터 순회를 시작, 방문한 노드임을 체크 후 큐에 넣음 ② 1을 큐에서 제거한 후 인접노드인 2, 3을 큐에 삽입 ③ 2를 큐에서 제거한 후 2의 인접노드인 4, 5를 큐에 삽입 ④ 3을 큐에서 제거한 후 3의 인접노드인 7, 8을 큐에 삽입 ⑤ 4를 ..
