유블로그

- 백트래킹 여러 가지 선택지들이 존재하는 상황에서 한 가지 선택 선택하면 새로운 선택지들 집합이 생성됨 선택들을 반복하며 최종 상태에 도달 - 백트래킹과 완전탐색(DFS)의 차이 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.(가지치기) 완전 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단한다. N! 가지의 경우의 수 같이 완전 탐색 하기 힘들 때 좋다. 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 최악의 경우에는 지수함수 시간을 요하므로 처리 불가능할 수 있다.

순서를 가진 데이터의 집합을 가리키는 추상자료형 동일한 데이터를 가지고 있어도 상관없다. 종류 배열을 기반으로 구현된 리스트인 순차리스트 메모리의 동적할당(JVM의 객체 생성)을 기반으로 구현된 리스트인 연결리스트 1차원 배열에 항목들을 순서대로 저장한다. 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열로 만들 수도 있다. 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다. 문제점 단순 배열을 이용해 순차리스트르 구현해 사용하는 경우, 자료의 삽입/삭제 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요하다. 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날수록 작업에 소요되는 시간이 크게 증가한다. 배열의 크기가 정해..

최적해를 구하는 데 사용. 하지만 최적해를 반드시 구한다는 보장이 없다. 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식. 선택 시점 때 최적이어도 최종해가 최적이라고는 할 수 없다.

java.lang.Comparable int compareTo(T other) 자신과 인자로 전달 받는 타 원소와 비교하여 정수 리턴 a.compareTo(b) 음수 : a가 더 작다. 그대로 0 : a = b 양수 : b 가 더 크다. 자리 바꾼다 오름차순 정렬 됨 class A implements Comparable { int num; A(int num){ this.num = num; } @Override public int compareTo(A o){ return this.num - o.num;// 정렬 기준은 하나 밖에 안됨. // 양수와 음수가 섞여있을 때 오버플로우 방지하려면 // return Integer.compare(this.num, o.num); 하면 됨 } } public static..

그래프에서 최소 비용 문제 모든 정점 연결 간선들 가중치 합이 최소가 되는 트리 두 정점 사이 최소 비용 경로 찾기 신장 트리 : n개 정점 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 : 서로소 집합 사용 간선을 하나씩 선택해서 MST 를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬(최대신장트리는 내림차순) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택(union 연산 실패 상황) n-1 개의 간선이 선택될 때까지 2를 반복 ..

.

너비 우선 탐색 루트 노드가 자식 노드들을 먼저 차례로 방문후, 방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식 노드들을 차례로 방문하는 방식 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 '큐' 를 활용함 BFS() 큐 생성 루트 v를 큐에 삽입 while(큐가 비어 있지 않은 경우) { t = 큐의 첫 번쨰 원소 반환 t 방문 for(t와 연결된 모든 간선에 대해) { u = t의 자식 노드 u를 큐에 삽입 } } end BFS() 깊이 우선 탐색 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색..

비선형, 계층형 최상위 노드 = Root 트리는 부트리로 구성 edge - 노드를 연결하는 선. 형제 노드 - 같은 부모의 자식 노드 조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 서브 트리 - 부모 노드와 간선을 끊었을 때 생성되는 트리 자손 노드 - 서브 트리에 있는 하위 레벨 노드들 노드의 차수 : 노드에 연결된 자식 노드 수 트리의 차수 : 모든 노드들 차수 중 가장 큰 값 노드의 높이 : 루트에서 노드에 이르는 간선 수. 노드의 레벨과 같음 트리의 높이 : 트리에 있는 노드 높이 중에서 가장 큰 값. 최대 레벨 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리 각 노드가 자식 노드를 최대 2개까지 가질 수 있음 레벨 i에서 노드 ..