dp = [1]*n
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j]+1)
이분 탐색 이용 - O(nlogn)
# 수열 A가 주어질 때, 가장 긴 증가하는 부분 수열 구하기
n = 6
arr = [10,20,10,30,20,50]
lis = [0]
for case in arr:
if lis[-1] < case:
lis.append(case)
else:
left = 0
right = len(lis)
while left < right:
mid = (left+right)//2
if lis[mid] < case:
left = mid + 1
else:
right = mid
lis[right] = case
print(lis[1:])
n, m = 4, 2
#n, m = map(int, input().split())
s = [] # 수열을 저장하는 리스트
def dfs():
if len(s) == m: # 리스트의 길이가 m개인 경우
print(' '.join(map(str, s))) # 리스트의 모든 숫자들을 출력
return
for i in range(1, n+1): # 1부터 n+1
if i not in s: # 리스트 안에 i(1~4) 가 없으면
s.append(i) # 리스트에 i(1~4) 추가
dfs() # 다음 레벨
s.pop() # 마지막으로 넣었던 i 제거
dfs()
n, m = 4,2
stack = []
def dfs(start):
if len(stack) == m:
# print(stack)
print(' '.join(map(str, stack)))
return
for x in range(1, n+1):
if x not in stack:
stack.append(x)
dfs(start+1)
stack.pop()
dfs(1)
n, m = map(int, input().split())
stack = []
def dfs(start):
if len(stack) == m:
print(' '.join(map(str, stack)))
return
else:
for x in range(start, n+1):
if x not in stack:
stack.append(x)
#print(stack)
dfs(x+1)
stack.pop()
dfs(1)
# n, m = map(int, input().split())
n, m = 4,2
stack = []
def dfs():
if m == len(stack):
print(' '.join(map(str, stack)))
return
for x in range(1, n+1):
stack.append(x)
dfs()
stack.pop()
dfs()
#n, m = map(int, input().split())
s = []
def dfs(start):
if len(s) == m: # 리스트의 길이가 m개인 경우
print(' '.join(map(str, s))) # 리스트의 모든 숫자들을 출력
return
for i in range(start, n+1): # start으로 1,1 2,2, 3,3
s.append(i) # 리스트에 i(1~4) 추가
dfs(i) # 다음 레벨
s.pop() # 마지막으로 넣었던 i 제거
dfs(1)
n, m = map(int, input().split())
# n, m = 4, 2 # n개의 수를 입력받고, m개의 중복없는 수열을 구하기
# arr = [9,8,7,1]
arr = list(map(int, input().split()))
arr = sorted(arr) # 사전순 출력
stack = []
def dfs():
if len(stack) == m:
for idx in stack:
print(arr[idx], end=' ')
print()
return
for x in range(0, n):
if x not in stack:
stack.append(x)
dfs()
stack.pop()
dfs()
#n, m = map(int, input().split())
#arr = list(map(int, input().split()))
n, m = 4, 4
arr = [1231, 1232, 1233, 1234]
arr = sorted(arr)
stack = []
def dfs(start):
if len(stack) == m:
for idx in stack:
print(arr[idx], end=' ')
print()
return
for x in range(start, n):
if x not in stack:
stack.append(x)
dfs(x+1)
stack.pop()
dfs(0)
n, m = map(int, input().split())
arr = list(map(int, input().split()))
#n, m = 4, 2
#arr = [9,8,7,1]
arr = sorted(arr) # 사전순 출력
stack = []
def dfs(start):
if len(stack) == m:
for idx in stack:
print(arr[idx], end=' ')
print()
return
for x in range(0, n):
# 중복 상관 X
stack.append(x)
dfs(start+1)
stack.pop()
dfs(0)
#n, m = map(int, input().split())
#arr = list(map(int, input().split()))
n, m = 4, 2
arr = [9,7,9,1]
arr = sorted(arr)
visited = [False]*n # 사용한 원소 체크
stack = []
answer = []
def dfs(v):
if len(stack) == m:
answer.append(tuple(stack))
return
for x in range(0, n):
if visited[x]:
continue
stack.append(arr[x])
visited[x] = True # 사용
dfs(v+1)
visited[x] = False # 사용끝
stack.pop()
dfs(0)
# 오름차순, set 중복제거
for x in sorted(list(set(answer))):
print(*x) # 튜플 출력
#n, m = map(int, input().split())
#arr = list(map(int, input().split()))
n, m = 4, 2
arr = [9,7,9,1]
arr = sorted(arr)
stack =[]
def dfs(v):
if len(stack) == m:
print(*stack)
return
prev = 0
for x in range(v, n):
if prev != arr[x]:
stack.append(arr[x])
prev = arr[x]
dfs(x)
stack.pop()
dfs(0)
6603번 로또
def dfs(stack, numbers, start, k):
if len(stack) == 6:
print(' '.join(map(str, stack)))
return
for x in range(start, len(numbers)):
dfs(stack + [numbers[x]], numbers, x + 1, k)
while True:
num = list(map(int, input().split()))
if num[0] == 0:
break
k = num[0] # 번호 개수
numbers = sorted(num[1:]) # 번호 리스트
visited = [False] * len(numbers)
dfs([], numbers, 0, k)
print()
1182번 부분수열의합
n, s = map(int, input().split()) # 정수의 개수, 정수 S
numbers = list(map(int, input().split()))
# n, s = 5, 0
# numbers = [-7, -3, -2, 5, 8]
cnt = 0
# 크기가 양수인 부분 수열 중에서 다 더한 값이 S인 경우의 수 구하기
def dfs(idx, cost):
global cnt
if idx >= n: # 인덱스가 정수 개수보다 크면 종료
return
cost += numbers[idx] # 더한값 += 현재 값
if cost == s: # 더한 값이 s면 경우의수 + 1
cnt += 1
dfs(idx + 1, cost) # 현재 원소를 포함하는 경우
dfs(idx + 1, cost - numbers[idx]) # 현재 원소를 포함하지 않는 경우
dfs(0, 0)
print(cnt)
9663번 N-Queen
def adjacent(x):
for i in range(x):
if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
return False
return True
def dfs(x):
global result
if x == n:
result += 1
return
for i in range(n):
if visite[i]:
continue
row[x] = i
if adjacent(x):
visite[i] = True
dfs(x + 1)
visite[i] = False
import sys
# n = int(sys.stdin.readline())
n = 8 # n x n 크기의 체스판
row = [0] * n
visite = [False] * n
result = 0
dfs(0)
print(result)
- DDL(Data Defination Language) : Create, Drop, Alter
- DCL(Data Control Language) : grant, deny
DML vs DDL
- Transaction의 사용 가능 유무
- DML Transaction 영향 O
- DDL Transaction 영향 X
Transaction(트랜잭션)
- 작업의 최소 단위
- 임의로 설정할 수 있는 개념이다.
- 여러 SQL 문장을 하나의 논리적인 단위인 Transaction으로 설정한다.
- 사용 이유 : Transaction 설정시 DBMS가 ACID 보장
- commit(반영) or rollback(무효화)
MySQL Workbench Auto Commit Transactions
- 워크벤치 기능에 쿼리를 할 때마다 자동적으로 트랜잭션해주는 모드가 켜져 있다.
ACID
(1) Atomicity(원자성)
- All or nothing
- 모든 작업이 완료되거나 실행이 아무것도 되지 않아야 한다.
(2) Consistency(일관성) - 트랜잭션이 끝난 후, 결과가 제약조건에 위배 되지 않는 상태(correct state)이 된다.
(3) Isolation(독립성)
- 모든 트랜잭션이 다른 트랜잭션에 독립적이다.
- Thread 동기화 처리와 일치한다.
(4) Durability(지속성)
- 트랜잭션 종료 시, 해당 결과가 2차 저장소에 영구적으로 저장된다.
Ex. 이체 시스템
- A 계좌 SELECT (잔고 확인)
- A 계좌 UPDATE (잔고 수정)
- B 계좌 SELECT (입금 전 금액)
- B 계좌 UPDATE (입금 후 금액)
JOIN
(1) INNER JOIN
- 일반적인 JOIN
(2) OUTER JOIN
- LEFT, RIGHT, FULL
- JOIN 조건을 만족하지 않는 행을 포함한다.
(3) SELFT JOIN
(4) CROSS JOIN
- 일반적으로 많이 사용하지 않는다.
- 더미데이터 생성에 사용
실습 SQL문 정리
-- 평균 구하기 --
SELECT AVG(칼럼명) FROM 테이블명;
-- 사용자별 평균 구매 금액 --
SELECT userID, AVG(칼럼명) FROM 테이블명
GROUP BY userID;
-- 가장 큰 키, 작은 키 회원의 이름과 키 출력 --
SELECT 이름, 키 FROM 테이블명
WHERE 키 = (
SELECT MAX(키 칼럼) FROM 테이블명
)
OR 키 =
(
SELECT MIN(키 칼럼) FROM 테이블명
);
-- 사용자별 총 구매 금액 1000 이상 --
SELECT userID, SUM(구매금액*구매횟수)
FROM 테이블명
GROUP BY userID
HAVING SUM(구매금액*횟수) >= 1000;
-- 트랜잭션 --
SELECT distinct userID FROM 테이블명;
START TRANSACTION -- 트랜젝션의 시작 구문 --
DELETE FROM 테이블명; -- 테이블 삭제 --
DELETE FROM 테이블명 WHERE 칼럼명 = '조건' LIMIT 100; -- 상위 100개만 지우기 --
COMMIT; -- 지금 작업한 내용 데이터베이스에 적용 --
ROLLBACK; -- 무효화 --
연습문제 SQL문 정리
-- FLOOR(AVG(SAL)) : 정수만 출력, 실수 값 버리기 --
SELECT JOB as '직무', FLOOR(AVG(SAL)) as '급여 평균' FROM EMP
WHERE DEPTNO=30
GROUP BY JOB;
-- 칼럼들의 누적 합계 구하기 --
-- FORMAT(금액, '0.000') : 금액 천단위마다 콤마 출력 --
SELECT JOB as '직무명', FORMAT(SUM(SAL), '0,000') as '급여의 합' FROM EMP
GROUP BY JOB
UNION ALL
SELECT 'TOTAL', FORMAT(SUM(SAL), '0,000') FROM EMP
ORDER BY '직무명';
-- CROSS JOIN : 2개 테이블 열 기준으로 붙이기 --
SELECT * FROM A CROSS JOIN B;
-- 1. IFNULL(칼럼명, 0) : NULL 처리 (NULL + 0이상의 값 = NULL이 출력된다) --
-- 2. FORMAT()으로 금액 천단위마다 콤마 + CONCAT()으로 금액 + '원' 출력
SELECT ENAME as '직원명', CONCAT(FORMAT(SAL+IFNULL(COMM, 0), '0,000'),'원') as '급여' FROM EMP
ORDER BY SAL+IFNULL(COMM, 0) DESC;
-- DATE_FROMAT() : DATE 타입 출력 형식 --
-- CASE WHEN ~ THEN : 조건별 표현식 --
SELECT ENAME as '직원명', DATE_FORMAT(HIREDATE, '%Y년 %m월 %d일') as '입사년월일',
(CASE
WHEN HIREDATE BETWEEN '1980-01-01' AND '1980-12-31' THEN 'A'
WHEN HIREDATE BETWEEN '1981-01-01' AND '1981-12-31' THEN 'B'
WHEN HIREDATE BETWEEN '1982-01-01' AND '1982-12-31' THEN 'C'
WHEN HIREDATE BETWEEN '1983-01-01' AND '1983-12-31' THEN 'D'
END) as '등급'
FROM EMP;
-- 3중 조인 --
SELECT * FROM A
INNER JOIN B
ON A.칼럼1 = B.칼럼1
INNER JOIN C
ON B.칼럼2 = C.칼럼2;
