백준 구간 합 구하기1

• 

  [백준] 2042번 구간 합 구하기 파이썬 해설 -세그먼트 트리 알고리즘 공부 혼자 하는 게 생각보다 어렵..지만 꾸준히 해야지! 나는 원래 C언어로 알고리즘 문제를 풀었다. 임베디드 전공이다 보니 전공과목에서 프로그래밍 언어를 C/C++ 만 배웠기 때문이다. 하지만 임베디드를 넘어서 다양한 분야에 만능 프로그래머가 되고 싶어서 파이썬을 시작하게 되었고, 요즈음은 파이썬으로만 문제를 푼다. 쓸데없는 소리를 한 이유는.. 파이썬으로 알고리즘 문제를 풀면 너무 느려서 시간 초과가 너무 자주 뜬다.. 편법으로는 PyPy3로 채점하는 방법이 있는데, 그래도 찝찝하긴 하다.. 나는 이 문제를 세그먼트 트리 알고리즘으로 풀었다. 간단하게 정리해보자 세그먼트 트리 이 문제를 단순하게 배열을 확인하는 알고리즘으로 구현한다면 O(N^2)의 시간 복잡도를 갖게 되어 시간 초과를 면하지.. 프로그래밍/Algorithm 2019. 9. 2.