해당 문제는 Floyd Warshall 알고리즘을 사용해 풀 수 있는 문제다. Floyd Warshall 알고리즘은 a에서 b도시로 이동하는 최단 거리를 임의의 도시 c를 경유하는 모든 경우를 고려하여 구하는 알고리즘이다. 즉, 총 도시의 개수가 5개인 경우 1에서 2로 이동하는 최단 거리를 찾을 때 아래 경우를 모두 고려한다. 도시 1에서 도시 1로 이동 후 도시 1에서 도시 2로 이동 도시 1에서 도시 2로 이동 후 도시 2에서 도시 2로 이동 도시 1에서 도시 3로 이동 후 도시 3에서 도시 2로 이동 도시 1에서 도시 4로 이동 후 도시 4에서 도시 2로 이동 도시 1에서 도시 5로 이동 후 도시 5에서 도시 2로 이동 해당 알고리즘은 DP을 활용하여 다음과 같이 구현할 수 있다. import s..
분류 전체보기
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지지만, 높이는 서로 다를 수 있다. 아래는 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이며 색칠된 부분은 가장 넓은 직사각형이다. 위와 같이 가장 넓은 직사각형을 구하기 위해서는 다음과 같은 알고리즘을 적용할 수 있다. 이때 히스토그램의 각 부분(2, 1, 4, 5, 1, 3, 3의 높이를 가지는 객체)를 ‘막대기’라고 부르자. 모든 막대기 중에 가장 낮은 높이의 막대기를 선택한다. (가장 낮은 높이) × (막대기의 개수)를 통해 현재 히스토그램에서 가장 낮은 높이의 직사각형의 넓이를 구한다. 가장 낮은 높이의 막대기를 기준으로 왼쪽과 오른쪽으로 나눈다. 각 부..
11049번: 행렬 곱셈 순서첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같www.acmicpc.net 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 이때 행렬 N개를 곱하는데 필요한 곱셈의 연산 수는 행렬을 곱하는 순서에 따라 따라지게 된다. 즉, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우 A, B를 먼저 곱하거나 B, C를 먼저 곱하는 경우 각각 90번, 126번으로 곱 횟수가 다르다. 이때 행렬 N개의 크기가 주어지고, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값..
데이터 정의어(DDL)은 스키마 객체를 생성, 변경, 제거시 사용한다. 이때 스키마 객체에는 테이블 뿐만 아니라 데이터베이스에서 제공하는 뷰, synonym index 등 다양한 객체들이 포함된다. DDL은 이러한 객체들을 생성, 변경, 제거할 때 사용되게 된다. MySQL Data Type 테이블을 선언할 때 column에 어떤 타입의 데이터를 사용할 지를 지정해야 한다. 따라서 MySQL에서 제공하는 Data Type에 대해 알아둘 필요가 있다. MySQL은 다음과 같은 Data Type을 제공한다. 숫자형 데이터 타입 Type Description Tinyint(M) 1Byte로 정수를 표현하며 부호가 있는 타입과 없는 타입이 존재한다. Smallint(M) 2Byte로 정수를 표현하며 부호가 있는..
Insert 구문 Insert문을 사용하면 원하는 값을 가지는 행을 추가할 수 있다. 이때 테이블명 옆에 원하는 column에 어떠한 값을 넣을지 명시하는 방법이 있고, 그냥 원하는 값만 적는 방식이 있다. 후자의 경우 모든 column의 값을 순서대로 입력해줘야 한다. Ex) Insert into role (role_id, description) values (200, 'CEO'); Ex) Insert into role (role_id) values (201); Ex) insert into role values(200, 'CEO'); 위 예시에서 두 번째 예시와 같이 description에 해당하는 값을 적지 않으면 default로 설정된 값이 들어가게 된다. 단, role_id와 같이 primary ..
이전 2-1에서 살펴봤던 Select구문 관련 함수들은 '단일 함수'로 column의 field 하나당 하나의 결과가 나오는 함수들이다. 오늘 배울 그룹 함수의 경우 하나의 column의 여러 field 값을 가지고 하나의 결과값을 만들어 낸다. 그룹 함수 select 구문에는 다음과 같은 그룹 함수가 존재한다. Function Description COUNT(expr) non-NULL인 row의 숫자 반환 COUNT(Distinct espr, [expr...]) non-NULL인 중복되지 않은 row의 숫자 반환 COUNT(*) row의 숫자 반환 AVG(expr) expr의 평균값 반환 MIN(expr) expr의 최소값 반환 MAX(expr) expr의 최대값 반환 SUM(expr) expr의 합계..
Data Manipulation Language는 모두 동사로 시작하고 아래와 같이 4가지 조작어가 존재한다. select(검색) / insert(등록) / update(수정) / delete(삭제) SELECT 구문 select 구문의 기본형은 다음과 같다. distinct: 중복행을 제거한다. alias: 나타날 칼럼에 대한 다른 이름을 부여한다. Ex) select deptno as '부서 번호', name as '부서 이름' from department; select [distinct] (Column_Name) as [alias] from (Table_Name); 이때 Column Name이 나오는 자리에 *을 사용하여 원하는 테이블의 모든 데이터를 출력할 수도 있다. Column 결합 (Conc..
Table 구성 요소 테이블은 RDBMS의 기본 저장 구조로 한 개 이상의 column과 0개 이상의 row로 구성된다. Column: 위 그림에서 빨간색 부분으로 테이블 상에서 단일 종류의 데이터를 나타낸다. 특정 데이터 타입 및 크기를 가진다. Row: 각 column들의 조합으로 record라고도 불리며 위 그림에서 파란색 부분이 이에 해당된다. 기본키(PK)에 의해 구분되며 기본키는 중복을 허용하지 않고 없어서도 안된다. Field: Row와 Column의 교차점으로 데이터를 포함하며 데이터가 없다면 NULL값을 가진다. 위 그림에서 검은색 부분이 이에 해당된다. Table 목록 확인 현재 데이터베이스에 존재하는 테이블 목록을 확인하려면 아래 명령어를 사용하면 된다. table이 존재하지 않는다면..
