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 = int(input())
#arr = list(map(int, input().split()))
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:
# print(lis)
mid = (left+right)//2
if lis[mid] < case:
left = mid + 1
else:
right = mid
lis[right] = case
print(len(lis)-1)
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
minValue = float('inf')
t1 = [] # 스타트팀
# t2 = [] # 링크팀
# 스타트팀 - 링크팀 능력치 최소값 출력
# (1,3,6) (2,4,5) -> 13,31,16,61,36,63
def calculator(combList):
total = 0
for x in range(len(combList)):
a = combList[x][0]-1
b = combList[x][1]-1
total += (arr[a][b] + arr[b][a])
return total
def dfs(start):
global minValue
if len(t1) == n//2:
t2 = []
diff = 0
for i in range(1, n+1):
if i not in t1:
t2.append(i)
combList1 = list(comb(t1, 2))
combList2 = list(comb(t2, 2))
total1 = calculator(combList1)
total2 = calculator(combList2)
diff = abs(total1 - total2)
if minValue > diff:
minValue = diff
else:
for idx in range(start, n+1):
if idx not in t1:
t1.append(idx)
dfs(idx)
t1.pop()
dfs(1)
print(minValue)
n, m = map(int, input().split())
arr = list(map(int, input().split()))
maxValue = 0
stack = []
def dfs():
global maxValue
if len(stack) == 3: # 3장의 카드
total = 0
for value in stack: # 카드의 합 구하기
total += arr[value]
if maxValue < total and total <= m: # m의 수를 넘지 않으면서, 최대값 구하기
maxValue = total
else:
for idx in range(n):
if idx not in stack:
stack.append(idx)
dfs()
stack.pop()
dfs()
print(maxValue)
n = int(input())
arr = list(map(int, input().split()))
s = []
maxValue = 0
def dfs():
global maxValue
if len(s) == n: # 리스트에 저장된 정수의 개수가 n 일때
total = 0
for x in range(1, n): # 최대값을 구해준다
total += abs(arr[s[x-1]] - arr[s[x]])
maxValue = max(maxValue, total)
else:
for idx in range(n): # idx 0부터 ~ n까지 (값 중복 가능)
if idx not in s:
s.append(idx)
dfs()
s.pop()
dfs()
print(maxValue)
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)