Algorithm-문제집

Oct 27, 2020 in Algorithm, Search

문제유형
- 탐색
- 힙
- 위상정렬
설명
- 위상정렬
  1. 진입 차수가 0인 정점을 큐에 삽입
  2. 큐에서 원소를 꺼내 해당 원소와 간선을 제거
  3. 제거 이후 진입 차수가 0이 된 정점을 큐에 삽입
  4. 큐가 빌 때까지 2 ~ 3을 반복
- 위상정렬 사용이유 : 2번 조건 - 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.)
- 힙 사용이유 : 3번 조건 - 가능하면 쉬운 문제부터 풀어야 한다

풀이

import heapq

n, m = map(int, input().split())
array = [[] for i in range(n + 1)]
indegree = [0] * (n + 1)

heap = []
result = []

for _ in range(m):
    x, y = map(int, input().split())
    array[x].append(y)
    indegree[y] += 1

for i in range(n+1):
    if indegree[i] == 0:
        heapq.heappush(heap, i)
    
result = []

while heap:
    data = heapq.heappop(heap)
    result.append(data)
    for y in array[data]:
        indegree[y] -= 1
        if indegree[y] == 0:
            heapq.heappuh(heap, y)

for i in result:
    print(i, end = ' ')

Comment and share

Algorithm-카드 정렬하기

Oct 27, 2020 in Algorithm, Search

백준 1715 : 문제링크

문제유형 :
- 탐색
- 힙
- 그리디
설명
- 가장 작은 숫자의 카드 묶음을 먼저 합쳤을 때 최소값
- heap을 사용해서 작은 값 두개를 pop한다
- 추출한 두 개의 값을 합해서 결과에 더한다
- 합한 값을 다시 heap에 push한다
- heap에 값이 한 개 남았을 때 종료한다

풀이

import heapq

n = int(input())
heap = []

for i in range(n):
    data = int(input())
    heaq.heappush(heapq, data)

result = 0

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    sum_value = one + two
    result += sum_value
    heapq.heappush(heap, sum_value)

print(result)

Comment and share

DATABASE-VIEW INDEX TRIGGER

Oct 27, 2020 in DATABASE, DDL

VIEW

Explain

가상 테이블로 일부분만 데이터로 보고자 할때 사용합니다.
실제 데이터를 저장하고 있지는 않습니다.
한마디로 특정 컬럼의 데이터를 보여주는 역할만 합니다.
뷰를 사용함으로 쿼리를 더 단순하게 만들수 있습니다.
한번 생성된 뷰는 수정이 불가능 하며 인덱스설정이 불가능 합니다.

Syntax

1	CREATE VIEW <뷰이름> AS (QUERY)

Example

국가코드와 국가이름이 있는 뷰

1
2
3

CREATE VIEW code_name AS
SELECT code, name
FROM country

city 테이블에 국가 이름 추가

SELECT *
FROM city
JOIN code_name
ON city.countrycode = code_name.code

INDEX

Explain

정의 : 테이블에서 데이터를 검색할때 빠르게 찾을수 있도록 해주는 기능입니다.
장점 : 검색속도가 빨라짐
단점 : 저장공간을 10% 정도 더 많이 차지 INSERT, DELETE, UPDATE 할때 속도가 느려짐
사용법 : SELECT시 WHERE 절에 들어가는 컬럼을 Index로 설정하면 좋다.
내부 작동 원리 (B-Tree)
- 루트노드와 리프노드의 계층적 구조로 루트노드를 이용하여 리프노드에서의 데이터를 빠르게 찾을수 있는 자료구조 알고리즘.

Syntax

1	CREATE INDEX <인덱스 이름> AS <테이블 이름(필드 이름)>

Example

employees 데이터 베이스에서 실행

실행계획을 확인하여 인덱스를 사용하는지 확인

EXPLAIN
SELECT *
FROM salaries
WHERE from_date < "1986-01-01"

EXPLAIN
SELECT *
FROM salaries
WHERE to_date < "1986-01-01"

인덱스 확인
1
SHOW INDEX FROM salaries;

인덱스 생성

CREATE INDEX fdate
ON salaries (from_date)

CREATE INDEX tdate
ON salaries (to_date)

여러개의 컬럼을 가지는 인덱스 생성도 가능
1
2
CREATE INDEX ftdate
ON salaries (from_date, to_date)

