🏃🏻&zwj;♀️스텝바이스텝

[BOJ] 11657 타임머신

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 📍 고려해야할 점 C < 0 인 경우 타임머신으로 시간을 되돌아가는 경우이다. ➔ 음의 가중치 존재 1번 도시에서 출발한다. 음의 사이클이 있거나 경로가 아예 없다면 -1 출력 오버플로우 범위 조심 🕹️ 풀이과정 1️⃣ 간선과 정점, 비용의 정보를 저장한다. 2️⃣ 벨만 포드 알고리즘을 사용..

알고리즘/BOJ

[BOJ] 1865 웜홀

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 📍 고려해야할 점 한 지점에서 출발하여 다시 출발했던 지점으로 돌아왔을 때 처음 출발했을 때보다 시간이 되돌아가 있는 경우 판단 ➔ 웜홀 내에서 시간이 거꾸로 흘러간다. ➡️ 음수 가중치 존재 & 음의 사이클 존재 O 한 지점에서 출발한다. (특정 지점에서 출발 X) 임의의 정점에서 출발 모든 정점에서 출발 두 지점을 연결하는 도로가 한 ..

알고리즘/🗂️ 정리

Bellman-Ford (벨만-포드)

2023.09.08

V개의 정점과 E개의 간선을 가진 가중 그래프 G에서 특정 출발 정점(S)에서부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘이다. 👀 특징 음의 가중치를 갖는 간선도 존재 가능하다. 음의 사이클의 존재 여부를 확인할 수 있다. 최단거리를 구하기 위해서는 V-1번 E개의 모든 간선을 확인한다. 음의 사이클 존재 여부를 확인하기 위해 한 번 더 E개의 간선을 확인한다. 총 연산 횟수 = VxE ⌛️ 시간 복잡도 = O(VE) V번째 모든 간선을 확인했을 때 거리배열이 갱신되었다면 그래프 G는 음의 사이클을 가지는 그래프이다. 위와 같이 음의 가중치를 갖고 있는 그래프가 있을 때, 다익스트라로 정점 1에서 모든 정점까지의 거리를 구현한다면 1 ➔ 2 = 1 1 ➔ 2 ➔ 3 = 2 1 ➔ 2 ➔ 3 ➔ ..

알고리즘/BOJ

[BOJ] 1939 중량제한

2023.09.07

✨ Binary Search + BFS/DFS https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 📍 고려해야할 점 두 섬 사이에 여러 개의 다리가 있고 양방향이다. 공장이 있는 두 섬을 연결하는 경로가 반드시 존재한다. (반드시 존재하는 경로의 입력값만 주어짐) 옮길 수 있는 물품의 최대 중량 구하기 🕹️ 풀이과정 1️⃣ 입력값으로 주어진 다리 정보 저장 (a섬과 b섬 사이에 중량제한이 ..

알고리즘/🗂️ 정리

LCA (최소공통조상)

2023.09.04

LCA는 Lowest Common Ancestor의 약자로 최소 공통 조상을 찾는 알고리즘이다. 트리구조에서 사용되며 두 정점 u, v에서 가장 가까운 공통 조상을 찾으면 된다. 이 그래프에서 13번 정점과 15번 정점의 최소공통조상은 5번 정점이다. 11번 정점과 13번 정점의 최소공통조상은 1번 정점이다. 이런 상황에서 12번 정점과 14번 정점의 최소공통조상은 12번 정점이다. 🕹️ LCA 과정 1️⃣ 입력받은 정점과 간선으로 양방향 그래프 (트리구조) 를 생성한다. 2️⃣ BFS나 DFS를 사용하여 depth를, DP를 활용하여 parent 정보를 저장하는 트리를 생성한다. 3️⃣ LCA(u, v) 메서드를 호출하여 u와 v의 최소공통조상을 찾는다. u와 v 중에서 깊이가 더 깊은 정점을 얕은 깊..

알고리즘/🗂️ 정리

Binary Search (이분탐색)

2023.09.01

Binary Search는 정렬되어 있는 리스트에서 탐색 범위를 좁혀가며 원하는 값을 얻는 알고리즘이다. 리스트가 반드시 정렬되어 있어야 하며, 3개의 변수 (low, mid, high)를 사용해서 값을 탐색한다. 중앙값(mid)을 기준으로 비교하여 low와 high 값을 정하고, 이 과정을 반복해서 값을 얻어내면 된다. 탐색 범위가 반으로 줄어들면서 start와 end 값을 정하는 과정을 거치기 때문에 시간복잡도가 낮고, 순차적 탐색보다 빠른 탐색이 가능하므로 배열의 원소 개수가 많을 때 주로 사용된다. 🕹️ Binary Search 과정 1️⃣ 배열의 중간 값을 계산하여 찾고자 하는 값과 비교한다. 중간 값은 (low+high)/2 로 계산한다. 2️⃣ 중간 값이 찾고자 하는 값보다 작다면 중간값보다..

Java

Priority Queue (우선순위 큐)

2023.08.31

Queue는 먼저 들어간 데이터가 먼저 나오는 형식이나, Priority Queue는 이와 다르게 데이터를 꺼낼 때 우선순위가 가장 높은 것부터 나오게 된다. 일반적인 큐처럼 추가/삭제 연산이 있지만, 그 순서에 관계없이 우선순위를 고려하여 데이터를 가져올 수 있다. Priority Queue는 힙 구조(트리구조)를 이용해서 만들고, 큰 값이 우선이 되는 최대힙과 작은 값이 우선이 되는 최소힙이 있다고 생각하면 된다. (default = 최소 힙) 🕹️ Priority Queue 사용법 최소 힙 (최솟값부터 배열) PriorityQueue minHeap = new PriorityQueue(); 최대 힙 (최댓값부터 배열) PriorityQueue maxHeap = new PriorityQueue(Coll..

Spring Framework/📛 에러 기록

📛 Variable used in lambda expression should be final or effectively final 에러

2023.08.31

자바에서 stream()을 사용해 orderProductOption에 있는 orderProduct를 설정해주는 과정에서 "Variable used in lambda expression should be final or effectively final" 에러를 나타내며 orderProduct에 빨간 밑줄이 그어졌다. 람다 표현식 내에서 사용되는 변수가 final 또는 effectively final이 아니기 때문에 발생하는 것으로 보인다. 더보기 👀 effectively final : 변수가 실제로 'final' 로 선언되어 있지 않더라도 람다 표현식 내에서 해당 변수의 값이 변경되지 않는 경우이다. int x = 10; Consumer consumer = (value) -> { // x = x + 5; ..

전체 글

[BOJ] 11657 타임머신

[BOJ] 1865 웜홀

Bellman-Ford (벨만-포드)

[BOJ] 1939 중량제한

LCA (최소공통조상)

Binary Search (이분탐색)

Priority Queue (우선순위 큐)

📛 Variable used in lambda expression should be final or effectively final 에러

티스토리툴바