본문 바로가기

분할정복

[BOJ] 백준 1493번 박스 채우기 (Java)
Dot Algo∙ DS/PS 2022. 3. 23. [BOJ] 백준 1493번 박스 채우기 (Java) #1493 박스 채우기 난이도 : 골드 4 유형 : 그리디 / 분할정복 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net ▸ 문제 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, 4×4×4, 8×8×8, ...) 세준이가 가지고 있는 박스의 종류와 큐브의 종류와 개수가 주어졌을 때, 박스를 채우는데 필..
[BOJ] 백준 2104번 부분배열 고르기 (Java)
Dot Algo∙ DS/PS 2022. 1. 16. [BOJ] 백준 2104번 부분배열 고르기 (Java) #2104 부분배열 고르기 난이도 : 플레 5 유형 : 세그먼트 트리 / 분할 정복 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net ▸ 문제 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱한..
[프로그래머스] 2020 카카오 #2 괄호 변환 (Java)
Dot Algo∙ DS/PS 2021. 9. 4. [프로그래머스] 2020 카카오 #2 괄호 변환 (Java) #2 괄호 변환 난이도 : LEVEL2 유형 : 문자열 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr ▸ 문제 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든..
[BOJ] 백준 2263번 트리의 순회 (Java)
Dot Algo∙ DS/PS 2021. 7. 25. [BOJ] 백준 2263번 트리의 순회 (Java) #2263 트리의 순회 난이도 : 골드 3 유형 : 트리 / 분할 정복 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net ▸ 문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. ▸ 입력 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. ▸ 출력 첫째 줄에 프리오더를 출력한다. 문제 풀이 preord..
[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 5. 30. [알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java) 분할정복(divide and conquer) 알고리즘 분할정복 알고리즘 (Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 정렬 알고리즘 비교 선택 정렬과 삽입 정렬의 최대 실행시간은 O(n^2)이다. 입력하는 배열의 크기가 크다면 이 알고리즘으로 정렬하는데 매우 오랜 시간이 걸릴 수 있다. 반면 분할정복 알고리즘을 사용하는 합병 정렬의 실행시간은 모든 경우에 대해 O(nlgn)으로 , 퀵 정렬은 최대 O(n^2)이지만 최선이나 평균의 경우 O(nlgn)으로 비교적 빠른 시간을 갖는 것을..
[BOJ] 백준 10211번 Maximun Subarray (Java)
Dot Algo∙ DS/PS 2021. 5. 28. [BOJ] 백준 10211번 Maximun Subarray (Java) #10211 Maximum Subarray 난이도 : 실버 3 유형 : DP/ 누적 합 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net ▸ 문제 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있다. 여러분은 N과 배열 X가 주어졌을 때, X의 maximum subarray의 합을 구..

티스토리툴바

티스토리툴바