Programming/Problem Solving3 3차원 펜윅 트리(Fenwick Tree/Binary Indexed Tree/Segment Tree) 최근 3차원 공간의 부분합을 많이 구해야 일이 생겼다. 속도가 느려서 팬윅트리를 이용하여 해결하고자 했는데, 3차원으로 가니 직관적이지 않다. 조금 공부를 했고, 3차원 팬윅트리 코드를 완성 시켜보았다. 까먹지 않기 위해 자체 PS 문제를 제작, 솔루션을 남겨본다. * 문제 설명 512^3 공간에서 인풋으로 주어진 범위 내의 '1' 을 카운트하여 반환하는 함수 작성 * 제약사항 힙 메모리 : 1gb 미만 스텍 메모리 : 1mb 미만 CPU TIME : 코드 참조 #include #include #include #include const int SIZE = 512; // 코드를 읽고 PASS를 출력하게 하는 CountDefect 함수를 작성하시오. // 제약사항 HEAP MEMORY < 1gb int Co.. 2021. 4. 16. 알고리즘 문제풀이 시간 단축을 위한 팁 (2) 1편에 이어서 몇 가지 더 써 보고자 한다. Cache를 고려하자 이 내용은 너무 기본적인 내용이라 넣을까 말까 고민을 했는데, 의외로 모르는 사람들이 많은듯해서 한 번 더 상기하고자 작성한다. 기본적으로 컴퓨터는 하나의 값을 읽어올 때 딱 그 변수를 읽어오는 것이 아니라. 주변에 있는 값을 포함해서 한 블록을 통째로 준비시킨다. 왜냐하면 통상적으로 주변에 있는 값들을 연속적으로 읽을 확률이 높기 때문이다. 따라서 연속해서 사용할 값은 쓴다면 연속한 위치에 있는 게 좋다. // 1000x1000 array 요소의 총 합을 반환 해주는 함수 void badSum(int a[1000][1000]) { int sum = 0; for(int x = 0 ;x < 1000 ; x++) for(int y = 0 ; .. 2021. 3. 31. 알고리즘 문제풀이 시간 단축을 위한 팁 (1) 라떼만해도 알고리즘 문제풀이 사이트라고 하면 백준, 알고스팟, 코드잼 같은 사이트 밖에 없었던 것 같은데, 우후죽순 많은 사이트들이 생겼고, 사이트들의 문제를 기반으로 많은 신입/경력 채용이 이루어지는 것 같다.(최근 이직 준비를 하면서 알게됨) 블로그에 알고리즘 카테고리를 하나 추가하면서, 중상급 이상의 문제에서 적용할 수 있는 테크닉, 풀이 접근방법 등을 정리해보고자 한다. 문제풀이 초/중급이라면 문제풀이를 할 때 어떤 알고리즘이 가장 최적화된 시간 복잡도로 풀이할 수 있는지 직관을 먼저 기르는 것을 추천한다. * 알고리즘 문제풀이에서만 해당되는 내용이며 실무에서는 정반대의 접근법으로 코드 작성을 해야 할 수도 있다. 이 점을 주의해야 한다. Function call 최소화 간단한 코드라면 funct.. 2021. 3. 29. 이전 1 다음
