- 명세만 존재 - 특징만 나타남 - 추상화 정도 (abstract class / interface)
데이터 타입
추상 데이터 타입 (Abstract Data Type, ADT)
: 명세와 구현을 분리하겠다!
추상화 정도 ↑ = 사용 불가 (내용이 거의 X)
Queue : 추상화 정도 ↑ (body가 없이 선언만 되어 있기 때문에 사용하기 위해선 LinkedList를 사용해야 함), 선입선출
Stack : 후입선출
컴파일 과정
전처리기
컴파일러
어셈블러
링커
ex) #define, #include
고급언어 → 어셈블리어
어셈블리어 → 기계어 ex) object 파일, 목적코드
ex) 산출물 exe
Call by value vs Call by reference
값(value)에 의한 전달
참조(reference)에 의한 전달
- 값만 전달 - 실인자에 영향 X
- 주소 전달 - 실인자에 영향 및 변경
정적 vs 동적
정적
동적
- 컴파일 타임 (프로그램 시작 전) - Stack
ex) static (정적 변수) → 컴파일 타임에 1번만 실행
- 런타임 (프로그램 실행 중) - Heap
함수 오버로딩
: 매개변수 선언이 다를 경우 동일한 이름의 함수로 정의 가능
자료형 다르면 가능
매개변수의 수 다르면 가능
반환형의 차이는 X
생성자
: 클래스의 이름과 동일한 이름의 함수이면서 반환형이 선언되지 않았고, 실제로 반환하지 않는 함수
객체 생성시 1번 호출
멤버변수의 초기화에 사용 불가!
오버로딩( 매개변수 조건에 따라 여러개를 작성 ) 가능
디폴트 값 설정 가능
주의! 생성자 코드가 1개라도 작성되어 있다면, 컴파일러는 기본생성자가 없다고 하더라도 기본생성자를 자동으로 생성 X
public class Book {
String title;
int price;
//public Book() { } // 기본생성자 필요!
public Book(String title, int price) { // 매개변수를 가진 생성자
this.title = title;
this.price = price;
}
public void showPrice() {
System.out.println(title + "의 가격은 " + price + "원 입니다");
}
}
public class HelloWorld {
public static void main(String[] args) {
Book b1 = new Book(); // Error발생 (기본생성자 자동생성 안됨)
Book b2 = new Book("국어책", 3000);
b1.showPrice();
b2.showPrice();
}
}
상속
1. 자바의 상속 방식 (2가지)
2. 자바에서 다중 상속이 안되는 이유!
EX) 상속받은 여러 개의 부모 클래스들에서 동일한 명칭의 필드나 메소드가 있는 경우
어떤 부모 클래스의 필드와 메소드를 상속받아야 하는가?
어떤 부모 클래스에 어떻게 접근해야 하는가?
➡️ 위와 같은 모호함 발생!
3. 자바 상속 방법 (extends)
//부모 클래스 생성
class 부모 {
}
//부모 클래스 상속
class 자식 extends 부모 {
}
4. 자바 상속 예제
class People{
// 필드
String name;
int age;
// 메소드
public void printMyself(){
System.out.println("이름 : " + name);
System.out.println("나이 : " + age);
}
}
class Student extends People{
// 필드
int korean_scroe; //국어성적
int math_score; //수학성적
int english_score; //영어성적
// 생성자
Student(String name, int age, int kor_score, int mat_score, int eng_score){
super.name = name; // 부모 필드
super.age = age; // 부모 필드
this.korean_scroe = kor_score;
this.math_score = mat_score;
this.english_score = eng_score;
}
// 메소드
public void printScore() {
System.out.println("국어성적 : " + korean_scroe);
System.out.println("수학성적 : " + math_score);
System.out.println("영어성적 : " + english_score);
}
}
public class Main {
public static void main(String[] args) {
Student student = new Student("홍길동", 18, 100, 90, 80);
student.printMyself(); // 부모 메소드 호출
student.printScore(); // 자식 메소드 호출
}
}
Super 키워드
: 자식 클래스에서 부모 클래스를 가리킬 때 사용하는 키워드
: 주로 부모 클래스의 필드에 접근, 메소드를 호출할 때 사용
5. 부모 클래스에서 상속이 안되는 것
부모클래스의 private 접근 제한을 갖는 필드 및 메소드
부모와 자식 클래스가 서로 다른 패키지에 있을 때, 부모의 default 접근 제한을 갖는 필드 및 메소드
접근 제어 지시자
1) public : 어디서든 접근 가능
2) protected : 상속관계에 놓였을 때, 자식 클래스에서의 접근 허용
3) private : 클래스 내에서만 접근 허용
알고리즘
: 특정 작업을 수행하는 명령어들의 유한 집합
알고리즘의 요건
입력 : 외부에서 제공되는 데이터가 0개 이상
출력 : 적어도 1개 이상의 결과 생성
명확성 : 각 명령은 명확하고 모호하지 X
유한성 : 알고리즘대로 수행하면 어떤 경우에도 반드시 종료
유효성 : 반드시 실행 가능 해야 함
정렬
정렬 방법의 분류
실행 방법
비교식 정렬 : 비교하고자 하는 각 키 값들은 한번에 두 개씩 비교하여 교환하는 방식
분산식 정렬 : 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식
정렬 장소
내부 정렬 : 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식 : 정렬 속도가 빠르지만, 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한됨
외부 정렬 : 정렬할 자료를 보조 기억장치에서 정렬하는 방식 : 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬 가능
Stable 정렬 : 버블, 삽입, 병합
Unstable 정렬 : 선택, 퀵, 힙
선택 정렬 출처 : https://gyoogle.dev/blog/algorithm/Selection%20Sort.html
: 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘: 배열에서 해당 자리를 선택하고, 그 자리에 오는 값을 찾는 것!
과정 1) 주어진 배열 중에 최솟값 찾기 2) 그 값을 맨 앞에 위치한 값과 교체 3) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체
시간복잡도
공간복잡도
O(n^2)
O(n)
버블 정렬 출처 : https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html : 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 : 단점 - 시간복잡도가 최선, 최악, 평균 모두 O(n^2)이므로 매우 비효율적!
과정 1) 1회전 : 1번째 원소 ↔ 2번째 원소, 2번째 원소 ↔ 3번째 원소, ... (n-1)번째 원소 ↔ n번째 원소 를 비교하여 교환 2) 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동 3) 2회전을 수행하고 나면 끝에서 두 번째 원소까지 정렬 4) 위의 과정을 계속 반복하여 뒤에서부터 첫번째 원소까지 정렬됨
시간복잡도
공간복잡도
O(n^2)
O(n)
삽입 정렬 출처 : https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html : 2번째 원소부터 시작하여 그 앞의 원소들고 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘 : 최선의 경우 O(n)의 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘 : 배열의 길이가 길어질수록 비효율적!
과정 1) 2번째 index의 값 temp에 저장 2) temp와 이전의 원소들과 비교하여 삽입 3) 1번 과정으로 돌아가 다음 index의 값을 temp에 저장하고 반환
시간복잡도
공간복잡도
최선 : O(n) 평균, 최악 : O(n^2)
O(n)
퀵 정렬 출처 : https://gyoogle.dev/blog/algorithm/Quick%20Sort.html : 분할 정복 (Divide and Conquer) 사용 : pivot 값이 최소나 최대값으로 지정되어 분할이 나누어지지 않으면 최악 (배열이 오름차순 / 내림차순 정렬된 경우)
과정 1) 배열 가운데서 하나의 원소 선택 = pivot 2) pivot 앞에는 pivot보다 값이 작은 모든 원소들이 오고, 뒤에는 pivot보다 값이 큰 모든 원소들이 오도록 배열을 둘로 나눔 → 분할 3) 분할을 마친 뒤 pivot은 더 이상 움직이지 X 4) 분할된 두 개의 작은 배열에 대해 재귀적으로 과정 반복
힙 정렬 출처 : https://gyoogle.dev/blog/algorithm/Heap%20Sort.html : 완전 이진 트리(삽입할 때 왼쪽부터 차례대로 추가하는 이진트리)를 기본으로 하는 Heap 자료구조를 기반으로 한 정렬 방식 : 최솟값 or 최댓값을 구할 때 유용함!
과정 1) 최대 힙 구성 2) 현재 힙 루트는 가장 큰 값 존재, 루트의 값을 마지막 요소와 바꾼 후 힙의 사이즈 하나 감소 3) 힙의 사이즈가 1보다 크면 위의 과정 반복
시간복잡도
공간복잡도
최선 : Θ(nlogn) 평균 : Ω(nlogn) 최악 : O(nlogn)
O(n)
기수 정렬 : 자릿수를 기준으로 차례대로 데이터를 정렬하는 정렬 알고리즘 : 각 데이터를 자릿수를 기준으로 분류하기 때문에 가장 큰 자릿수를 D라고 했을 때 O(Dn)의 시간 복잡도 가짐 : 자릿수의 개수만큼 반복
합병 정렬 출처 : https://st-lab.tistory.com/233 : 큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식
과정 1) 주어진 리스트를 절반으로 분할하여 부분리스트로 나눔 (분할) 2) 해당 부분리스트의 길이가 1이 아니라면 1번 과정 반복 3) 인접한 부분리스트끼리 정렬하여 합침 (정복)
시간복잡도
공간복잡도
O(nlogn)
O(n)
이분 탐색 (Binary Search)
: 배열 내부 데이터가 이미 정렬되어 있는 상황에서 사용 가능한 알고리즘
: 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
과정 1) 배열 정렬 2) left와 right로 mid 값 설정 3) mid와 구하고자 하는 값 비교 4) 구하고자 하는 값 > mid → left = mid + 1 구하고자 하는 값 < mid → right = mid - 1 5) left > right가 될 때까지 반복
시간복잡도 : O(logn)
순환 알고리즘 (Recursive Algorithm)
: 수행이 완료되기 전에 자기 자신을 다시 호출
직접 순환(direct recursion) : 함수가 그 수행이 완료되기 전에 자기 자신을 다시 호출 ➡️ 자기 자신을 재귀
간접 순환 (indirect recursion) : 호출 함수를 다시 호출하게 되어 있는 다른 함수를 호출 ➡️ main에서 재귀
public class Stack {
private Node head;
private Node top;
public Stack() {
head = top = null;
}
private Node createNode(int data) {
return new Node(data);
}
private boolean isEmpty() {
return top == null ? true : false;
}
public void push(int data) {
if (isEmpty()) { // 스택이 비어있다면
head = createNode(data);
top = head;
}
else { //스택이 비어있지 않다면 마지막 위치를 찾아 새 노드를 연결시킨다.
Node pointer = head;
while (pointer.next != null)
pointer = pointer.next;
pointer.next = createNode(data);
top = pointer.next;
}
}
public int pop() {
int popData;
if (!isEmpty()) { // 스택이 비어있지 않다면!! => 데이터가 있다면!!
popData = top.data; // pop될 데이터를 미리 받아놓는다.
Node pointer = head; // 현재 위치를 확인할 임시 노드 포인터
if (head == top) // 데이터가 하나라면
head = top = null;
else { // 데이터가 2개 이상이라면
while (pointer.next != top) // top을 가리키는 노드를 찾는다.
pointer = pointer.next;
pointer.next = null; // 마지막 노드의 연결을 끊는다.
top = pointer; // top을 이동시킨다.
}
return popData;
}
return -1; // -1은 데이터가 없다는 의미로 지정해둠.
}
}
큐 (Queue)
: 뒤쪽으로 들어가서 앞쪽으로 나오는 (선입선출) 자료 구조 형태
: 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용
FIFO (First In First Out, 선입선출) : 가장 먼저 들어온 것이 가장 먼저 나옴
첫 원소 : rear, 끝 원소 : rear
함수 종류
데이터 넣음 : enQueue()
비어있는 지 확인 : isEmpty()
꽉차있는 지 확인 : isFull()
데이터 뺌 : deQueue()
구현 방법
배열 이용
단순 배열 : 큐의 첫번째 원소를 queue[0]로 표현한 큐
배열 응용 : 큐의 첫번째 원소를 queue[front]로 표현한 큐
연결 리스트 이용
원형 큐 : 메모리 공간을 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기 제한 연산시간 : O(1)
연결리스트 큐 : 연결리스트 큐는 크기가 제한 없고 삽입, 삭제가 편리
우선순위 큐 : 우선순위가 가장 높은(낮은) 원소를 먼저 삭제 : 임의의 우선순위를 가진 원소 삽입 가능 : 힙 자료구조를 사용
// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
Queue<Integer> pq = new PriorityQueue<>();
// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
함수 종류
add(): 원소를 추가. 큐가 꽉 찬 경우에러 발생
offer() : 원소를 추가. 값 추가 실패 시 false를 반환
poll() : 첫 번째 값을 반환하고 제거, 비어있으면 null 반환
remove() : 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
isEmpty() : 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
clear() : 우선순위 큐를 초기화
size() : 원소의 수를 반환
트리 (Tree)
: 값을 가진 Node와 노드들을 연결해주는 Edge로 이루어진 자료구조
용어 정리
노드 : 트리의 원소
루트 노드 : 트리의 시작 노드
간선(edge) : 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 : 각 노드는 자식 노드의 개수만큼 서브 트리를 가짐
차수 : 노드의 차수 : 노드에 연결된 자식 노드의 수
트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
단말 노드 / 리프 노드 : 차수가 0인 노드, 자식 노드가 없는 노드
비단말 노드 : 차수 != 0
길이 : 출발 노드에서 목적지 노드까지 거쳐야 하는 가지의
높이
노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨
트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨
특징
사이클 존재 X (사이클 만들어지면 ➡️ 그래프)
모든 노드는 자료형으로 표현 가능
루트에서 한 노드로 가는 경로는 유일한 경로 뿐
노드의 개수가 N개면, 간선은 N-1개 가짐
트리의 종류
이진 트리 (Binary Tree) : 최대 2개의 자식을 가질 수 있는 트리
포화 이진 트리 : 리프 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리
완전 이진 트리 : 모든 노드들이 왼쪽 자식부터 차근차근 채워진 노드
높이 균형 트리 : 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이나지 않는 트리출처 : https://velog.io/@april_5/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%ACbinary-tree
이진 탐색트리 (이진 탐색 + 연결리스트, BST) : 이진 트리에 탐색을 위한 조건을 추가하여 정리한 자료구조출처 : https://gyoogle.dev/blog/computer-science/data-structure/Binary%20Search%20Tree.html
특징
각 노드의 자식이 2개 이하
각 노드의 왼쪽 자식 < 부모, 오른쪽 자식 > 부모
중복된 노드 X : 검색 목적 자료구조인데 중복이 있으면 검색 속도를 느리게 하기 때문
중위순회 방식 (왼쪽- 루트 - 오른쪽)
시간 복잡도
균등 트리 : 노드 개수가 N개일 때 O(logN)
편향 트리 : 노드 개수가 N개일 때 O(N) 편향된 트리(정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음)는 시간복잡도가 O(N)이므로 트리를 사용할 이유가 사라짐 → 이를 바로 잡도록 도와주는 개선된 트리가 AVL Tree, RedBlack Tree
트리 순회 방식출처 : https://gyoogle.dev/blog/computer-science/data-structure/Tree.html
전위 순회 : 각 루트를 순차적으로 먼저 방문하는 방식 [루트 ➡️ 왼쪽 자식 ➡️ 오른쪽 자식] ex)1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 13 → 7 → 14
중위 순회 : 왼쪽 하위 트리를 방문 후 루트를 방문하는 방식 [왼쪽 자식➡️ 루트➡️ 오른쪽 자식] ex)8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7
레벨 순회 : 왼쪽 하위 트리부터 하위를 모두 방문 후 루트를 방문하는 방식 [왼쪽 자식 ➡️ 오른쪽 자식 ➡️루트] ex)8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1
레벨 순회 : 루트부터 계층별로 방문하는 방식 ex)1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14
AVL 트리
: 이진 탐색 트리가 한쪽으로 쏠릴 경우 트리에서 특정 값 찾으려면 O(N)의 시간이 필요 ➡️ 성능 안좋음
: 이런 단점 극복하기 위한 자료구조
특징
이진 탐색 트리의 속성 가짐
왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1
높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄임
삽입, 검색, 삭제의 시간 복잡도가 O(log N)
B 트리
: 트리 자료구조의 일종
: 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조
특징
노드에 2개 이상의 데이터가 들어갈 수 있으며, 항상 정렬된 상태
특정 노드의 데이터가 k개라면, 자식 노드의 개수는 k+1
특정 노드의 왼쪽 서브 트리는 특정 노드의 key보다 작은 값들로, 오른쪽 서브 트리는 큰 값들로 구성
모든 리프 노드들이 같은 레벨에 존재
B+ 트리
: 데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드가 추가로 있음
: 리프 노드는 연결리스트의 형태를 띄어 선형 검색 가능
: 아주 작은 시간복잡도에서 검색 수행 가능
: 키 값의 삭제는 리프 노드에서만 수행
: 성능 = O(log n)
Red-Black 트리
: 자가 균형 이진 탐색 트리
특징
루트 노드는 검은색
모든 리프 노드는 검은색
새로운 노드는 항상 빨간색 출처 : https://code-lab1.tistory.com/62
힙 (Heap)
: 완전 이진 트리의 일종
: 우선순위 큐를 위해 만들어진 자료구조 : 삽입 - O(logn) , 삭제 - O(logn)
정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현 (Vi, Vj) == (Vj, Vi) ➡️ 같은 간선
정점이 n개 일 때 최대 간선 수 : n(n-1)/2
방향 그래프 (directed graph)
간선에 방향이 있는 그래프
정점 Vi와 정점 Vj를 연결하는 간선을 <Vi, Vj>로 표현 Vi : 꼬리 (tail), Vj : 머리 (head) <Vi, Vj> != <Vj, Vi>➡️ 다른 간선
그래프의 제한 사항
자기 간선 (self edge) / 자기 루프 (self loop) X
동일 간선의 중복 없음 (단, 다중 그래프는 제한 X)
완전 그래프 (Complete graph)
각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프
정점이 n개인 무방향 그래프에서 최대 간선 수 : n(n-1)/2개
정점이 n개인 방향 그래프의 최대 간선 수 : n(n-1)개
부분 그래프 (Subgraph)
원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프
가중치 그래프 (Weighted graph)
정점을 연결하는 간선에 가중치를 할당한 그래프
그래프 표현법
인접 행렬 (Adjacency Matrix)
G = (V,E)는 정점의 수가 n (n >= 1)인 그래프
인접 행렬 : n*n의 2차원 그래프
수행시간 : 최소 O(n^2)
희소 그래프 : O(e+n)
단점 1) 항상 n*n개의 메모리 사용 2) 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비 발생
인접 리스트 (Adjacency Lists)
각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트 ➡️ 인접 행렬의 각 행을 연결 리스트로!
각 정점의 차수만큼 노드를 연결 (오름차순)
n개의 정점, e개의 간선
무방향 그래프 : 배열의 크기 n, 노드의 수 2e
방향 그래프 : 배열의 크기 n, 노드의 수 e
인접 행렬 vs 인접 리스트출처 : https://wjjeong.tistory.com/38 📌M = Node의 개수, E = Edge의 전체 개수
인접리스트
인접행렬
노드 추가 : O(1)
노드 삭제 :O(M+E)
Edge 추가 : O(1)
Edge 삭제 :O(E)
노드 추가 : O(M^2)
노드 삭제 :O(M^2)
Edge 추가 : O(1)
Edge 삭제 :O(1)
그래프의 기본 연산
그래프 순회, 그래프 탐색 : 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산
그래프 탐색 방법
깊이 우선 탐색 (depth first search : DFS) 1) 시작 정점 v 방문 2) v의 인접 정점 중 아직 방문하지 않은 정점 w가 있으면 정점 v를 스택에 push하고 정점 w 방문 3) 방문하지 않은 정점이 없으면 탐색의 방향을 바꾸기 위해 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 반복 4) 스택이 공백이 될 때까지 반복
인접리스트로 구현
인접리스트의 노드들의 탐색을 끝내는 시간 : O(e)
O(|V| + |E|) = O(|V|) + O(|E|)
인접행렬로 구현
v에 인접한 모든 정점들을 찾는데 O(n)의 시간
최대 n개의 vertex를 방문해야 하므로 O(n^2)
너비 우선 탐색 (breath first seach : BFS) 1) 시작 정점 v 방문 2) v의 인접 정점 중 아직 방문하지 않은 정점을 차례대로 방문 3) 2번이 끝났다면 큐에 있는 정점을 꺼내 2번 실행
전체 시간 : O(n^2)
인접리스트로 표현 : O(e) [O(1) ~ O(n^2)]
최소 비용 신장 트리
신장 트리 : G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리
깊이 우선 신장 트리 : DFS를 이용하여 생성
너비 우선 신장 트리 : BFS를 이용하여 생성
최소부분 그래프
n-1개의 간선 가짐 (사이클 X)
최소 비용 신장 트리 : 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리
최소 비용 신장 트리를 만드는 알고리즘
Kruskal - 간선 추가/삭제 (간선에 집중) 1) 가중치가 가장 낮은 간선을 하나씩 추가 2) 가중치가 가장 높은 간선을 하나씩 제거
위의 과정 반복하다가 최소 비용 신장 트리 구축되면 종료
간선을 추가할 경우, 이미 포함된 간선들과 사이클을 형성하지 않는 간선만 추가!
Prim - 간선을 연결하면서 트리를 확장 (정점에 집중) 1) 그래프에서 시작 정점 선택 2) 선택한 정점에 부속된 간선들 중에서 가중치가 가장 작은 간선을 연결하여 트리 확장 3) 이전에 선택한 정점과 확장된 정점에 부속된 모든 간선 중에서 가중치가 가장 작은 간선 삽입 (사이클 형성하는 경우 pass) 4) 그래프에 n-1개의 간선이 포함될 때까지 추가 단계 반복
탐욕 알고리즘 (Greedy Algorithm)
매순간 최적의 해를 단계별로 도출
각 단계에서는 판단 기준에 따라 최상의 결정을 선택 (단, 번복 불가)
최종적인 최적해에 도달
그리디 알고리즘이 잘 작동하는 조건
탐욕스런 선택 조건 : 앞의 선택이 이후의 선택에 영향 X
최적 부분 구조 조건 : 문제에 대한 최적해가 부분 문제에 대해서도 최적해
최단 경로
: 가중치 방향 그래프에서 출발지에서 도착지까지 경로의 간선 가중치 합이 최소인 경우
최단 경로 구하는 알고리즘
다익스트라 1) 아직 방문하지 않은 정점 중 출발지로부터 가장 거리가 짧은 정점 방문 2) 해당 정점을 거쳐 갈 수 있는 정점의 거리가 이전 기록한 값보다 적으면 갱신
하나의 정점에서 출발하는 최대 거리를 구함 (출발지만 정함)
음수 가중치 X
인접 행렬로 표현된 그래프의 경우 O(n^2)
Dist[w] = min {Dist[w], Dist[u] + weight[u, w]}
벨만 포드 dist는 출발지로부터 최단거리를 기록하는 1차원 배열 출발지는 0, 나머지는 INF로 초기화 1) 간선 m개를 하나씩 살펴봄 2) dist[v] = min(1️⃣, 2️⃣) 1️⃣ : 지금까지 계산한 v에 도착하는 최단거리 (dist[v]) 2️⃣ : w에 도착하는 최단거리 + w에서 v로 가는 간선의 가중치 (dist[w] + cost(w, v))
