Lee 코딩 Lee 코딩

: 배낭에 들어갈 수 있는 무게가 주어지고, 물건들의 무게와 가치가 주어진 후 총 가치가 최대가 되도록 하는 방법을 구하는 문제 1) 물건들을 쪼갤 수 있다고 가정하는 문제 -> 그리디 알고리즘을 사용해서 풀이 2)물건들을 쪼갤 수 없다고 가정하는 문제 -> DP를 이용해서 풀이 (브루트포스를 이용해서 각 물건들을 넣을 때와 안 넣을 때를 모두 고려해서 풀이할 수도 있지만 이 경우 O(2^N)의 시간복잡도를 가지기 때문에 시간초과가 발생한다.) 배낭 알고리즘 p[i,w]를 i개의 보석이 있고 무게의 한도가 w일 때 최적의 가치라고 하자. i번째 물건이 배낭에 들어갈 수 없다면 : i-1개의 물건이 배낭에 들어갔을 때의 최적 가치 값 -> 즉 p[i-1][w] i번째 물건을 배낭에 넣을 수 있다면 : i-..

위상 정렬이란? : 정렬 알고리즘의 일종으로 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 ex) 선수과목을 고려한 학습 순서 결정 *진입 차수 : 특정한 노드로 들어오는 간선의 개수 위상 정렬 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐가 빌 때까지 다음 과정을 반복한다 - 큐에서 노드를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다 - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 가능하다.(보통 사이클이 발생하지 않는다고 문제에서 주어짐) 위 과정을 수행하는 동안 큐에서 빠져나간 노드를 순서대로 출력하면 위상 정렬의 결과값이다. 따라서 큐에 들어가는 원소의 순서에 따라 답이 여러가지 존..

다익스트라 알고리즘과 같이 한 노선에서 다른 노선으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이라면 플로이드 워셜 알고리즘은 모든 노드쌍들의 최단 거리를 구하는 알고리즘이다. ** 플로이드 워셜 알고리즘은 음의 간선이 있는 경우에도 사용 가능하다. for (int k = 0; k < n; k++) { //모든 노드를 한 번씩 중간 노드로 놓고 거리를 갱신 for(int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } k는 경유지, i는 시작, j 는 도착지이다. 예..

2022.06.27 - [분류 전체보기] - 최단 경로 - 다익스트라 알고리즘 최단 경로 - 다익스트라 알고리즘 다익스트라 알고리즘 : 특정 노드에서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘(음의 간선이 없을 때 제대로 동작) 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화 한다 3. leeeehhjj.tistory.com 최단 경로를 구하는 알고리즘 중 다익스트라 알고리즘을 위의 링크처럼 간단히 구현하면 O(V^2)의 시간 복잡도가 나오기 때문에 노드 개수가 10000개가 넘어가면 위의 코드로는 구현하기가 힘들다. 따라서 매번 최단 거리 테이블을 선형적으로 탐색하는 것이 아니라 우선순위 큐를 활용하여 찾게 되면 O(ElogV)의 시간 복잡도로 구현할 수 있다. 개선된 다익스트라..

다익스트라 알고리즘 : 특정 노드에서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘(음의 간선이 없을 때 제대로 동작) 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화 한다 3. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신한다 5. 3과 4번을 반복한다 -출발 노드는 1일 때 노드 번호 1 2 3 4 5 6 거리 0 무한 무한 무한 무한 무한 -1번 노드에서 갈 수 있는 노드는 2,3,4이므로 이 노드들의 최단 거리 테이블을 갱신 노드 번호 1 2 3 4 5 6 거리 0 2 5 1 무한 무한 -4번 노드가 가장 가까우므로 4번 노드를 거쳐 가는 거리 확인 -> 3번, 5번으로 가는 거리의 최단..

자바의 Collection에는 Set, List, Map 3가지의 인터페이스가 있다. 1. Set 인터페이스 (집합) : 중복되는 요소를 허용하지 않음. 저장 순서를 유지하지 않음. - Hash Set Hash란? : 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑(변환)하는 것 ex) apple -> eef6ecaf , a -> 89aee2fe Hash Set이란? : Hash와 set이 합쳐진 것으로 set 기능을 통해중복없이 데이터를 저장하고, Hash 기능을 통해데이터가 저장되어 있는지 빠르게 찾을 수 있게 하는 클래스이다 - Linked HashSet : Hash set을 개선한 것으로 중복은 허용하지 않으면서 입력 순서는 보장받고 싶은 경우 사용한다. -Tree set : hash s..

크루스칼 알고리즘을 사용하기 위해서는 union-find 알고리즘을 알아야 한다 2022.04.14 - [자료구조, 알고리즘] - Union-Find(합집합 찾기)알고리즘 Union-Find(합집합 찾기)알고리즘 = Disjoint-Set 서로소 집합 알고리즘이라고도 불림. 그래프에서 여러 개의 노드 중 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. - find : 노드의 부모 leeeehhjj.tistory.com - 신장 트리(Spanning tree) : 그래프 내에 있는 모든 정점들을 포함하고, 정점들 간에 서로 연결되며 사이클을 이루지 않는 그래프이다 신장 트리는 정점의 개수가 n개일 때 간선의 개수가 n-1개이다. 이때 간선의 가중치들의 합이 최소가 ..

= Disjoint-Set 서로소 집합 알고리즘이라고도 불림. 그래프에서 여러 개의 노드 중 두 개의 노드를 선택해서 이 노드들이 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. - find : 노드의 부모가 같은지 확인하여 현재 같은 집합에 속하는지 확인하는 것 - union : 두 노드가 각각 포함되어 있는 집합을 합치는 것 1. 처음에 모든 노드들이 연결되어 있지 않을 때 -> 자기 자신이 부모 i 0 1 2 3 4 5 parent[i] 0 1 2 3 4 5 2. 1과 3, 2와 5가 각각 연결되어 있을 때 i 0 1 2 3 4 5 parent[i] 0 1 2 1 4 2 1과 3의 부모를 합쳐주고, 2와 5의 부모를 합쳐 준다(Union) 이 때는 더 작은 값으로 합쳐준다 3. 1-2-3처럼 연..