인덱스 삭제

DROP INDEX fdate
ON salaries

DROP INDEX tdate
ON salaries

DROP INDEX ftdate
ON salaries

여러개의 컬럼을 조건으로 WHERE절에 사용하는 경우 인덱스 확인

인덱스가 하나의 컬럼에 있을때 보다 둘다 있을때가 더 빠름

EXPLAIN
SELECT *
FROM salaries
WHERE from_date < "1986-01-01" AND to_date < "1986-01-01"

TRIGGER

정의 : 특정 테이블을 감시하고 있다가 설정된 조건의 쿼리가 실행되면 미리 지정한 쿼리가 자동으로 실행되도록하는 방법

Syntax

create trigger {trigger name}
{before | after} {insert | update |delete}
on <table name> for each row
begin
    <excute query>
end

Example

database 생성

create table data1 (
    id varchar(20),
    msg varchar(50) not null
);

create table data_backup (
    id varchar(20),
    msg varchar(50) not null
);

Trigger 생성

create trigger backup
before delete on data1
for each row 
begin
    insert into data_backup(id, msg)
    values(old.id, old.msg);
end

Comment and share

DATABASE-Sub Query

Oct 27, 2020 in DATABASE, DML

Sub Query

sub query는 query 문 안에 있는 query를 의미합니다.

SELECT절, FROM절, WHERE 등에 사용이 가능합니다.

Example

전체 나라수, 전체 도시수, 전체 언어수를 출력 ( SELECT 절에 사용 )

`SUB QUERY 사용시 JOIN TABLE 크기를 줄일 수 있다`

SELECT
    (SELECT count(name) FROM city) AS total_city,
    (SELECT count(name) FROM country) AS total_country,
    (SELECT count(DISTINCT(Language)) FROM countrylanguage) AS total_language
FROM DUAL

800만 이상되는 도시의 국가코드, 이름, 도시인구수를 출력 ( FROM 절에 사용 )

SUB QUERY를 안 쓸때

city table row : 4079
coutnry table row : 239

JOIN TABLE : 4079 * 239

SELECT *
FROM
    city
JOIN
    (SELECT code, name
    FROM country) AS country
ON city.countrycode = country.code
HAVING city.population > 8000000;

SUB QUERY를 쓸 때

city table row : 10
coutnry table row : 239

JOIN TABLE : 10 * 239

SELECT *
FROM
    (SELECT countrycode, name, population
    FROM city
    WHERE population > 8000000) AS city
JOIN
    (SELECT code, name
    FROM country) AS country
ON city.countrycode = country.code;

800만 이상 도시의 국가코드, 국가이름, 대통령이름을 출력( WHERE 절에 사용 )

SELECT code, name, HeadOfState
FROM country
WHERE code IN (
    SELECT DISTINCT(countrycode) FROM city WHERE population > 8000000
)

Comment and share

Algorithm-최소 힙

Oct 27, 2020 in Algorithm, Search

백준 1927 : 문제링크

문제유형 :
- 탐색
- 힙
설명
- 파이썬에서 heapq 라이브러리를 이용하면 힙 구현 가능하다.

풀이

import heapq

n = int(input())
heap = []
result = []

for _ in range(n):
    data = int(input())
    if data = 0:
        if heap:
            result.append(heapq.heappop(heap))
        else:
            result.append(0)
    else:
        heapq.heappush(heap, data)

for data in result:
    print(data)

Comment and share

Algorithm-중량제한

Oct 27, 2020 in Algorithm, Search, Binary Search

백준 1939 : 문제링크

문제유형 :
- 탐색
- 이진탐색
- BFS
설명
- 다리의 개수 M의 최대 100,000, 중량 제한 C는 최대 1,000,000,000
- 이진탐색을 이용하면 시간 복잡도는 O(M * logC)
- DFS로 도착지에 옮길 수 있는 지 확인
- 한 번에 옮길 수 있는 물품의 최대값을 이진탐색으로 찾아낸다.

풀이

from collections import deque

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]

def bfs(c):
    queue = deque([start_node])
    visited = [False] * (n + 1)
    visited[start_node] = True
    while queue:
        x = queue.popleft()
        for y, weight in adj[x]:
            if not visited[y] and weight >= c:
                visited[y] = True
                queue.append(y)
    return visited[end_node]

