본문 바로가기

분류 전체보기

 (328)
[백준] 7662번 : 이중우선순위 큐 7662번: 이중 우선순위 큐 처음 이 문제를 풀때 이분탐색법으로 문제를 해결하려고 했으나 시간 초과 판정을 받았습니다. 큐를 하나두고 이분탐색으로 큐를 삽입할 인덱스를 결정하여 해당 인덱스에 값을 삽입한다면 큐의 첫번째 원소값은 최소값 큐의 마지막 원소는 최대값을 갖게 됩니다. T = int(input()) for _ in range(T): k = int(input()) queue = deque() for _ in range(k): cmd , num = map(str, input().split()) number = int(num) if cmd == 'I': # 삽입 if queue: if number > queue[-1]: queue.append(number) else: idx = bisect_left..
[백준] 10942번 : 팰린드롬? 10942번: 팰린드롬? 팰린드롬은 문자열이 주어졌을때 왼쪽으로 부터 읽었을때와 오른쪽에서부터 읽었을때가 같을때 팰린드롬이라고 합니다. 해당 문제는 다이나믹 프로그래밍 문제로 다음과 같은 아이디어에서 문제를 해결 할 수 있습니다. dp[n][m]이 있을때 문자열 n부터 m까지의 팰린드롬인지 아닌지를 구분하는 역할을 한다. dp[n][m]은 현재 문자열 arr[n] == arr[m]이 같다면 dp[n+1][m-1]이 팰린드롬인지 아닌지만 판별하면 dp[n][m]이 팰린드롬인지 아닌지 알수 있습니다. 예시 dp[0][0] ... dp[n][n] 은 자기자신임으로 팰린드롬 입니다. dp[0][1] … dp[n-1][n]은 arr[n-1] 과 arr[n]이 같다면 팰린드롬 입니다. dp[0][2]는 arr[0]..
[백준] 11049번 : 행렬곱셈순서 11049번: 행렬 곱셈 순서 해당문제는 다이나믹 프로그래밍 문제로 행렬 곱을 연산할때 순서가 뒤바뀌면 행렬 곱셈량이 달라진다. 행렬 곱셈량의 최소값을 구하기위해서는 아래와 같이 문제를 정의하고 해결하였습니다. 행렬 A,B,C,D가 있다고 할때 A인 자기자신은 곱셈을 할수 없으므로 0으로 초기화 한다. 길이가 2인 경우는 (AB), (BC) 각각 곱한 결과 값을 갖는다. 길이가 3인 경우는 (AB),C, A(B,C) 중 최소 값이다. 길이가 4인 경우는 A(BCD), (AB)(CD), (ABC)(D) 중 최소 값이다. 위의 내용을 점화식으로 정리한뒤 코드로 정리하면 아래와 같다. dp[n][m]은 n번째 행렬부터 m번째 행렬을 곱을 연산시 곰셈량의 최소값을 저장하는 배열이다. dp[n][m]은 min(d..
[백준] 1915번 : 가장 큰 정사각형 1915번: 가장 큰 정사각형 해당문제는 다이나믹프로그래밍으로 문제를 해결하였습니다. from pprint import pprint n, m = map(int, input().split()) move = [(-1,-1), (-1,0), (0,-1)] cost = [-1 for _ in range(3)] graph = [[] for _ in range(n)] for i in range(n): char = list(str(input())) for num in char: graph[i].append(int(num)) maxresult = 0 for i in range(n): for j in range(m): for t in range(len(cost)): # 초기값 Init cost[t] = -1 for k ..
[백준] 2225번 : 합분해 2225번: 합분해 해당 문제는 다이나믹 프로그래밍 문제로 해결하였습니다. N이 5이고 K가 3일때 구하는 아래의 그림과 같이 표현하였습니다. 첫번째는 모두 한가지 이고, 두번째 부터는 숫자 N일때 이전에 있던 0부터 N까지의 경우의 수를 모두 더한 값과 같다. 예를들어 두번째에 3의 숫자의 경우의 수를 구한다고 한다면 0+3 → 1 1+2 → 1 2+1 → 1 3+0 → 1 총 4가지가 된다. 즉 이전에 있던 경우의수를 0부터 N까지 모두 더한값과 같다. 위의 내용을 코드로 정리하면 아래와 같다. N , K = map(int, input().split()) dp = [[1 for _ in range(N+1) ] for _ in range(K)] for i in range(1, K): for j in r..
[백준] 2096번 : 내려가기 https://www.acmicpc.net/problem/2096 해당 문제는 캐싱으로 문제를 해결 하였습니다. 캐싱을 할때에 필요한 배열은 temp 변수와 현재 최대값 ,최소값을 저장하는 current 변수를 선언 하였습니다. 정수 삼각형 문제처럼 문제를 해결하면 됩니다. 현재 값은 이전에 값중에서 최소값 혹은 최대값을을 선택 한뒤 자기자신을 더하면 됩니다. N = int(input()) current = [[0,0] for _ in range(3)] # maxValue, minValue for _ in range(N): a,b,c = map(int, input().split()) # 최대값 구하기 temp = [0 for _ in range(3)] temp[0] = a + max(current[0][..
[백준] 2565번 : 전기줄 https://www.acmicpc.net/problem/2565 해당문제는 다이나믹 프로그래밍으로 문제를 해결하였습니다. LIS 문제로 최장증가 부분 수열 을 찾는 문제입니다. ( Longest Increasing Subsequence) LIS란 : 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대한 부분 수열을 최장 증가 부분 수열이라고 합니다. 예를들어, {6,2,5,1,7,4,8,3} 이라는 배열이 있을경우, LISSMS { 2,5,7,8 } 이 됩니다. 일반적으로 길이가 얼마인지 푸는 방법은 DP 다이나믹 프로그래밍을 이용하는 것입니다. N = int(input()) queue = [] for _ in range(N..
[백준] 17471번 : 게리맨더링 17471번: 게리맨더링 해당문제는 문제를 푸느라 굉장히 고생을 했습니다. A구역, B구역 으로 나눌 수 있는 경우의 수를 모두 구한다. A,B 구역을 나누는 방법은 저는 재귀를 통하여 경우의 수를 만들었습니다. 파이썬의 조합 라이브러리를 사용 할 수 있었지만 사용하지 않았습니다. A,B 구역을 나눌때 예를들어 N이 6일때 {1,2,3) {4,5,6}와 {4,5,6}, {1,2,3} 이 중복되지 않도록 만듭니다. 또한 순열이 아닌 조합으로 만들어야합니다. A구역, B구역으로 각각 잘 나누어졌는지 확인한다. A, B 구역으로 잘 나누었는지 확인하는 방법은 BFS를 활용 하였습니다. 팀에서 특정한 점에서 BFS를 했을때 다른 팀을 거쳐서 가지않고 우리팀을 갈 수 때이어야 합니다. A구역, B구역의 인구수의 ..

티스토리툴바