Algorithm

[BOJ] - 내 생각에 A번인 단순 dfs문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 극좌표압축 + 스위핑 + 완전탐색 + maximum subarray

https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 문제자체가 참 난감하다. 처음 든 생각은, 금광세그처럼 좌표를 압축한 다음에, 완전 탐색을 하는 것이였다. 그리고 잘 생각해보면, 2차원 스위핑을 1차원으로 치환할 수 있는데, dfs를 통해 각 노드에 시퀀스와 깊이를 저장해주면 이가 충분히 가능하다. import sys input = sys.stdin.readline '''..

[BOJ] - 제곱근 분할법 (Square Root Decomposition) + mo's 알고리즘

문제 크기가 N인 정수 배열 A가 있고, 여기서 다음과 같은 연산을 최대 M번 수행해야 하는 문제가 있다고 해 봅시다. 1. 구간 l, r (l a[i]: ans = a[i] 소스 1의 시간복잡도는 O(N)입니다. 2번 연산의 시간복잡도 A[i] = v는 O(1)입니다. 최대 쿼리가 M번 수행해야 하니 연산 하나의 시간 복잡도는 O(N)이 됩니다. 총 시간복잡도는 O(NM)입니다. 제곱근 분할법 제곱근 분할법을 사용하려면 크기가 N개인 배열을 크기가 sqrt(N)인 그룹으로 나누고, 각 그룹의 최솟값을 별도로 저장해야 합니다. 그룹의 크기가 sqrt(N)이니, 그룹의 개수도 sqrt(N)개입니다. N이 제곱수가 아닌 경우에는 그룹의 크기로 sqrt(N) a[i]: d[i//r] = a[i] 여기서 2번 ..

Java - 알고리즘 ( quick sort )

1. 퀵 정렬이란? 퀵 정렬 ( quick sort )이란 ? 정렬 알고리즘의 꽃 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성함 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함 함수는 왼쪽 + 기준점( pivot ) + 오른쪽을 리턴함 2. 퀵 정렬의 구현 // src/com.company/QuickSort.java package com.company; import java.util.ArrayList; import java.util.Arrays; public class QuckSort { public ArrayList splitFunc(ArrayList dataList) { if(dataList...

Java - 알고리즘 ( merge sort )

1. 병합정렬 재귀용법을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 알고리즘 이해 데이터가 네 개 일떄(데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해 보자) 두 단계로 분리해서 이해할 수 있음 1단계: 정렬되지 않은 배열을 끝까지 분리하는 단계 2단계: 분리한 데이터를 단계별로 합치는 단계 예: dataList = [1, 9, 3, 2] 먼저 [1, 9], [3, 2]로 나누고 다시 앞 부분은 [1], [9]로 나누고 ( 여기까지 1단계 ) 다시 정렬해서 합친다. [1, 9] ( 이 부분부터 2단계 ) 다음..