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

DATABASE-Constraint

Oct 26, 2020 in DATABASE, MYSQL, DDL

Constraint : 제약조건

데이터 베이스의 테이블을 생성할때 각 컬럼은 각각의 제약조건을 갖습니다.

NOT NULL

NULL 값 (비어있는 값)을 저장할수 없습니다.
UNIQUE

같은 값을 저장할수 없습니다.
PRIMARY KEY
- NOT NULL과 UNIQUE 의 제약조건을 동시에 만족해야 합니다.
- 그러므로 컬럼에 비어 있는 값과 동일한 값을 저장할수 없습니다.
- 하나의 테이블에 하나의 컬럼만 조건을 설정할수 있습니다.
AUTO_INCREMENT

주로 테이블의 PRIMARY KEY 데이터를 저장할때 자동으로 숫자를 1씩 증가시켜 주는 기능으로 사용합
니다.

FOREIGN KEY

다른 테이블과 연결되는 값이 저장됩니다.

테이블 수정으로 FK 설정

alter table money
add constraint fk_user
foreign key (user_id)       # money의 user_id
references user (user_id);  # user의 user_id

테이블 생성시 FK 설정

create table money(
    money_id int primary key auto_increment,
    income int, 
    user_id int,
    foreign key (user_id) references user(user_id)
);

ON DELETE, ON UPDATE 설정
- 참조를 받는 데이터가 수정하거나 삭제될때 참조 하는 데이터를 설정(수정,삭제 등등)
- CASECADE : 참조 받는 데이터가 수정, 삭제하면, 참조하는 데이터도 수정 삭제
- SET NULL : 참조 받는 데이터가 수정 삭제하면, 참조하는 데이터는 NULL로 수정

DEFAULT

데이터를 저장할때 해당 컬럼에 별도의 저장값이 없으면 DEFAULT로 설정된 값이 저장됩니다.

create table money(
    money_id int primary key auto_increment,
    income int, 
    user_id int,
    foreign key (user_id) references user(user_id)
    on update cascade on delete set null
);

Comment and share

DATABASE-DATA TYPE

Oct 26, 2020 in DATABASE, DDL

DATA TYPE

데이터 베이스의 테이블을 생성할때 각 컬럼은 데이터 타입을 가집니다.

reference : https://dev.mysql.com/doc/refman/5.7/en/data-types.html

Numberic

reference : https://dev.mysql.com/doc/refman/5.7/en/numeric-types.html

정수 타입 ( integer types )
실수 (floating-point types)

소수점을 나타내기 위한 데이터 타입으로 아래의 두가지 데이터 타입이 있습니다.

두가지의 데이터 타입은 데이터 저장공간의 차이가 있습니다.

FLOAT (4byte), DOUBLE (8byte)

또한 아래와 같이 고정 소수점 타입으로도 사용이 가능합니다.

FLOAT(M,D), DOUBLE(M,D)

Date & Time

reference : https://dev.mysql.com/doc/refman/5.7/en/date-and-time-types.html

DATE

DATE는 날짜를 저장하는 데이터 타입이며, 기본 포멧은 “년-월-일” 입니다.
DATETIME

DATETIME은 날짜와 시간을 저장하는 데이터 타입이며, 기본 포멧은 “년-월-일 시:분:초” 입니다.
TIMESTAME

TIMESTAME는 날짜와 시간을 저장하는 데이터 타입이며,

DATETIME과 다른점은 날짜를 입력하지 않으면 현재 날짜와 시간을 자동으로 저장할수 있는 특징이 있습니다.
TIME

TIME은 시간을 저장하는 데이터 타입이며, 기본 포멧은 “시:분:초” 입니다.
YEAR

YEAR는 연도를 저장할수 있는 데이터 타입입니다.

YEAR(2)는 2자리의 연도를 저장할수 있으며 YEAR(4)는 4자리의 연도를 저장할수 있습니다.

String

reference
https://dev.mysql.com/doc/refman/5.7/en/string-types.html

CHAR & VARCHAR

TEXT
- CHAR와 VARCHAR는 대체로 크기가 작은 문자열을 저장할때 사용되며 크기가 큰 문자열을 저장할 때는 TEXT를 사용합니다.
- TEXT의 타입에 따라서 아래와 같이 크기를 가집니다.

Comment and share

DATABASE-DDL

