본문 바로가기

Algorithm 💡272

[백준 7570번] 줄 세우기 n = int(input()) data = list(map(int,input().split())) data.insert(0,0) index_list = [0]*(n+1) count = 1 max_length = -1 for i in range(1,n+1): index_list[data[i]] = i for i in range(1,n): if index_list[i] < index_list[i+1]: count += 1 max_length = max(max_length, count) else: count = 1 if max_length != -1: print(n - max_length) else: print(0) 이번 문제는 임의의 순서로 세워진 번호를 맨 앞이나 맨 뒤로만 이동시킬 수 있다는 가정 하에 .. 2023. 8. 14.
[백준 2631번] 줄세우기 n = int(input()) data = [] dp = [1]*n for i in range(n): data.append(int(input())) for i in range(n): for j in range(i): if data[i] > data[j]: dp[i] = max(dp[i],dp[j]+1) print(n - max(dp)) 이번 문제는 임의의 순서로 세워진 번호를 번호 순서대로 배치하기 위한 최소한의 이동횟수를 구하는 문제이다. 번호를 옮기는 횟수를 최소화하기 위해서는 번호 순서대로 세워져있는 어린이들을 최대한 많이 고정시키고 나머지만 이동시켜야 한다. 즉, 가장 긴 증가하는 부분수열 LIS(Longest Increasing Subsequence)의 길이를 구하고 이를 전체 어린이 수에서 빼.. 2023. 8. 14.
[백준 1525번] 퍼즐 from copy import deepcopy from collections import deque import sys sys.setrecursionlimit(10**7) graph = [list(map(int,input().split())) for _ in range(3)] final_graph = [[1,2,3],[4,5,6],[7,8,0]] dx = [-1,1,0,0] dy = [0,0,-1,1] visited = {} temp_graph = deepcopy(graph) for i in range(3): for j in range(3): if graph[i][j] == 0: first_x, first_y = i, j def changeToString(arr): # 퍼즐의 상태를 문자열로 바꿔주는 함.. 2023. 8. 12.
[백준 16637번] 괄호 추가하기 # 우선순위 X, 중첩괄호 X, 괄호 없어도 Ok # 괄호 안에는 연산자 1개만 가능 # 괄호를 적절히 추가해서 최대값 만들기 n = int(input()) formula = list(input()) # 최대값 초기화 max_value = float("-inf") # 주어진 값 2개를 연산하는 함수 def calculate(num1,operator,num2): if operator == '+': return num1 + num2 elif operator == '-': return num1 - num2 elif operator == "*": return num1 * num2 def dfs(index,value): global max_value # dfs로 마지막 값까지 계산을 마쳤을 경우 if index .. 2023. 8. 10.
[백준 14503번] 로봇 청소기 n,m = map(int,input().split()) r,c,d = map(int,input().split()) # 현재 방향을 기준으로 반시계방향으로 탐색 dx = [[0,1,0,-1],[-1,0,1,0],[0,-1,0,1],[1,0,-1,0]] dy = [[-1,0,1,0],[0,-1,0,1], [1,0,-1,0],[0,1,0,-1]] # 바라보는 방향이 북쪽인 경우 # dx_0 =[0,1,0,-1] # dy_0 =[-1,0,1,0] # 바라보는 방향이 동쪽인 경우 # dx_1 = [-1,0,1,0] # dy_1 = [0,-1,0,1] # 바라보는 방향이 남쪽인 경우 # dx_2 = [0,-1,0,1] # dy_2 = [1,0,-1,0] # 바라보는 방향이 서쪽인 경우 # dx_3 = [1,0,-1.. 2023. 8. 9.
[백준 15662번] 톱니바퀴(2) t = int(input()) gear = [[0]*8 for _ in range(t)] rotate_list = [] answer = 0 for i in range(t): gear[i] = list(map(int,list(input()))) def rotate_right(lst): # 시계 방향으로 회전시키는 함수 lst.insert(0,lst.pop()) def rotate_left(lst): # 반시계 방향으로 회전시키는 함수 lst.append(lst.pop(0)) k = int(input()) for i in range(k): # 회전 목록 입력받고 저장 number, direction = map(int,input().split()) rotate_list.append((number-1,direc.. 2023. 8. 9.

티스토리툴바