sh1mj1_log

트리(Tree) 는 노드와 에지로 연결된 그래프의 특수한 형태입니다. 순한 구조(cycle) 이 없고, 1개의 루트 노드가 존재. 루트 노드를 제외한 노드는 단, 1개의 부모 노드를 가짐. 트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따름. 리프노드는 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드) 입니다. 백준 11725 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 분석 주어지는 데이터가 단순히 연결되어 있는 두 노드를 알려 주는 것이므로 데이터 ..

이전 글에서의 다양한 의존성 관리 기법을 원칙 이라는 관점에서 정리해봅시다. https://sh1mj1-log.tistory.com/154 의존성 관리 - 코드로 이해하는 객체지향 잘 설계된 객체지향 App. 은 작고 응집도 높은 객체들로 구성됩니다. 책임이 명확하고 한 가지 일을 잘하는 객체이지요. 이 객체들이 협력을 하는 것입니다. 협력은 하면 필연적으로 의존성이 발 sh1mj1-log.tistory.com 개방-폐쇄 원칙 개방-폐쇄 원칙(Open-Closed Principle, OCP): 소프트웨어 개체(클래스, 모듈, 함수 등)는 확장에 대해 열려 있어야 하고, 수정에 대해서는 닫혀 있어야 한다. 여기서 확장 은 애플리케이션(이하 앱)의 동작의 관점, 수정 은 코드의 관점 을 반영합니다. 확장에 ..

최소신장 트리 최소 신장 트리(Maximum Spanning Tree, MST)란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리입니다. 아래 특징을 가집니다. 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음. N 개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개임. 최소 신장 트리 핵심 이론 1. 그래프 구현(에지 리스트), 유니온 파인드 배열 초기화 최소 신장 트리는 데이터를 노드가 아니라 에지를 중심으로 저장합니다. 그래서 벨만-포드 알고리즘에서처럼 에지 리스트의 형태로 저장해야 합니다. Edge 클래스는 일반적으로 노드 변수 2개, 가중치 변수 1개로 구성됩니다. 사이클 처리를 위한 유니온 파인드 배열도 초..

잘 설계된 객체지향 App. 은 작고 응집도 높은 객체들로 구성됩니다. 책임이 명확하고 한 가지 일을 잘하는 객체이지요. 이 객체들이 협력을 하는 것입니다. 협력은 하면 필연적으로 의존성이 발생합니다. 너무 과한 협력은 과한 의존성을 발생시키므로 결국 '적당히' 가 중요합니다. 충분히 협력적이면서도 유연한 객체르 만들기 위한 의존성 관리에 대한 글입니다. 의존성 변경과 의존성 의존성은 의존하고 있는 대상의 변경에 영향을 받을 수 있는 가능성입니다. 실행 시점 의존성: 의존하는 객체가 정상적으로 동작하기 위해서는 실행 시에 의존 대상 객체가 반드시 존재해야 함. 구현 시점 의존성: 의존 대상 객체가 변경될 경우 의존하는 객체도 함께 변경됨. 위 글만 읽으면 무슨 소리인지 잘 이해가 안되는데, 코드를 통해서..

MySQL 로 배우는 데이터베이스 개론과 실습 (- 박우창, 남송휘, 이현룡 지음) 교재의 연습문제입니다. 오답이 있다면 거리낌없이 지적해주세요! 1. 마당서점의 고객이 요구하는 다음 질문에 대해 SQL 문을 작성하시오. 1. 도서번호가 1인 도서의 이름 SELECT bookname FROM Book WHERE bookid = '1'; 2. 가격이 20,000 원 이상인 도서의 이름 SELECT bookname FROM Book WHERE price >= 20000; 3. 박지성의 총 구매액 -- AND 사용 SELECT SUM(od.saleprice) FROM Orders od WHERE custid = (SELECT custid FROM Customer cs WHERE cs.name = '박지성') ..

프로시저 추상화와 데이터 추상화 프로그래밍 언어의 두가지 추상화 메커니즘은 프로시저 추상화(procedure abstraction) 와 데이터 추상화(data abstraction) 입니다 . 각각 소프트웨어가 무엇을 해야 할지를 추상화하고, 소프트웨어가 무엇을 알아야 하는지를 추상화합니다. 시스템을 분해하는 방법을 결정하려면 프로시저 추상화를 중심으로 할 것인지, 데이터 추상화를 중심으로 할 것인지를 결정해야 합니다. 프로시저 추상화를 중심으로 하면 기능 분해(functional decomposition) == 알고리즘 분해(algorithmic decomposition) 을 하는 것이며, 데이터 추상화를 중심으로 하면 데이터를 중심으로 타입을 추상화(type abstraction) == 추상 데이터 ..

플로이드-워셜(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)에 나타나며 각 데이터의 속성, 자료 타입 등의 정보를 담고 있다. 릴레이션 인스턴스 릴레이션 스키마실제로 저장되어 있는 데이터의 집합. 관계 데이터베이스 시스템 관계 데이터 모델을 컴퓨터 시스템에..