[알고리즘] 세그먼트 트리 (Segment Tree)
세그먼트 트리는 연속된 데이터에서 특정 범위에 대한 합과 같은 연산이 필요할 때 사용되는 알고리즘 입니다. 예를들어, {5, 8, 7, 3, 2, 5, 1, 8, 9, 7}이라는 배열에서 특정 범위인 (0번부터 시작할 때) 1번부터 9번까지 합을 빠르게 구하려고 합니다. 단순하게 연산한다면 반복문을 통해 순차적으로 방문하여 합을 계산할 수 있습니다...
세그먼트 트리는 연속된 데이터에서 특정 범위에 대한 합과 같은 연산이 필요할 때 사용되는 알고리즘 입니다. 예를들어, {5, 8, 7, 3, 2, 5, 1, 8, 9, 7}이라는 배열에서 특정 범위인 (0번부터 시작할 때) 1번부터 9번까지 합을 빠르게 구하려고 합니다. 단순하게 연산한다면 반복문을 통해 순차적으로 방문하여 합을 계산할 수 있습니다...
이 포스트는 백준 사이트의 구간 합 구하기 문제 풀이입니다. 문제 해결 과정 이 문제는 세그먼트 트리라는 알고리즘을 사용하면 큰 값이 입력되더라도 빠르게 정답을 구할 수 있습니다. 세그먼트 트리를 사용하지 않고 주어진 명령어에 따라 매번 합을 구하고 숫자를 갱신한다면, 시간초과가 발생합니다. 따라서 임의의 구간별로 합을 미리 계산해 ...
이 포스트는 “게임 서버 프로그래밍 교과서”를 참고하여 작성된 포스트입니다. 개인 학습을 기록한 내용을 담고 있어 추후 수정될 예정입니다. epoll은 리눅스에서 대량의 논블로킹 소켓을 효율적으로 처리해 주는 API 였습니다. 윈도우에서는 epoll 대신 IOCP 라는 API를 사용하여 대량의 소켓을 관리합니다. 이번 포스트에서는 IOCP의 개...
이 포스트는 백준 사이트의 외판원 순회 문제 풀이입니다. 문제 해결 과정 이 문제는 비트마스킹과 메모이제이션 기법을 사용하면 제한시간 안에 결과를 확인할 수 있습니다. 문제가 요구하는 결과는 모든 지점을 방문할 때, 비용의 최솟값입니다. 이 값을 구하기 위해 모든 지점에서 매번 새롭게 비용을 구한다면 시간초과로 인해서 제한시간 안에 해...
이 포스트는 개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다. 프로세스는 메인 메모리에서 독립적으로 실행되는 프로그램 단위입니다. 각각의 프로세스는 고유의 주소 공간을 할당 받고 각자의 실행 흐름을 갖고 있기 때문에 한 프로세스가 다른 프로세스 주소 공간에 접근하여 데이터를 공유하는 것은 불가능합니다. 따라서 운영체제에서는 프로...
이 포스트는 백준 사이트의 행렬 곱셈 순서 문제 풀이입니다. 문제 해결 과정 이 문제는 여러 작은 문제로 나워서 해결하는 DP(다이나믹 프로그래밍) 방법을 사용해 해결할 수 있습니다. 문제를 해결하기 위해서 먼저, DP 테이블을 사용하였습니다. 2차원 배열의 테이블은 DP_table[a][b]에서 a번째 행렬부터 b번째 행렬까지의 곱 ...
이 포스트는 개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다. 이 포스트는 “게임 서버 프로그래밍 교과서”를 참고하여 작성된 포스트입니다. 멀티 쓰레드는 여러 가지 일을 한 번에 처리할 수 있다는 엄청난 장점이 있지만 쓰레드를 생성하고 일반 싱글 쓰레드처럼 사용하면 최악의 경우, 싱글 쓰레드 프로그램보다 못한 결과가 나올 수 있습니다...
이 포스트는 백준 사이트의 DSLR 문제 풀이입니다. 문제 해결 과정 이 문제는 4가지 연산에 따른 결과를 BFS를 활용해 반복적으로 수행하며 정답을 구할 수 있습니다. 첫 번째 시도에서는 주어진 숫자(start)를 문자열을 활용하여 4가지 연산을 수행하고자 하였습니다. 그러나 이러한 방법은 시작 숫자가 1 이고 목표한 숫자가 1000...
이 포스트는 “게임 서버 프로그래밍 교과서”를 참고하여 작성된 포스트입니다. 이전 포스트에서 Poll() 함수를 언급을 했었습니다. 포스트의 마지막에 설명한 Poll() 함수의 단점으로 반복문을 사용한 소켓 전체 순회가 있었습니다. 이 전체 순회로 인해 실시간 처리가 중요한 게임 서버에서는 적합하지 않을 수 있습니다. 따라서 처리 속도가 중요...
이 포스트는 백준 사이트의 부분합 문제 풀이입니다. 문제 해결 과정 이 문제를 처음 시도하였을 때, 주어진 배열을 정렬하고 정렬된 배열을 순차 탐색하면서 총 합이 S가 넘은 순간의 길이를 반환하려고 했습니다. 그러나 이러한 해결 방법의 문제점은 최단 길이가 아니라 최초 적합 길이가 반환된다는 점입니다. 예를들어, N과 S가 10, 20...