목록전체 글 (601)
sm 기술 블로그
분할정복 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 알고리즘 설계 유형 1)Divide : 문제가 분할이 가능한 경우 2개 이상의 문제로 나눈다. 2)Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다. 3)Combine : Conquer한 문제들을 퉁합하여 원래 문제의 답을 얻는다. 분할정복 알고리즘은 최소한 두 개의 하위 문제를 생성하므로 재귀 호출을 여러번 실행한다. 사용정렬 퀵정렬 특정 원소 피봇을 기준으로 주어진 배열을 두 부분 배열로 분할하고 각 부분 배열에 대해 퀵 정렬을 순환적으로 적용하는 방식이다. 1)Divide 피봇 하나를 선택하여 피봇을 기준으로 2개의 부분 배열로 ..
import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int T = Integer.parseInt(br.readLine()); for (int i = 0; i < T; i++) { String[] p = br.readLine().split(""); int n = Integer.parseInt(br.readLine()); String x = br.readLine(..
from collections import deque import sys input = sys.stdin.readline T = int(input()) for _ in range(T): p = list(input().rstrip()) n = int(input()) x = input() x = x.replace("[", "") x = x.replace("]", "") x = x.replace(",", " ") queue = deque(list(x.split())) R_cnt = 0 error = False for val in p: if val == 'R': R_cnt += 1 continue if val == 'D' and len(queue) == 0: error = True break else: if R..
import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] tmp1 = br.readLine().split(" "); int N = Integer.parseInt(tmp1[0]); int M = Integer.parseInt(tmp1[1]); //indexof 사용을 위해 deque대신 linkedlist 사용 LinkedList num = new LinkedList(); Deque innum = new ArrayDequ..