Oct 26, 2020 in DATABASE, DDL

CREATE USE ALTER DROP

USE

test 데이터 베이스 선택
1
USE test;
현재 데이터 베이스 확인
1
SELECT DATABASE()

CREATE

데이터 베이스 생성
1
CREATE DATABASE <database_name>;
test 데이터 베이스 생성
1
CREATE DATABASE test;

테이블 생성

CREATE TABLE <table_name> (
    column_name_1 column_data_type_1 column_constraint_1,
    column_name_2 column_data_type_2 column_constraint_2,
    ...
)

제약조건이 없는 user1 테이블 생성

CREATE TABLE user1(
    user_id INT,
    name Varchar(20),
    email Varchar(30),
    age INT(3),
    rdate DATE
)

제약조건이 있는 user2 테이블 생성

CREATE TABLE user2(
    user_id INT PRIMARY KEY AUTO_INCREMENT,
    name Varchar(20) NOT NULL,
    email Varchar(30) UNIQUE NOT NULL,
    age INT(3) DEFAULT '30',
    rdate TIMESTAMP
)

ALTER

Database

사용중인 데이터베이스의 인코딩 방식 확인
1
SHOW VARIABLES LIKE "character_set_database"

test 데이터 베이스의 문자열 인코딩을 utf8으로 변경

1 2	ALTER DATABASE world CHARACTER SET = ascii ALTER DATABASE world CHARACTER SET = utf8

Table

ALTER를 이용하여 Table의 컬럼을 추가하거나 삭제하거나 수정할수 있습니다.
ADD
- user2 테이블에 TEXT 데이터 타입을 갖는 tmp 컬럼을 추가
  1
  ALTER TABLE user2 ADD tmp TEXT
MODIFY
- user2 테이블에 INT 데이터 타입을 갖는 tmp 컬럼으로 수정
  1
  ALTER TABLE user2 MODIFY COLUMN tmp INT
DROP
- user2 테이블의 tmp 컬럼을 삭제
  1
  ALTER TABLE user2 DROP tmp

DROP

DATABASE

tmp 데이터 베이스 생성
1
2
CREATE DATABASE tmp;
SHOW DATABASES;
tmp 데이터 베이스 삭제
1
2
DROP DATABASE tmp;
SHOW DATABASES;

TABLE
- tmp 데이터 베이스 생성
  1
  CREATE DATABASE tmp;
- tmp 데이터 베이스 선택
  1
  USE tmp;
- tmp 테이블 생성
  1
  CREATE TABLE tmp( id INT );
- tmp 테이블 삭제
  1
  DROP TABLE tmp;

Comment and share

성 지키기

Oct 26, 2020 in Algorithm, Search

백준 1236 : 문제링크

문제유형 :
- 탐색
설명
- 행 기준, 열 기준 중 더 큰 값을 출력한다.

풀이

n, m = map(int, input().split())
array = []

for _ in range(n):
    array.append(input())

row = [0] * n
column = [0] * m

for i in range(n):
    for j in range(m):
        if array[i][j] == 'X':
            row[i] = 1
            column[j] = 1

row_count = 0
for i in range(n):
    if row[i] == 0:
        row_count += 1

column_count = 0
for i in range(m):
    if column[j] == 0:
        column_count +=  1
    
print(max(row_count, column_count))

Comment and share

트로피 진열

Oct 26, 2020 in Algorithm, Search

백준 1668 : 문제링크

문제유형 :
- 탐색
설명
- N의 최대값이 50이기 때문에 단순 구현

풀이

def ascending(array):
    now = array[0]
    result += 1
    for i in range(1, len(array)):
        if now < array[i]:
            result += 1
            now = array[i]
    return result

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

for _ in range(n):
    array.append(int(input()))

print(ascending(array))
array.reverse()
print(ascending(array))

Comment and share

JOIN

MAKE TEST TABLE & DATA

INNER JOIN

LEFT JOIN

RIGHT JOIN

JOIN과 DISDINCT의 사용

테이블 세개 조인하기

UNION

Functions

조건문 IF, IFNULL, CASE

INSERT

UPDATE SET

DELETE, DROP, TRUNCATE

Constraint : 제약조건

DATA TYPE

Numberic

Date & Time

String

CREATE USE ALTER DROP

USE

CREATE

ALTER

Database

Table

DROP

Yechan Kim