이 포스트는 백준 사이트의 토마토(7576) 문제 풀이입니다. 문제 해결 과정 이 문제는 BFS(너비우선탐색)을 활용하여 해결할 수 있습니다. 문제의 입력을 받으면서 익지 않은 토마토 개수(pure_tomato_cnt)를 증가시킵니다. 그리고 그 숫자에 따라 BFS 실행 여부를 결정합니다. BFS로 창고의 각 칸에 접근하여 익지 않은...

힙(Heap) 자료구조란 완전 이진 트리를 사용한 자료구조로 주로 우선순위를 표현하기 위해 사용됩니다. 힙의 구현 방법에 따라 최댓값 혹은 최솟값을 빠르게 찾을 수 있습니다. 최댓값을 빠르게 구하기 위한 힙을 최대 힙이라고 하며, 최솟값을 빠르게 구하기 위한 힙을 최소 힙이라고 합니다. 최대 힙 최댓값을 빠르게 구할 수 있는 최대 힙은 루트...

이 포스트는 백준 사이트의 최소 스패닝 트리 문제 풀이입니다. 문제 해결 과정 이 문제는 Union-Find 알고리즘을 활용한 크루스칼 알고리즘으로 해결할 수 있습니다. 최소 스패닝 트리란, 주어진 그래프의 모든 정점을 연결하는 부분 그래프에서 그 가중치의 합이 최소인 트리를 의미합니다. 그리고 이 트리를 구하기 위한 크루스칼 알고리즘...

개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다. 인덱스의 개념 인덱스는 데이터베이스 테이블에서 검색 성능을 향상시키기 위한 자료구조의 이름입니다. 테이블에 있는 특정 칼럼에 대해 인덱스를 생성하면, 해당 칼럼의 데이터들은 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장됩니다. 인덱스가 생성된 이후 입력 받은 쿼리문에서 ...

이 포스트는 백준 사이트의 앱 문제 풀이입니다. 문제 해결 과정 이 문제는 DP 테이블을 활용하여 해결할 수 있는 문제입니다. 또 다른 대표 DP 문제인 배낭 문제와 유사하게 메모리 교체 비용의 최소값을 구해야 합니다. 차이점이 있다면 배낭 문제의 경우, 최댓값을 구하는 것이 목표였지만 이 문제에서는 최솟값을 구하는 것이 목표라는 점 ...

이 포스트는 개인 학습을 기록한 내용을 담고 있어 추후 수정될 수 있습니다. 교착 상태란 쓰레드란 프로세스 안에서 존재하는 하나의 실행 단위입니다. 이 실행 단위는 실행 중인 프로그램 안에서 최소 1개 이상이 존재하며 복수의 쓰레드가 동시에 실행될 수 있습니다. 쓰레드는 고유의 스택을 갖고 있기 때문에 함수의 호출로 생성되는 정보들을 저장하...

이 포스트는 백준 사이트의 기념품 문제 풀이입니다. 문제 해결 과정 이 문제는 STL 컨테이너 중 하나인 Deque을 활용하면 쉽게 해결할 수 있습니다. 문제에서는 백준이가 움직이지만, Deque을 활용한 풀이에서는 백준이가 아닌 N명의 사람이 차례마다 백준이 앞에 오는 것으로 Deque의 양방향 연산(Push, Pop)을 활용하였습니...

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

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

이 포스트는 “게임 서버 프로그래밍 교과서”를 참고하여 작성된 포스트입니다. 개인 학습을 기록한 내용을 담고 있어 추후 수정될 예정입니다. epoll은 리눅스에서 대량의 논블로킹 소켓을 효율적으로 처리해 주는 API 였습니다. 윈도우에서는 epoll 대신 IOCP 라는 API를 사용하여 대량의 소켓을 관리합니다. 이번 포스트에서는 IOCP의 개...