puravida

1. 위상 정렬 ① 비순환 방향 그래프 (공정이랑 비슷하네) - 방향 그래프이면서 사이클이 없는 그래프 ② 위상 정렬 - 처리해야 할 여러가지 일들이 있고, 이들 사이의 선후 관계가 있으면 이를 유향 그래프로 표현 가능 - 유향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 - 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있음 - 위상 정렬은 사이클이 있어서는 안됨 - 위상 정렬 알고리즘이란? 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 - ex) 대학의 선수과목 => 각 업무를 수행하기 위한 순서를 제공! - 조건 : 사이클이 없는 유향 그래프 - 진입 간선 : 유향 그래프에서 한 정점으로 들..

1. 기본 계수법칙 ① 기본 계수법칙 - 어떤 사건이 일어나는 방법이 전부 m가지일 때, 그 사건이 일어나는 '경우의 수'를 m가지라고 함. - 경우의 수에는 곱의 법칙과 합의 법칙이 있음 ② 곱의 법칙 - 사건 A,B가 동시에 발생할 경우의 수 - 하나의 작업이 n개의 연속된 작업으로 이루어진 경우에 사용(그리고, ~이고) - 두 사건 A,B가 일어날 경우의 수가 N(A) = n, N(B) = m일때, 동시에 일어날 경우의 수는 nXm임. - 4비트로 표현할 수 있는 이진수는 몇개인가? 2^4 = 16 ③ 합의 법칙 - 사건 A또는 B가 발생할 경우의 수 - 작업들이 서로 독립적인 경우 적용(또는, ~이거나) 2. 순열 ① 순열 - 물체의 집합에서 일정한 개수를 선택하는 문제를 풀 때 사용할 수 있으며..

1. 최소 신장 트리 ① 신장 트리의 조건 - 모든 정점을 포함 - 모든 정점은 직,간접적으로 연결되어야 함. - 트리의 속성 만족해야 함. ② 최소 신장 트리 - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리. - 프림 알고리즘, 크루스칼 알고리즘이 대표적 - 신장 트리의 비용을 최소로 만드는 것은 실제 응용 분야에서 경제성이나 효율성 등을 고려할 때 매우 중요한 문제. - 본사와 각 지역에 있는 지점의 통신 네트워크를 구성하고자 할 때 네트워크를 어떤 방법으로 구성하느냐에 따라 통신 비용이 달라질 수 있음. - 정의 : 그래프 G의 모든 변의 가중치 합을 총 가중치라고 했을 때, G의 신장 트리 중 총 가중치가 가장 작은 신장 트리를 최소 신장 트리라고 함. 2...

