PROGRAMMING/Algorithm
-
[구간최대/최소/구간합] Sqrt Decomposition과 Segment TreePROGRAMMING/Algorithm 2024. 12. 11. 17:59
배열이 업데이트 되면서서 구간 최대, 최소, 합을 구하는 문제를 효율적으로 풀기 위한 Sqrt Decomposition과 Segment Tree 알고리즘에 대하여 알아보겠습니다. Square Root Decomposition은 특정 유형의 쿼리 및 업데이트 작업을 효율적으로 처리하기 위한 기법으로, 주로 정적 배열에서 동작합니다. 이 기법은 배열을 고정된 크기의 블록으로 나누어 각 블록에 대한 일부 계산을 미리 수행하여 시간 복잡도를 줄이는 방식으로 동작합니다.1. 블록 크기배열의 길이를 n이라 할 때, 각 블록의 크기는 √n으로 설정합니다. 이는 시간 복잡도를 O(√n)으로 유지하기 위해서입니다.Python 코드에서는 math.ceil(math.sqrt(n))을 사용하여 블록 크기를 정수로 계산합니..
-
baekjoon 3190 : 뱀(snake)PROGRAMMING/Algorithm 2017. 8. 5. 04:44
오랜만에 알고리즘 문제 푸려니 너무 힘들었다.. 백준 기준 정답률 17%의 삼성 SW역량시험에 출제되었던 문제. 특정 class를 만들어 Queue를 이용하는 idea까진 생각해 냈지만, 문제에 대한 이해도가 부족했던 것 같다. 나에게 있어서 문제의 요지는 다음과 같았다. 1. 방향 설정을 간단하게 하기 처음에 east west 난리를 쳤다가 코드가 점점 길어졌다. L로 계속 돌면 반시계, D면 시계방향이라는 것을 뒤늦게 깨닫고 순환성을 이용하여 마침내 방향이 숫자가 될 수 있었다. 역시 수학을 잘 해야해.. 2. queue에 무엇을 넣을 것인지? ★★★ 머리와 꼬리만 알면 된다고 생각했는데 몸통도 알아야 한다. 그래서 뱀 전체를 queue에 넣었다. 꼬리는 queue의 head이므로 꼬리가 없어질 때마..