Computer Science(50)
-
펜윅 트리(Fenwick Tree)
Overview 펜윅 트리 (Fenwick Tree)는 구간 합을 빠르게 구하기 위해 고안된 자료구조입니다. 결론부터 말씀을 드리면 구간트리의 진화된 형태라고도 할 수 있습니다. 기존의 배열 자체에서 구간 합을 구하기 위해서는 해당 구간을 모두 순회하면서 값을 더해야 하므로 구간 길이에 비례하는 시간이 소요됩니다. O(N)의 시간복잡도를 갖는다는 의미이죠. 이를 더 빠르게 구현하기 위해 고안된 자료구조가 바로 구간트리이며, 구간트리가 갖는 장점을 살리면서 메모리를 훨씬 더 절약할 수 있도록 고안된 자료구조가 바로 펜윅 트리입니다. (구간 트리에 관한 자세한 내용은 구간 트리를 다룬 포스팅을 참고해주세요) Definition 펜윅 트리가 갖는 중요한 아이디어는 구간 합을 구하기 위해서 부분 합만을 빠르게 ..
2020.06.14 -
[백준 2263] 트리의 순회
풀이 트리의 중위 순회(InOrder), 후위 순회(postOrder)의 성질을 이용하여 전위 순회(preOrder)의 결과를 출력하라는 문제입니다. 중위 순회와 후위 순회를 이용해서 직접 트리를 생성한 후에 그냥 전위 순회를 재귀적으로 호출하는 방법도 있겠지만, 이 방법은 트리를 생성해야 하기 때문에 귀찮고 비효율적인 작업이 될 가능성이 보여서 다른 방법으로 문제를 해결하였습니다. 트리의 중위 순회는 트리의 모든 데이터를 일차원 직선에 사영했을 때, 그 결과를 순차적으로 보여준다는 특징이 있습니다. 정렬된 이진 탐색 트리의 경우 트리의 중위 순회 결과는 숫자 배열을 정렬된 순서대로 출력합니다. 트리의 후위 순회는 재귀적인 방식으로 Left child -> rightChild -> Parent Node의..
2020.03.21 -
KMP 알고리즘
Overview 문자열 매칭은 여러 곳곳에서 흔하게 사용되는 알고리즘 중의 하나입니다. 당장에 브라우저에서 command + f 나 ctrl + f를 눌렀을때 나타나는 검색 바에서도 문자열 매칭을 통해 찾고자하는 문자열의 위치를 알려줍니다. 가장 단순한 문자열 매칭 방법은 해당 페이지에 있는 모든 문자열에 대해서 찾고자 하는 문자열을 일일이 대입하는 방식일 것입니다. 전체 문자열의 길이를 $n$, 찾고자 하는 문자열의 길이를 $m$이라고 하면 $O(mn)$ 의 시간이 소요되게 될 것입니다. 이는 문자열의 길이가 굉장히 긴 경우에는 심각한 비효율성을 초래하기 때문에 개선의 필요성이 있으며, 이를 효율적으로 개선한 방법 중의 하나 ( $ O(m+n) $ 의 시간복잡도를 가지고 있음 )가 이제 소개할 KMP알..
2020.03.17 -
[BOJ_10814 | Stable Sort] 나이순 정렬
풀이 stable sort를 통해 구현한다면 쉽게 해결할 수 있는 문제이다. Stable Sort란 정렬 알고리즘의 종류가 아닌 알고리즘의 정렬 방식에 관한 것으로 동일한 키 값을 가진 원소들에 대하여 정렬하기 전과 정렬하기 후의 value가 같은 순서를 가지도록 정렬하는 방식을 의미한다. 예를 들어 [key, value] 쌍을 갖는 객체들이 다음과 같이 나열되어 있다고 하자 [3, "철수"] [2, "영희"] [1, "훈이"] [2, "맹구"], [2,"뚱이] key값에 대하여 위 객체들을 오름차순으로 정렬한다고 할 때, Stable Sort는 객체들을 다음과 같이 정렬한다. [1, "훈이"] [2, "영희"] [2, "맹구"] [2, "뚱이"] [3, "철수"] 즉, key 값이 동일한 경우 정렬되기..
2019.07.10 -
[BOJ_1182 | DFS backtracking] 부분집합의 합
풀이 DFS 백트래킹을 이용해서 풀 수 있는 문제였다.부분집합의 모든 경우를 헤아린다든지 하는 문제에서는 DFS를 통해재귀함수가 알아서 처리하도록 하는 편이 코딩하는 데 더 간편한 것 같다. 이 문제를 풀 때 주의해야 할 점은탐색을 하다가 S값을 찾았다고 해서 서둘러 탐색을 종료해서는 안된다는 것이다.예를 들어 S 값이 10이라고 할 때 1, 2, 3, 4 를 순서대로 탐색하고 '아 10이니까 이제 종료하고 다른 케이스를 살펴봐야지'하면 안된다는 의미인데, 왜냐하면 Array의 원소 중에 음수인 경우가 있으므로1, 2, 3, 4, -5, 5인 경우도 합이 10이 되는 케이스가 있을 수 있기 때문이다.따라서 S값을 찾았을 때는 counter의 값만 증가시켜주고 탐색을 계속해야 한다. 소스코드 import ..
2019.02.15 -
[BOJ_10799 | Stack] 쇠막대기
풀이 스택을 이용해서 풀어야하는 문제였다. 물론 반복문을 이용해서 풀 수도 있겠지만, 스택을 활용하면 문제풀이가 훨씬 용이해진다.간단히 정리해보자면, 스택은 FIFO(First in First out)을 특징으로 하는 자료구조이다.말 그래도, 먼저 넣은 데이터가 먼저 나오게 하는 구조인 것이다.이를 이용해서 쇠막대기를 레이저로 자를때 한번에 몇개씩 자르는지를 쉽게 구할 수 있다. *출처 Wikipedia 원리는 다음과 같다.'(' 가 나오면 스택에 '(' 를 집어넣고 막대기의 개수를 하나 추가한다.예를 들어 '((((' 이런식인 경우 계속 스택에 쌓기만 하는 것이다.막대기의 개수는 4개가 될 것이다. 그 다음이 중요한데, 만약 ')' 가 나오는 경우 "막대기의 개수를 하나 줄이고" 막대기의 개수만큼 총 ..
2019.02.15