그래프 순회 위상 정렬 유항 그래프이고, 사이클이 없어야 한다. 위상정렬 코드
네트워크 유량 문제
그래프 네트워크 유량 문제 그래프에서 각 노드들 간의 용량(Capacity)가 정의되어 있을 때, 시작점(Source)에서 끝점(Target)까지 흐를 수 있는 최대 유량 구하는 문제 용어 소스(S, source): 시작점 싱크(T, sink): 끝점 정점(Vertex): 유량이 모이는 위치 ...
Strongly Connected Component(강연결요소)
그래프 SCC(강연결요소) Strongly Connected Component A에서 B로 갈 수 있다면, B에서 A로도 갈 수 있는 성질 방향성이 존재하는 유향 그래프에서 모든 정점이 다른 모든 정점들에 대하여 방문할 수 있는 경우 증명 방법 그래프 G에서 한 정점 V를 선택 V에서 DFS를 통해 모...
최단 경로 문제
최단 경로 문제 다익스트라 알고리즘 시작점부터 출발해 목표점까지의 거리 구하기 구하는 방법 우선순위 큐 사용 다익스트라 코드 All-Pairs Shortest Paths 모든 쌍에 대하여 최단 경로 구하는 알고리즘 증명 방법 다익스트라 알고리즘을 n번 호출(음의 가중치X)...
객체지향 프로그래밍
객체지향 프로그래밍 다양한 연산을 수행하는 계산기를 여러 개 구현하고자 할 때, 여러 개의 계산기를 각각 하나씩 세세하게 구현하는 것은 매우 비효율적이다. 따라서, 계산기들의 공통 속성을 뽑아내어 클래스로 만든 후 계산기의 개수가 추가될 때마다 객체를 손쉽게 만들어 내기 위해서 객체지향 프로그래밍이 필요하다. 객체 class Animal{ } p...
다형성
다형성 하나의 객체가 여러개의 자료형 타입을 가질 수 있는 것 인터페이스에서 사용한 코드에 추가로 ‘경비원’ 클래스를 형성, 경비원 클래스는 동물을 짖게(barkAnimal) 하여 건물을 지킨다. class Bouncer { void barkAnimal(Animal animal) { if (animal instanceo...
추상화
추상화 인터페이스 필요한 이유 난 동물원의 사육사이다. 육식동물이 들어오면 난 먹이를 던져준다. 호랑이가 오면 사과를 던져준다. 사자가 오면 바나나를 던져준다. 위 케이스를 코드로 구현 class Animal { String name; void setName(String name) { this.name = n...
상속과 생성자
클래스 상속 키워드 extends 사용 class Person { String name; void setName(String name) { this.name = name; } } class Woman extends Person { void sleep() { System.out.prin...