Mgcllee

[알고리즘] 세그먼트 트리 (Segment Tree)

세그먼트 트리는 연속된 데이터에서 특정 범위에 대한 합과 같은 연산이 필요할 때 사용되는 알고리즘 입니다. 예를들어, {5, 8, 7, 3, 2, 5, 1, 8, 9, 7}이라는 배열에서 특정 범위인 (0번부터 시작할 때) 1번부터 9번까지 합을 빠르게 구하려고 합니다. 단순하게 연산한다면 반복문을 통해 순차적으로 방문하여 합을 계산할 수 있습니다...

[백준][2042] 구간 합 구하기

이 포스트는 백준 사이트의 구간 합 구하기 문제 풀이입니다. 문제 해결 과정 이 문제는 세그먼트 트리라는 알고리즘을 사용하면 큰 값이 입력되더라도 빠르게 정답을 구할 수 있습니다. 세그먼트 트리를 사용하지 않고 주어진 명령어에 따라 매번 합을 구하고 숫자를 갱신한다면, 시간초과가 발생합니다. 따라서 임의의 구간별로 합을 미리 계산해 ...

[백준][2098] 외판원 순회

이 포스트는 백준 사이트의 외판원 순회 문제 풀이입니다. 문제 해결 과정 이 문제는 비트마스킹과 메모이제이션 기법을 사용하면 제한시간 안에 결과를 확인할 수 있습니다. 문제가 요구하는 결과는 모든 지점을 방문할 때, 비용의 최솟값입니다. 이 값을 구하기 위해 모든 지점에서 매번 새롭게 비용을 구한다면 시간초과로 인해서 제한시간 안에 해...

[OS] 프로세스 간 통신하기 (IPC)

이 포스트는 개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다. 프로세스는 메인 메모리에서 독립적으로 실행되는 프로그램 단위입니다. 각각의 프로세스는 고유의 주소 공간을 할당 받고 각자의 실행 흐름을 갖고 있기 때문에 한 프로세스가 다른 프로세스 주소 공간에 접근하여 데이터를 공유하는 것은 불가능합니다. 따라서 운영체제에서는 프로...

[멀티 쓰레드] 멀티 쓰레드 프로그래밍은 언제 해야 할까?

이 포스트는 개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다. 이 포스트는 “게임 서버 프로그래밍 교과서”를 참고하여 작성된 포스트입니다. 멀티 쓰레드는 여러 가지 일을 한 번에 처리할 수 있다는 엄청난 장점이 있지만 쓰레드를 생성하고 일반 싱글 쓰레드처럼 사용하면 최악의 경우, 싱글 쓰레드 프로그램보다 못한 결과가 나올 수 있습니다...

[네트워크] EPoll의 개념

이 포스트는 “게임 서버 프로그래밍 교과서”를 참고하여 작성된 포스트입니다. 이전 포스트에서 Poll() 함수를 언급을 했었습니다. 포스트의 마지막에 설명한 Poll() 함수의 단점으로 반복문을 사용한 소켓 전체 순회가 있었습니다. 이 전체 순회로 인해 실시간 처리가 중요한 게임 서버에서는 적합하지 않을 수 있습니다. 따라서 처리 속도가 중요...

[백준][1806] 부분합

이 포스트는 백준 사이트의 부분합 문제 풀이입니다. 문제 해결 과정 이 문제를 처음 시도하였을 때, 주어진 배열을 정렬하고 정렬된 배열을 순차 탐색하면서 총 합이 S가 넘은 순간의 길이를 반환하려고 했습니다. 그러나 이러한 해결 방법의 문제점은 최단 길이가 아니라 최초 적합 길이가 반환된다는 점입니다. 예를들어, N과 S가 10, 20...