개발의 희망 개발의 희망

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

플로이드 와샬 모든 정점에서 모든 정점으로의 최단 거리를 구하기 위해서 플로이드 와샬 알고리즘을 사용할 수 있습니다. 즉, 정점 [A, B, C, D]가 존재할 때 A->C로 이동하기 위해서 중간에 B를 거치거나 D를 거쳐 갈 수 있습니다. B와 D를 거치는 게 A->C로 가는 것보다 더 짧은 거리로 이동할 수도 있고 아닐 수도 있습니다. 또한 기존에는 지나갈 수 없는 경로를 다른 정점을 거쳐 지나갈 수 있는 경로가 되기도 합니다. 다음 방향 그래프가 존재합니다. 무한대의 의미는 해당 방향으로 이동하는 경로가 존재하지 않음을 의미합니다 => ex. 정점A -> 정점C 정점A 정점B 정점C 정점D 정점A 0 4 무한대 6 정점B 3 0 7 무한대 정점C 5 무한대 0 4 정점D 무한대 무한대 2 0 위의..