heemang.dev heemang.dev

문제 : https://www.acmicpc.net/problem/2346 메모리 초과 코드 : https://ideone.com/TxRwHV   위 문제를 Deque 자료 구조를 사용하여 풀 수 있되, 구현체로 LinkedList를 사용하면 메모리 초과가 발생한다.반대로 ArrayDeque 구현체를 사용하면 메모리 초과가 발생하지 않는다. LinkedList의 특징으로는 연속적인 메모리 공간을 사용하지 않고, 참조(Reference) 필드를 사용하여 다음 노드를 가리킨다. 반면에 ArrayDeque는 배열 기반의 구현체이므로 연속적인 메모리 공간을 사용한다.  Deque 구현체로 LinkedList를 사용하면 큐에 값이 저장될 때마다 새로운 노드가 생성된다. 이 노드에서는 이전 노드를 가리키는 참조 포..

https://www.acmicpc.net/problem/2696https://www.acmicpc.net/problem/1655해당 문제의 경우 입력받은 숫자들 중에서 중앙값을 구하는 문제이다. 예를 들어, [1, 5, 7, 8, 9] 리스트가 존재할 때 중앙에 위치한 값은 7이다. 본 문제를 풀기 위해, 1개의 우선순위 큐를 사용하여 문제를 풀었다.자바에서 PriorityQueue를 사용하여 원소 삽입, 삭제 시에 발생하는 시간 복잡도는 다음과 같다.삽입 : O(log N)삭제 : O(log N)원소 삽입 및 삭제 시에 최소 힙, 최대 힙 성질을 만족하기 위해 트리 구조를 조정한다. 최소 힙과 최대 힙 그리고 트리 구조 조정에 대해서 모른다면 다음 글을 참고한다. https://bristle-com..

1. 여러 사용자가 동시에 서버에 요청을 보낸다면, 서버는 모든 요청을 어떻게 순차적으로 처리할 수 있을까?웹 서비스 이용자가 많고, 특정 서비스에 대한 요청이 동시에 몰리게 되면, 서버에서 적절한 처리를 하지 않는 경우 일부 요청이 유실되는 문제가 발생할 수 있다. 예를 들어, 두 사용자가 동시에 물건을 구매했을 때 재고가 100개라면 정상적으로는 98개가 되어야 하지만, 첫 번째 사용자의 요청이 유실되면 DB에는 99개로 잘못 저장될 수 있다. 서버는 여러 사용자가 동시에 동일한 데이터에 접근하더라도 모든 요청을 순차적으로 처리할 수 있도록 관리해야 한다. 하지만 모든 요청을 완벽히 처리하려고 하면 서비스 속도가 느려질 수 있는 한계가 있다. MySQL에서는 배타적 락(Pessimistic Lock)..

1. Redis란?Redis는 Key:Value 구조의 비정형 데이터를 저장하고 관리하는 비관계형 데이터베이스이다. 데이터를 디스크가 아닌 메모리에 저장하므로 인메모리 DB(In-Memory DB)라고 부른다. 2. 데이터베이스가 있는데, 왜 Redis를 사용할까?데이터베이스가 있음에도 Redis를 사용하는 이유는 CPU가 계산에 필요한 데이터를 얻기 위한 속도 차이가 발생하기 때문이다. 데이터베이스는 물리 디스크에 직접 데이터를 쓰기 때문에 서버에 장애가 발생하더라도 데이터가 손실되지 않는다. 그러나 데이터가 필요할 때마다 매번 디스크에 접근하게 되면 사용자가 많아질수록 데이터베이스에 부하가 발생하게 된다. 따라서 사용자가 많을 때 데이터베이스의 과부하를 줄이기 위해서 Redis와 같은 캐시 서버를 도..

InnoDB 버퍼 풀(Buffer Pool) : 메모리 내의 캐시 영역으로, 실제 데이터를 디스크에서 읽어오지 않고 메모리에서 바로 접근할 수 있도록 하는 공간이다.데이터 파일(Data File) : 디스크에 저장된 실제 데이터 파일이다. 모든 변경 사항은 결국 디스크에 반영되어야 한다. 1. INSERT 발생INSERT INTO User(m_id, m_name, m_area)VALUES(1, '이희망', '부산'); 데이터가 새로 삽입되면, InnoDB 버퍼 풀에 해당 데이터가 먼저 기록된다. 버퍼 풀에 저장된 데이터는 백그라운드 프로세스에 의해 나중에 데이터 파일에 기록된다. 2. UPDATE 발생UPDATE SET m_area = '서울' WHERE m_id = 1; UPDATE 작업이 발생하면서 ..

1. 컴퓨터 시스템에서 연산 속도CPU 레지스터 > CPU 캐시(Cache) > 메인 메모리(RAM) > 하드 디스크(HDD) 2. 캐시(Cache)를 왜 사용할까?메모리가 CPU 속도를 따라오지 못한다.CPU 성능은 빠르게 향상되었지만, 메모리의 처리 속도는 이를 따라오지 못했다. 아무리 CPU의 처리 속도가 빠르더라도 메모리 속도가 이를 따라오지 못한다면 시스템 성능은 저하될 수밖에 없다.메모리와 CPU 간 속도 차이로 작업이 지연된다.CPU는 초당 수십억 개의 명령어를 처리할 수 있지만, 메인 메모리는 그 속도를 따라오지 못한다. CPU가 데이터를 처리하려면 메모리에서 필요한 데이터를 읽어오거나 쓰는 과정이 필요한데, 메모리 속도가 느리면 CPU는 데이터가 도착할 때까지 대기해야 한다. CPU가 메..