희연's 개발 일기장

https://www.acmicpc.net/problem/11053

LIS 알고리즘 - DP

https://hhiyeon.tistory.com/167

백준 풀이

#n = 6
#arr = [10,20,10,30,20,50]
n = int(input())
arr = list(map(int, input().split()))
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)

# print(dp)
# 1 2 1 3 2 4
# 10의 길이 1, 20의 길이 2, 10의 길이 ...
print(max(dp))

https://www.acmicpc.net/problem/12015

LIS 알고리즘 정리

https://hhiyeon.tistory.com/167

백준 풀이

#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)

https://www.acmicpc.net/problem/10815

import sys
n = int(input())
cNum = list(map(int, sys.stdin.readline().split()))
m = int(input())
card = list(map(int, sys.stdin.readline().split()))
cNum = sorted(cNum)
answer = ''

for num in card:
    lt = 0
    rt = n - 1
    flag = 0
    while lt <= rt:
        mid = (lt + rt) // 2
        if cNum[mid] < num:
            lt = mid +1
        elif cNum[mid] == num:
            flag = 1
            break
        else:
            # cNum[lt] > num
            rt = mid -1
    answer += str(flag) + ' '
print(answer[:-1])

https://www.acmicpc.net/problem/14888

n = 3
op = [3,4,5] # 주어진 수열 - 순서 바꾸기 X
add, sub, mul, div = 1, 0, 1, 0  # 덧셈 뺄셈 곱셈 나눗셈 개수
#n = int(input())
#op = list(map(int, input().split()))
#add, sub, mul, div = map(int, input().split())
minValue = float('inf')
maxValue = float('-inf')

def dfs(i, arr):
    global minValue, maxValue, add, sub, mul, div
    if i == n:
        # 최대값 최소값 구하기
        maxValue = max(maxValue, arr)
        minValue = min(minValue, arr)
    else:
        if add > 0:
            add -= 1
            dfs(i+1, arr+op[i])
            add += 1
        if sub > 0:
            sub -= 1
            dfs(i+1, arr-op[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i+1, arr*op[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i+1, int(arr/op[i]))
            div += 1

dfs(1, op[0])
print(maxValue)
print(minValue)

https://www.acmicpc.net/problem/14889

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)

https://www.acmicpc.net/problem/2798

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)

https://www.acmicpc.net/problem/10819

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)

def divStr(p): # 문자열 u,v 분리
    leftCnt = 0
    rightCnt = 0
    
    for x in range(len(p)):
        if p[x]=='(':
            leftCnt += 1
        if p[x]==')':
            rightCnt += 1

        if leftCnt == rightCnt:
            return p[:x+1], p[x+1:] # u, v
    
def checkStr(u): # 올바른 괄호 문자열인지 체크
    stack = []
    for x in u:
        if x == '(':
            stack.append(x)
        else:
            if not stack:
                return False
            stack.pop()
    return True

def solution(p):
    answer = ''
    
    # 1번 - 빈 문자열이면 빈 문자열 반환
    if not p:
        return ""
        
    # 2번 - u, v으로 분리
    u, v = divStr(p)
    
    # 3번 - u가 올바른 문자열이면 v에 대해 1단계부터 수행
    # 수행한 결과 문자열을 u에 이어 붙이고 반환한다.
    if checkStr(u):
        return u + solution(v)
    else:
        # 4번 - u가 올바르지 않은 문자열인 경우
        # 4-1번 빈 문자열에 첫 번째 문자로 '(' 붙이기
        answer = '('
        
        # 4-2번 문자열 v에 대해 1단계부터 재귀적으로 수행하고 결과를 이어 붙이기
        answer += solution(v)
        
        # 4-3번 ')' 붙이기
        answer += ')'
        
        # 4-4번 u의 첫 번째 마지막 문자 제거, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙이기
        for x in u[1:len(u)-1]:
            if x == '(':
                answer += ')'
            else:
                answer += '('
        
    return answer