heemang.dev heemang.dev

입력받은 숫자가 소수인지 판단하는 근거는 다음과 같다.숫자 1은 소수가 아니다.약수로 1과 자기 자신의 값만 갖는다. 예를 들어, 숫자 13의 약수는 1과 13이므로 소수이다. 위 조건에 맞춰 자바 코드를 작성할 수 있다.static boolean isPrimeNumber(int num) { if (num == 1) { return false; } for (int i = 2; i  그러나 위 방법으로 소수를 판단하게 되면 소요 시간이 길다는 단점이 있다. 만약 num이 소수이면서 매우 큰 수라면 반복문 수행 시간이 너무 길어지기 때문에 비효율이 존재한다. 반복문 소요 시간을 줄이기 위해 소수를 판단하는 근거를 새로 설정한다.숫자 1은 소수가 아니다.숫자 2는 짝수 중에서 유일..

문제 : 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..

플로이드 와샬 모든 정점에서 모든 정점으로의 최단 거리를 구하기 위해서 플로이드 와샬 알고리즘을 사용할 수 있습니다. 즉, 정점 [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 위의..