start = 1000000000
end = 1

for _ in range(m):
    x, y, weight = map(int, input().split())
    adj[x].append((y, weight))
    adj[y].append((x, weight))
    start = min(start, weight)
    end = max(end, weight)

start_node, end_node = map(int, input().split())

result = start
while(start <= end):
    mid = (start + end) // 2
    if bfs(mid):
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

Comment and share

Algorithm-공유기 설치

Oct 27, 2020 in Algorithm, Search, Binary Search

백준 2110 : 문제링크

문제유형 :
- 탐색
- 이진탐색
설명
- 집의 개수 N의 최대는 200,000 이고 집의 좌표 X의 최대 1,000,000,000이다
- 이진탐색을 이용하면 시간 복잡도는 O(N * logX)
- 집 간 거리 Gap에 대해서 이진탐색을 한다.

풀이

n, c = list(map(int, input().split(' ')))`

array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)

start = array[1] - array[0]
end = array[-1] - array[0]
result = 0

while(start <= end):    // 시간 복잡도 : O(logX)
    mid = (start + end) // 2
    value = array[0]
    count = 1
    for i in range(1, len(array)): // 시간 복잡도 : O(N)
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

Comment and share

DATABASE-JOIN UNION

Oct 26, 2020 in DATABASE, DML

JOIN

JOIN은 여러개의 테이블에서 데이터를 모아서 보여줄 때 사용됩니다.
JOIN에는 INNER JOIN, LEFT JOIN, RIGHT JOIN이 있습니다.

MAKE TEST TABLE & DATA

create table & data

CREATE TABLE user (
    user_id int(11) unsigned NOT NULL AUTO_INCREMENT,
    name varchar(30) DEFAULT NULL,
    PRIMARY KEY (user_id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE addr (
    id int(11) unsigned NOT NULL AUTO_INCREMENT,
    addr varchar(30) DEFAULT NULL,
    user_id int(11) DEFAULT NULL,
    PRIMARY KEY (id)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO user(name)
VALUES ("jin"),
("po"),
("alice"),
("petter");

INSERT INTO addr(addr, user_id)
VALUES ("seoul", 1),
("pusan", 2),
("deajeon", 3),
("deagu", 5),
("seoul", 6);

INNER JOIN

두 테이블 사이에 공통된 값이 없는 row는 출력하지 않는다.

두 테이블을 합쳐 id, name, addr 출력

SELECT id, user.name, addr.addr
FROM user
JOIN addr
ON user.user_id = addr.user_id

world 데이터베이스에서 도시이름과 국가이름을 출력

SELECT city.name AS country_name, country.name AS city_name
FROM city
JOIN country
ON city.CountryCode = country.code

아래와 같이 사용할수도 있다.

1
2
3

SELECT city.name AS country_name, country.name AS city_name
FROM city, country
WHERE city.CountryCode = country.code

LEFT JOIN

왼쪽 테이블을 기준으로 왼쪽 테이블의 모든 데이터가 출력되고 매핑되는 키값이 없으면 NULL로 출력된다.

두 테이블을 합쳐 id, name, addr 출력

SELECT id, user.name, addr.addr
FROM user
LEFT JOIN addr
ON user.user_id = addr.user_id

RIGHT JOIN

오른쪽 테이블을 기준으로 왼쪽 테이블의 모든 데이터가 출력되고 매핑되는 키값이 없으면 NULL로 출력된다.

두 테이블을 합쳐 id, name, addr 출력

SELECT id, user.name, addr.addr
FROM user
RIGHT JOIN addr
ON user.user_id = addr.user_id

JOIN과 DISDINCT의 사용

지역과 대륙별 사용하는 언어 출력

SELECT DISTINCT country.Region, country.continent, countrylanguage.Language
FROM country
JOIN countrylanguage
ON countrylanguage.CountryCode = country.Code

대륙과 지역별 사용하는 언어의 수 출력

SELECT sub1.region, sub1.continent, count(*) as count
FROM (
SELECT DISTINCT country.Region, country.continent, countrylanguage.Language
FROM country
JOIN countrylanguage
ON countrylanguage.CountryCode = country.Code
) AS sub1
GROUP BY sub1.region, sub1.continent

테이블 세개 조인하기

국가별, 도시별, 언어의 사용율

SELECT country.name as country_name, city.name as city_name,
countrylanguage.language, countrylanguage.percentage
FROM country
JOIN city
ON country.code = city.countrycode
JOIN countrylanguage
ON country.code = countrylanguage.countrycode

SELECT country.name as country_name, city.name as city_name,
countrylanguage.language, countrylanguage.percentage
FROM country, city, countrylanguage
WHERE country.code = city.countrycode and country.code = countrylanguage.countrycode

UNION

UNION은 SELECT 문의 결과 데이터를 하나로 합쳐서 출력합니다.

컬럼의 갯수와 타입, 순서가 같아야 합니다.

UNION은 자동으로 distinct를 하여 중복을 제거해 줍니다.

중복제거를 안하고 컬럼 데이터를 합치고 싶으면 UNION ALL을 사용합니다.

또한 UNION을 이용하면 Full Outer Join을 구현할수 있습니다.

UNION
- user 테이블의 name 컬럼과 addr 테이블의 addr 컬럼의 데이터를 하나로 함쳐서 출력
  1
  2
  3
  4
  5
  SELECT name
  FROM user
  UNION
  SELECT addr
  FROM addr
UNION ALL
- 중복데이터를 제거하지 않고 결과 데이터 합쳐서 출력
  1
  2
  3
  4
  5
  SELECT name
  FROM user
  UNION ALL
  SELECT addr
  FROM addr

FULL OUTER JOIN

union을 이용하여 full outer join 구현

SELECT id, user.name, addr.addr
FROM user
LEFT JOIN addr
ON user.user_id = addr.user_id
UNION
SELECT id, user.name, addr.addr
FROM user
RIGHT JOIN addr
ON user.user_id = addr.user_id

Comment and share

DATABASE-Function

Oct 26, 2020 in DATABASE

Functions

CEIL, ROUND, TRUNCATE는 소수점 올림, 반올림, 버림 함수입니다.
- CEIL
  
  CEIL는 실수 데이터를 올림 할 때 사용합니다.
- 12.345를 올림하여 정수로 나타냄
  1
  SELECT CEIL(12.345)
- 국가별 언어 사용 비율을 소수 첫번째자리에서 올림하여 정수로 나타냄
  1
  2
  SELECT CountryCode, Language, Percentage, CEIL(Percentage)
  FROM countrylanguage
- ROUND
  
  ROUND는 실수데이터를 반올림 할 때 사용합니다.
  - 12.345를 소수 둘째자리까지 나타내고 소수 셋째자리에서 반올림
    1
    SELECT ROUND(12.345, 2)
  - 국가별 언어 사용 비율을 소수 첫번째자리에서 반올림하여 정수로 나타냄
    1
    2
    SELECT CountryCode, Language, Percentage, ROUND(Percentage, 0)
    FROM countrylanguage
- TRUNCATE
  
  TRUNCATE는 실수 데이터를 버림 할 때 사용합니다.
  - 12.345를 소수 둘째자리까지 나타내고 소수 셋째자리에서 버림
    1
    SELECT TRUNCATE(12.345, 2)
  - 국가별 언어 사용 비율을 소수 첫번째자리에서 버림하여 정수로 나타냄
    1
    2
    SELECT CountryCode, Language, Percentage, TRUNCATE(Percentage, 0)
    FROM countrylanguage
    1
    2
    3
    SELECT CountryCode, Language, Percentage, ROUND(Percentage, 0),
    TRUNCATE(Percentage, 0)
    FROM countrylanguage
DATE_FORMAT

DATE_FORMAT은 날짜 데이터에 대한 포멧을 바꿔줍니다.

https://dev.mysql.com/doc/refman/5.7/en/date-and-time-functions.html
- sakila 데이터 베이스에서 월별 총 수입
  1
  2
  3
  SELECT DATE_FORMAT(payment_date, "%Y-%m") AS monthly, SUM(amount) AS amount
  FROM payment
  GROUP BY monthly

조건문 IF, IFNULL, CASE

SQL에서도 다른 언어에서 처럼 조건문 사용이 가능합니다. IF, CASE 에 대해서 설명합니다.
IF(조건, 참, 거짓)

- 도시의 인구가 100만이 넘으면 "big city" 그렇지 않으면 "small city"를 출력하는 city_scale 컬럼을 추가
    <!--hexoPostRenderEscape:<figure class="highlight sql"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">SELECT</span> <span class="keyword">name</span>, population, <span class="keyword">IF</span>(population &gt; <span class="number">1000000</span>, <span class="string">&quot;big city&quot;</span>, <span class="string">&quot;small city&quot;</span>) <span class="keyword">AS</span> city_scale</span><br><span class="line"><span class="keyword">FROM</span> city</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

IFNULL(참, 거짓)

독립년도가 없는 데이터는 0으로 출력

1 2	SELECT IndepYear, IFNULL(IndepYear, 0) as IndepYear FROM country

CASE

CASE 
WHEN (조건1) THEN (출력1)
WHEN (조건2) THEN (출력2)
END AS (컬럼명)

나라별로 인구가 10억 이상, 1억 이상, 1억 이하인 컬럼을 추가하여 출력

SELECT name, population,
CASE
WHEN population > 1000000000 THEN "upper 1 bilion"
WHEN population > 100000000 THEN "upper 100 milion"
ELSE "below 100 milion"
END AS result
FROM country

Comment and share

DATABASE-DML-INSERT UPDATE DELETE

Oct 26, 2020 in DATABASE, DML

INSERT

테이블 이름 뒤에 오는 컬럼이름은 생략이 가능하며 대신에 VALUES 뒤에 value 값이 순서대로 와야 합니다.
1
2
INSERT INTO <table_name>(<column_name_1>, <column_name_2>, ...)
VALUES(<value_1>, <value_2>, ...)
test 데이터 베이스 선택
1
sql> USE test;

user1 테이블에 user_id, name, email, age, rdate를 입력

INSERT INTO user1(user_id, name, email, age, rdate)
VALUES (1, "jin", "pdj@gmail.com", 30, now()),
(2, "peter", "peter@daum.net", 33, '2017-02-20'),
(3, "alice", "alice@naver.com", 23, '2018-01-05'),
(4, "po", "po@gmail.com", 43, '2002-09-16'),
(5, "andy", "andy@gmail.com", 17, '2016-04-28'),
(6, "jin", "jin1224@gmail.com", 33, '2013-09-02');

city_2 테이블 생성

CREATE TABLE city_2 (
    Name VARCHAR(50),
    CountryCode CHAR(3),
    District VARCHAR(50),
    Population INT
)

select 절에서 나온 결과데이터를 Insert

INSERT INTO city_2
SELECT Name, CountryCode, District, Population
FROM city
WHERE Population > 8000000;

UPDATE SET

업데이트시에는 항상 select-where로 변경할 데이터를 확인하고 update 해줘야 실수를 줄일수 있습니다. 또한 limit도 함께 사용해주면 좋습니다.

1
2
3

UPDATE <table_name>
SET <column_name_1> = <value_1>, <column_name_2> = <value_2>
WHERE <condition>

jin 이름을 가지고 있는 사람의 나이를 20, 이메일을 pdj@daum.net으로 변경
1
2
3
sql> UPDATE user1
SET age=20, email="pdj@daum.net"
WHERE name="jin"

DELETE, DROP, TRUNCATE

조건을 설정하여 데이터를 삭제할수 있습니다.

1 2	DELETE FROM <table_name> WHERE <condition>

2016-01-01 이전 데이터 삭제 (DML)

1 2	sql> DELETE FROM user1 WHERE rdate < "2016-01-01"

테이블 구조를 남기고 모든 데이터를 삭제 (DLL)
1
sql> TRUNCATE FROM user1
테이블 전체를 모두 삭제 (DLL)
1
sql> DROP FROM user1

Comment and share

VIEW

Explain

Syntax

Example

INDEX

Explain

Syntax

Example

TRIGGER

Syntax

Example

Sub Query

Example

SUB QUERY 사용시 JOIN TABLE 크기를 줄일 수 있다

JOIN

MAKE TEST TABLE & DATA

INNER JOIN

LEFT JOIN

RIGHT JOIN

JOIN과 DISDINCT의 사용

테이블 세개 조인하기

UNION

Functions

조건문 IF, IFNULL, CASE

INSERT

UPDATE SET

DELETE, DROP, TRUNCATE

Yechan Kim

`SUB QUERY 사용시 JOIN TABLE 크기를 줄일 수 있다`