본문 바로가기

분할 정복4

[알고리즘] 분할 정복 알고리즘(Divide-and-Conquer) - 퀵 정렬(quick sort) 분할 정복에 대한 설명은 https://cuckoobird.tistory.com/153 을 참고해주세요. 퀵 정렬 퀵 정렬은 피봇(pivot)이라 일컫는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓습니다. 퀵 정렬은 분할된 부분문제들에 대해서도 위와 동일한 과정을 순환으로 수행하여 정렬합니다. 피봇은 분할된 왼편이나 오른편 부분에 포함되지 않습니다. 피봇이 60이라면, 60은 [20, 40, 10, 30, 50] 과 [70, 90, 80] 사이에 위치하게 됩니다. 초기 배열이 { 6, 3, 11, 9, 12, 2, 8, 15, 18, 10, 7, 14 } 인 배열을 예시로 설명하겠습니다. 피봇을 중간에 있는 값으.. 2023. 10. 6.
[알고리즘] 분할 정복 알고리즘(Divide-and-Conquer) - 합병 정렬(merge sort) 분할 정복 알고리즘이란? 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘입니다. 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산합니다. 이들의 해를 취합하여 원래 문제의 해를 얻습니다. 분할 알고리즘의 분할은 부분 문제와 부분 해로 나누어 집니다. 분할된 입력에 대한 문제를 부분 문제(subproblem)라고 합니다. -> 해 계산 부분 문제의 해를 부분 해라고 합니다. 부분 문제는 더 이상 분할 할 수 없을 때까지 분할합니다. 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분 문제의 크기가 n/2일 경우의 분할의 예입니다. 총 분할한 횟수가 k라고 한다면, 처음 입력의 크기가 n이고, 분할된 그 다음의 크기는 n/2, 그 다음은 n/(2^2), ... , n/(2^.. 2023. 9. 24.
[백준] 10830번 '행렬 제곱' - Java https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 코드 import java.io.*; import java.util.*; public class Main { private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); private static final BufferedWriter bw = new BufferedWriter(new OutputSt.. 2023. 8. 24.
[백준] 2447번 별 찍기 10 - Java 문제 코드 맞았습니다가 뜬 코드입니다. - 메모리 16784KB | 시간 556ms | 코드 길이 745B import java.io.*; public class Main { private static final BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { int n = Integer.parseInt(bf.readLine()); for(int.. 2023. 7. 2.

티스토리툴바