CS

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)란?원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 다음 조건을 만족하는 수열이다.각 원소가 이전 원소보다 크다. (증가하고 있다)그 길이가 최대이다 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 } 이다. 구현 방법DP를 이용한 방법이분탐색을 이용한 방법 DP를 이용한 방법 알고리즘 설명간단하지만 시간복잡도가 O(n^2)로 이분탐색보다는 큰 알고리즘이다dp[i]:  i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이라고 한다면,주어진 배열에서 인덱스를 한 칸씩(i+=1) 늘려가면서 확인합니다.내부 반복문으로 i보다 작은 인덱스들을..

Union-Find 연산에서 find()함수의 코드는 일반적으로 이렇게 짠다.public static int find(int x){ if(x==parent[x]) { return x; } return parent[x]=find(parent[x]);} ❗️이때 return을 find(parent[x])이 아니고 왜 parent[x]=find(parent[x]);를 해야할까?다음과 같은 트리 구조가 있다고 하자.1  이런 경우 1이 루트 노드가 되고, parent 배열은 다음과 같다.노드 Idx12345parent[idx]11234 return find(parent[x]);일 경우find(5)를 호출하면:find(5) -> find(4) -> find(3) -> find(2) -..

위상정렬 알고리즘이란?정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 이때 위상정렬은 사이클이 없는 방향 그래프(DAG)에서만 가능하다. 인접 리스트를 사용하면 시간 복잡도가 O(V+E)이고 인접 행렬을 사용하면 시간 복잡도가 O(V^2)이다. 위 DAG 그래프를 위상정렬하면 아래와 같이 여러 결과가 나올 수 있다.구현 방법진입차수를 이용한 BFS 방법과 재귀를 이용한 DFS 방법이 있다.BFS 방법알고리즘 설명진입차수 (in-degree) : 특정한 노드로 들어오는 간선의 개수진출차수 (out-degree) : 특정한 노드에서 나가는 간선의 개수(시작) 진입차수가 0인 정점을 큐에 넣는다.큐가 빌 때까지 다음의 과정을 반복한다.큐에서 ..

프림 알고리즘이란?트리 집합을 단계적으로 확장하는 것이다. 새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 한다. 이때 새로운 정점을 연결하는 것은 가중치를 기준으로 오름차순 정렬한 우선순위 큐에서 꺼낸다는 것이고, 단게적으로 확장하는 것은 이 우선순위 큐에서 뽑을 정점에서 연결 가능하고 방문하지 않은 정점을 우선순위 큐에 추가한다는 것이다.배열로 구현할 경우 시간 복잡도 o(n^2)이고, 최소 힙으로 구현할 경우 시간 복잡도 O(Elog n)이다.구현 방법초기 상태로 정점(=노드)는 서로 연결되어 있지 않다. 정점과 연결된 간선을 하나씩 추가하면서 MST를 만든다. 우선 순위 큐에는 (정점, 가중치) 형식으로 저장되며, 첫 시작은 (시작 정점..

Spanning Tree이란? 신장 트리는 그래프 내의 모든 정점을 포함하는 트리이다. 모든 정점들이 연결 되어 있어야 한다.사이클을 포함해서는 안된다.그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다.MST(=Minimum Spanning Tree)이란?최소 신장 트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 간선의 가중치의 합이 최소여야 한다.n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.사이클이 포함되어서는 안된다. MST 알고리즘 구현 방법- 크루스칼 알고리즘 Kruskal Algorithm- 프림 알고리즘 Prim Algorithm 크루스칼 알고리즘이란?간선을 가중치가 작은 순서대로 그래프에 포함시킨다. ..

분리 집합분리집합이란 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합, 즉 서로소 집합이다. 따라서 A ∩ B = Ø가 성립된다. 유니온 파인드이러한 분리집합은 유니언 파인드 자료구조를 사용한다.  Find 연산각 트리셋의 자식 노드가 루트(최상위 노드)를 찾는 과정find(x)찾는 노드에 들어있는 대표 노드로 감x와 x의 부모가 같다면 x를 리턴그렇지 않다면 재귀적으로 find를 수행x의 x의 부모가 같다면 그 노드는 루트 노드이다.public int find(int x) { if (x == parent[x]) return x; return parent[x] = find(parent[x]);} Union연산한 트리셋의 루트가 다른 트리셋의 루트를 가르키게 하여 트리를 병합하는 과정Union(x..

플로이드 워셜 알고리즘이란?플로이드-워셜 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 모두 구하는 알고리즘이다. 따라서 2차원 테이블에 최단 거리 정보를 저장한다.  다익스트라벨만-포드플로이드-워셜경로계산방식One-To-AllOne-to-OneAll-to-All음의 가중치XOO음수 사이클XXX최단거리테이블1차원테이블1차원테이블2차원테이블다른 알고리즘 포함그리디-DP 경로 계산 방식에는 아래와 같은 종류가 있다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 ->벨만-포드 알고리즘  2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 ->다익스트라 알고리즘3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 ->..

벨만-포드 알고리즘이란? 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다. 음의 사이클이 없고 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정에서 시작된다. 다익스트라 알고리즘에 비해 효율이 떨어지지만 더 많은 그래프에 대해서 정확한 답을 구할 수 있다.  다익스트라벨만-포드음수 가중치XO음수 사이클XX시간복잡도O(mlog n)O(mn)❗️벨만-포드가 가중치가 음수인 경우에도 최단 거리를 구할 수 있는 이유다익스트라 알고리즘에서는 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택해서 1단계씩 최단 ..

다익스트라 알고리즘이란?다익스트라 알고리즘은 기본적으로 greedy와 dp를 사용한 알고리즘으로 그래프의 최단 경로를 구하는 알고리즘이다. 하나의 정점에서 출발하는 최단 거리를 구하는 것이다.  이때 간선의 가중치는 양수여야 한다. 인접 행렬로 표현된 그래프의 경우 시간 복잡도 O(n^2)이지만 우선순위 큐를 사용하면 시간 복잡도 O(mlog n)까지 낮출 수 있다.  음의 가중치를 가지면 안되는 이유 다음과 같은 경우에 다익스트라 알고리즘은 A->B->D 총 비용 22가 가장 최소 경로라고 생각 할 것이다. (A-B-DB->C->D가 총-90 으로 값이 더 작다. 즉, 위와 같이 음의 가중치가 포함된 그래프의 최단 경로는 다익스트라 알고리즘으로 구할 수 없는 경우가 있다. 동작 과정출발지에서 인접한 노..

✔️ Comparable목적: 자기 자신과 매개변수 객체를 비교구현 방법: Comparable 인터페이스를 구현하는 클래스는 compareTo 메서드를 오버라이드import java.util.*;class Person implements Comparable { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public int getAge() { return age; } @Overrid..