1. 람다식이란? 함수형 프로그래밍이란 함수를 정의하고 이 함수를 데이터 처리부로 보내 데이터를 처리하는 기법 데이터 처리부는 데이터만 가지고 있을 뿐, 처리하는 방법이 정해져 있지 않아 외부에서 제공된 함수에 의존한다. 외부에서 제공되는 함수가 람다식이다. 람다식은 익명 클래스 안에 있는 익명 메소드이다. 따라서, 람다식 자체가 메소드이면서 인터페이스를 구현한 객체가 된다. -> 인터페이스의 유일한 추상메소드를 구현한다. 람다식을 사용하면 크게 함수형 인터페이스, 데이터 처리부(메소드 정의), 메소드 호출하여 람다식을 정의하여 사용하는 부분으로 나뉜다. ​ 2. 매개변수가 없는 람다식 예제 package Chapter10; public class ButtonExample { public static v..

1. Map 컬렉션 - Map 컬렉션은 key와 value로 구성된 앤트리 객체 저장. - key는 중복저장할 수 없지만, 값은 중복저장될 수 있어서 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. - Map.of() 사용하면 immutable이기 때문에 추가, 수정, 삭제 불가능하다. ​ 2. HashMap - HashMap은 key로 사용할 객체가 haseCode() 메소드의 리턴값이 같고, equals() 메소드가 true를 리턴할 경우, 동일 key로 보고 중복 저장을 허용하지 않는다. - 같은 객체인지 판단할 때 순서가 hashCode() 메소드 -> equals() 메소드 이기 때문에 객체 비교에 대하여 재정의 하려면 hashCode()와 eqaul..

제네릭 타입 1. 정의 - 제너릭 : 타입을 결정하지 않고 클래스를 설계 - >사용할 때 구체적인 타입을 결정함! - >결정되지 않은 타입을 파라미터로 가지는 클래스와 인터페이스를 제네릭 타입이라고 함. ​ 2. 제네릭 타입 의미 - 하나의 코드를 다양한 타입의 객체에 재사용하는 객체 지향 기법 ​ 3. 제네릭 타입의 장점 - 컴파일 할 때 타입을 점검하기 때문에 실행 도중 발생할 오류 사전 방지! ​ - 우선 아무거나 담게하면 그걸 다시 밖으로 꺼낼 때는 어떤 타입인지 모르게됨. > 꺼낼 때 type check를 해야함. > Generic 사용하면 사용할 때 타입에 대한 제한을 걸어 두기에 type check 안해도 됨. ​ - 제네릭 쓰면 불필요한 타입 변환이 없어서 프로그램 성능 향상된다. ​ cf..

1. 최소 신장 트리 ① 신장 트리 - 그래프 G의 신장 트리는 정점 집합 V를 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것! - 너비우선 트리와 깊이 우선 트리도 신장 트리임 - 간선들의 가중치를 갖는 그래프에서 간선 가충치의 합이 가장 작은 트리를 최소 신장 트리라고함. ② 최소 신장 트리 - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 - 프림 알고리즘/ 크루스칼 알고리즘 - 조건 : 무향 연결 그래프(모든 정점 간에 경로가 존재하는 그래프) 2. 프림 알고리즘(힙 이용) ①프림 알고리즘 - 집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워나감 - 연결된 정점들과 연결된 모든 간선들 중 가중치가 가장 작은 간선 선택 ② 프림 알고..

1. 트리 탐색 ① 트리 순회 - 트리 내의 모든 노드를 오직 한 번씩 방문하는 방법 -> 전위 순회/ 중위 순회/후위 순회 ②전위 순회 ③ 중위 순회 ④ 후위 순회 2. 너비 우선 탐색 (큐 이용) ① 그래프 순회 - 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산 - 트리 순회와 달리 일반적인 그래프 순회에서는각 정점들을 한 번 이상 방문하는 경우도 있음 - 그래프에서는 다른 모든 정점들을 연결시켜주는 트리의 루트 같은 정점이 존재하지 않을 수도 있음. ② 그래프에서 모든 정점 방문하기 - 임의의 정점 선택하여 탐색하는 방법보다는 시작점을 기준으로 일정한 방향으로 탐색하는 것이 효율적 - 너비우선 탐색 / 깊이 우선 탐색 ③ 너비 우선 탐색 - 노드들을 동심원의 형태..

1. 이진 트리 순회의 개념 ① 개념 - 모든 원소를 빠트리거나 중복하지 않고 처리하는 연산 2. 이진 트리 순회 ① 이진 트리 순회 - 이진트리가 순환적으로 정의되어 있으므로, 순회작업도 서브 트리에 대해 순환적으로 반복하여 완성함. ② 전위 순회 - D -> L ->R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행 ③ 중위 순회 - L-> D ->R 순서로, 현재 노드를 방문하는 작업 D를 작업 L과 작업 D 중간에 수행 ④ 후위 순회 - L-R-D 순서로 현재 노드를 방문하는 D작업을 가장 나중에 수행 3. 이진 트리 순회의 응용 ① 이진 트리 순회의 응용 프로그램 - 컴퓨터 폴더 구조가 이진 트리 구조인 경우, 각 폴더 순회하면서 용량 계산하면 내 컴퓨터의 전체 용량 계산 가능..

1. 트리의 개념 ① 트리 - 원소들 간에 1:n 관계를 가지는 비선형 자료구조 - 원소들 간에 계층관계를 가지는 계층형 자료구 ② 트리의 구조와 구성 요소 - 서브 트리(Subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리로 각 노드는 자식노드의 개수 만큼 서브 트리를 가짐. - 노드의 차수 : 노드에 연결된 자식 노드의 수 - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 - 높이 -> 노드의 높이 : 루트에서 노드에 이르는 간선의 수 -> 트리의 높이: 트리에 있는 노드 높이 중에서 가장 큰 값이며 최대 레 ③ 포리스트(Forest) : 서브트리의 집합 - 트리 A에서 노드 A를 제거하면 A의 자식 노드 B,C,D에 대한 서브트리가 생기고, 이들의 집합이 포리스트 2..