sh1mj1_log

플로이드-워셜(Floyd-warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 아래와 같습니다. 기능 특징 시간 복잡도 (V: 노드 수) 모든 노드 간에 최단 경로 탐색 ▪️ 음수 가중치 에지가 있어도 수행할 수 있음. ▪️ 동적 계획법의 원리를 이용해서 알고리즘에 접근 O(V³) 플로이드-워셜의 핵심 이론 플로이드-워셜 알고리즘을 도출하는 가장 핵심적인 원리는 A 노드에서 B 노드까지의 최단 경로 'X'를 구했다고 가정했을 때 그 최단 경로 'X' 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것입니다. 위에 빨간색 경로가 노드 1 에서 노드 5로 가는 최단경로라고 합시다. 그렇다면 1 -> 4 최단 경로와 4 -> 5 의 최단 경로도 빨간색 경..

MySQL 로 배우는 데이터베이스 개론과 실습 (- 박우창, 남송휘, 이현룡 지음) 교재의 Chapter 별 요약입니다. 양이 많아서 요약과 연습문제를 나눴습니다. CH03 데이터베이스 프로그래머 MYSQL MySQL 은 세계에서 가장 많이 쓰이는 오픈소스의 관계형 데이터베이스 관리 시스템(RDBMS)임. 스웨덴 MySQL AB 사에서 만들어지고 썬 마이크로시스템즈에 10억 달러에 인수되고 썬 마이크로시스템즈가 오라클에 인수되며 같이 넘어갔다. SQL SQL(Structured Query Language)은 1970년대 후반 IBM이 SEQUEL(Structured English QUEry Language) 라는 이름으로 개발한 관계형 데이터베이스 언어이다. 데이터 정의어(DLL: Data Definit..

MySQL 90년대 중반에 개발된 MySQL 은 최초의 오픈 DB중 하나이며 가장 널리 사용되고 있습니다. 역사가 깊은 만큼 성능과 신뢰성 등에서 꾸준히 개선되어 왔습니다. 또한 MySQL은 오픈 소스이며, 다중 사용자와 다중 스레드를 지원하고 C언어, C++, JAVA, PHP 등 여러 프로그래밍 언어를 위한 다양한 API를 제공합니다. MySQL은 유닉스, 리눅스, 윈도우 등 다양한 운영체제에서 사용할 수 있지만 상업적으로 사용할 때는 상업용 라이센스를 구입해야만 합니다. MariaDB 2010년 MySQL의 썬마이크로시스템즈이 오라클에 합병되면서 많은 MySQL 개발자들은 썬마이크로시스템즈을 떠나며 본인만의 프로젝트를 진행하게 됩니다. 이 중 MySQL의 창시자인 몬티 와이드니어가 만든 프로젝트가 ..

MySQL 로 배우는 데이터베이스 개론과 실습 (- 박우창, 남송휘, 이현룡 지음) 교재의 Chapter 별 요약과 연습문제입니다. 연습문제 해답은 하단에 있습니다. 오답이 있다면 거리낌없이 지적해주세요! CH02 데이터 베이스 시스템의 개념 요약 릴레이션(relation) 관계 데이터 모델의 핵심적인 개념으로 행과 열로 구성된 테이블. 릴레이션 스키마 관계 데이터베이스의 릴레이션이 어떻게 구성되는지 어떤 정보를 담고 있는지에 대한 기본적인 구조를 정의. 테이블에서 스키마는 테이블의 첫 행인 헤더(header)에 나타나며 각 데이터의 속성, 자료 타입 등의 정보를 담고 있다. 릴레이션 인스턴스 릴레이션 스키마실제로 저장되어 있는 데이터의 집합. 관계 데이터베이스 시스템 관계 데이터 모델을 컴퓨터 시스템에..

벨만-포드(bellman-ford moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘입니다. 기능 특징 시간 복잡도 (V: 노드 수, E: 에지 수) 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 - 음수 가중치 에지가 있어도 수행할 수 있음. - 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음. O(VE) 벨만 - 포드의 핵심 이론 아래 3가지 단계로 동작합니다. 1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화. 벨만-포드 알고리즘은 에지를 중심으로 동작하여 에지 리스트로 구현합니다. 다익스트라와 똑같이 출발 노드는 0, 다른 노드들은 ∞ 로 초기화합니다. 아래 그래프의 예에서 출발 노드는 1로 하여 벨만-포드 알고리즘을 진행해보겠습니다. 2. 모든 에지를 ..

메시지와 인터페이스 객체 지향 애플리케이션의 가장 중요한 재료는 클래스가 아닌 객체들이 주고받는 메시지입니다. 객체를 수신하는 메시지들이 객체의 퍼블릭 인테페이스를 구성합니다. 책임 주도 설계 방법 + 좋은 퍼블릭 인터페이스를 얻기 위한 설계 원칙과 기법을 익히고 적용해야 합니다. 협력과 메시지 클라이언트 - 서버 모델 두 객체 사이의 협력 관계를 설명할 때 전통적으로 클라이언트 - 서버(Client - Server) 모델 을 사용합니다. 메시지를 전송하는 객체가 클라이언트, 수신하는 객체가 서버입니다. 클라이언트가 서버의 서비스를 요청하는 단방향 상호작용이죠 위 그림에서 클라이언트 Screening 이 가격을 계산하라 메시지를 전송하여 도움을 요청하고 서버 Movie 는 가격을 계산하는 서비스를 제공하..

다익스트라(dijkstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로, 주요 특징은 아래와 같습니다. 기능 특징 시간 복잡도 (V: 노드 수, E: 에지 수) 출발 노드와 모든 노드 간의 최단 거리 탐색 에지는 모두 양수여야 함. O(ElogV) 다익스트라 최단 경로 알고리즘은 기본적으로 '그리디 알고리즘'으로 분류됩니다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문입니다. 다익스트라 알고리즘 핵심 이론 아래 5 단계로 설명됩니다. 1. 인접 리스트로 그래프 구현 그래프가 위와 같을 때 인접리스트가 표현됩니다. 물론 그래프를 인접 행렬로 구현해도 좋지만 시간 복잡도 측면, N 의 크기가 클 것을 대비해서 보통 인접 리스트로 구현됩니다. 2. 최단 거리 배열 초기화 ..

위상정렬(topology sort)은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘입니다. 기능 특징 시간 복잡도(V: 노드 수, E: 에지 수) 노드 간의 순서를 결정함. 사이클이 없어야 함. O(V+E) 위상 정렬에서는 항상 유일한 값으로 정렬되지 않습니다. 또 사이클이 존재하면 노드 간의 순서를 명확히 정의할 수 없어 위상정렬을 적용할 수 없습니다. 아래 구체적인 시나리오를 통해서 단계별로 알아봅시다. 위상 정렬의 원리 1. 그래프에서 진입차수(in-degree) 을 저장합니다. 진입차수는 자기 자신을 가리키는 에지의 개수입니다. 1 에서 2, 3 을 가리키고 있으므로 D[2], D[3] 을 각각 1을 증가하는 식으로 계산하면 진입 차수 배열 D[N] 을 구할 수 있습니다. 2. 진입 차..

유니온 파인드 union-find 는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해서 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘입니다. union 연산 각 노드가 속한 집합을 1개로 합치는 연산입니다. 노드 a, b 가 a ∈ A, b ∈ B 이 때 union(a,b) 는 A ∪ B 을 뜻합니다. find 연산 특정 노드 a 에 관해 a 가 속한 집합의 대표 노드를 반환하는 연산입니다. 노드 a 가 a ∈ A 일 때 find(a) 는 A 집합의 대표 노드를 반환합니다. 유니온 파인드 알고리즘 구현 방법 유니온 파인드 알고리즘 구현 방법을 아래 예를 통해서 알아봅시다. 1. 유니온 파인드는 일반적으로 1차원 배..

https://sh1mj1-log.tistory.com/140 이전 글에서 계속 됩니다. 백준 1707 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1. 문제 분석 노드를 집합 2개로 나눌 때 인접한 노드끼리 같은 집합이 되면 안 됩니다. 즉, 같은 위 그림처럼 인접해있으면 색이 달라야 한다는 의미입니다. 만약 사이클이 발생한다면 이분 그래프가 불가능합니다. 이런 경우를 어떻게 알아낼 수 있을까요? 탐색 매커니즘에서 탐색한 노드..