본문 바로가기

전체 글115

[자료구조] 최단 경로 최단경로: 하나의 정점에서 다른 모든 정점까지(Single-source Shortest Path Problem) 시작점 v에서 G의 나머지 모든 정점까지의 최단 경로 시작점 v와 목표점 t까지의 경로 중, 경로를 구성하는 간선들의 가중치 합이 최소가 되는 경로 방향 그래프 G = (V, E), weight[l, j] >=0 Dijkstra 최단 경로 알고리즘 Dijkstra 최단 경로 알고리즘의 원리 S: 최단 경로가 발견된 정점들의 집합 weight[i, j]: 간선 의 가중치 Dist[i]: S에 속하지 않은 i에 대해서, v에서 시작하여 S에 있는 정점만을 거쳐 정점 i에 이르는 최단 경로의 길이 처음 S에는 시작점 v만 포함, Dist[v] = 0 가장 최근에 S에 첨가된 노드를 u라고 하자. u.. 2023. 6. 2.
[JAVA] 컬렉션과 제네릭 컬렉션 배열이 가진 고정 크기의 단점을 극복하기 위해 객체들을 쉽게 삽입, 삭제, 검색할 수 있는 가변 크기의 컨테이너이다. 특징 컬렉션은 제네릭이라는 기법으로 만들어졌다. 컬렉션의 요소는 객체들만 가능하다. Vector 배열을 가변 크기로 다룰 수 있게 하고, 객체의 삽입, 삭제, 이동이 쉽도록 구성한 컬렉션 클래스이다. 벡터를 생성할 때, Vector의 E에 요소로 사용할 타입을 지정해야 한다. Vector v = new Vector(); 문자열만 다루는 벡터는 다음과 같이 생성할 수 있다. Vector stringVector; stringVector = new Vector(); add() 메소드를 이용하면 벡터의 끝이나 중간에 요소를 삽입할 수 있다. v.add(Integer.valueOf(5));.. 2023. 5. 31.
[JAVA] String 클래스 String 클래스 java.lang 패키지에 포함된 클래스로서 String 클래스는 문자열을 나타낸다. // 스트링 리터럴 String s1 = "abcd"; // 스트링 객체 char data[] = {'a', 'b', 'c', 'd'}; String s2 = new String(data); String s3 = new String("abcd"); 스트링 리터럴: 자바 내부에서 리터럴 테이블로 특별히 관리하여 동일한 리터럴을 공유시킨다. new String(): new를 이용하여 생성되는 다른 객체와 동일하게 힙 메모리에 생성된다. 스트링 객체는 수정이 불가능하다. 다음 코드의 실행 결과 t는 "HelloJava"를 가리틴다. 하지만 s는 변함없이 "Hello" 그대로이다. String s = new.. 2023. 5. 31.
[JAVA] Wrapper 클래스 Wrapper 클래스 int, char, double 등 8개의 기본 타입을 객체로 다루기 위해 JDK에 만들어진 8개의 클래스를 통칭하여 Wrapper 클래스라고 한다. Byte, Short, Integer, Long, Character, Double, Float, Boolean 클래스가 기본 타입에 해당되는 값을 객체로 다룰 수 있게 하는 Wrapper 클래스이다. 기본 타입의 값을 객체로 만들어 사용할 수 있도록 Wrapper 클래스를 제공한다. 객체 생성 Wrapper 객체는 기본 타입의 값을 인자로 하여 다음 예와 같이 정적 메소드인 valueOf()를 호출하여 생성한다. Integer i = Integer.valueOf(10); Character c = Character.valueOf('c').. 2023. 5. 31.
[JAVA] Object 클래스 Object 클래스 생성과 특징 Object는 java.lang 패키지에 속한 클래스이며, 모든 클래스에 강제로 상속된다. Object만이 아무 클래스도 상속받지 않는 유일한 클래스로 계층 구조 상 최상위 클래스이다. 객체 속성 class Point{ private int x, int y; public Point(int x, int y){ this.x = x; this.y = y; } } public class ObjectPropertyEx{ public static void print(Object obj){ System.out.println(obj.getClass().getName()); System.out.println(obj.hashCode()); System.out.println(obj.toStr.. 2023. 5. 31.
[JAVA] 메소드 오버라이딩(Method Overriding) 메소드 오버라이딩(Method Overriding) 메소드 오버라이딩은 슈퍼 클래스와 서브 클래스의 메소드 사이에 발생하는 관계로서, 슈퍼 클래스에서 선언된 메소드와 같은 이름, 같은 리턴 타입, 같은 매개 변수 리스트를 갖는 메소드를 서브 클래스에서 재작성하는 것이다. 동적 바인딩 슈퍼 클래스의 메소드를 무시하고 서브 클래스에서 오버라이딩 된 메소드가 무조건 실행되도록 처리하는 것을 동적 바인딩이라고 한다. 제약 사항 1. 슈퍼 클래스의 메소드와 동일한 원형으로 작성한다. 슈퍼 클래스의 메소드와 동일한 이름, 동일한 매개변수 타입과 개수, 동일한 리턴 타입을 갖는 메소드를 작성해야 한다. 2. 슈퍼 클래스 메소드의 접근 지정자보다 접근의 범위를 좁여 오버라이딩할 수 없다. 슈퍼 클래스에서 protect.. 2023. 5. 30.
[자료구조] 최소 비용 신장 트리(Minimum-cost Spanning Tree) 신장 트리(Spanning Tree) G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리이다. 최소 비용 신장 트리(Minimum-cost Spanning Tree) 최소 비용 신장 트리란 최저의 비용을 갖는 신장 트리이다. 연결 무방향 그래프에서 최소 비용 신장 트리를 구하기 위해서는 세 가지 상이한 알고리즘을 사용할 수 있다. 모두 갈망법(greedy method)이라고 하는 설계 전략을 사용하고 있다. Kruskal 알고리즘 Prim 알고리즘 Solin 알고리즘 그래프 내에 있는 간선들만을 사용해야 한다. 정확하게 n-1개의 간선만을 사용해야 한다. 사이클을 생성하는 간선을 사용해서는 안 된다. 탐욕 알고리즘(Greedy Algorithm) 매 순간 최적의 해를 단계별로 도출한다. 각 단계에서.. 2023. 5. 29.
[자료구조] 그래프 순회(Graph Traversal) 그래프 순회(Graph Traversal) 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산 깊이 우선 탐색(DFS: depth first search) 1. 시작 정점 v를 결정하여 방문한다. 2. 정점 v에 인접한 정점 중에서 (a) 방문하지 않은 정점 w가 있으면, 정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 v로 하여 다시 2번을 반복한다. (b) 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 2번을 반복한다. 3. 스택이 공백이 될 떄까지 2번을 반복한다. ❗️시간 복잡도❗️ 인접 리스트의 노드들의 탐색을 끝내는 시간 O(e) O(|V| + |E|) = O(|V|) + O.. 2023. 5. 29.
[자료구조] 그래프(Graph) 그래프(Graph) 선형 자료구조나 트리 자료구조로 표현하기 어려운 관계를 가지는 원소들을 표현하기 위한 자료구조 그래프 G는 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다. V는 그래프에 있는 정점들의 집합 E는 정점을 연결하는 간선들의 집합 무방향 그래프(Undirected Graph) 두 정점을 연결하는 간선의 방향이 없는 그래프이다. 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현한다. 이때 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미한다. 위의 그래프를 집합으로 표현하면 다음과 같다. V(G1) = {A, B, C, D} E(G1) = {(A,B), (A,D), (B,C), (B,D), (C,D)} V(G2) = {A, B, C} V(G.. 2023. 5. 29.
[자료구조] 이원 탐색 트리(Binary Search Tree) 사전(Dictionary) 사전(Dictionary)은 쌍의 집합으로서 각 쌍은 키와 이에 연관된 원소로 구성된다. 같은 key를 갖는 두 쌍은 없다고 가정한다. template class Dictionary{ public: virtual bool IsEmpty() const = 0; virtual pair *Get(const k&) const = 0; virtual void Insert(const pair&) = 0; virtual void Delete(const K&) = 0; }; 키와 원소의 데이터 값은 각각 K와 E이다. 이진 탐색 트리(Binary Search Tree) 모든 원소는 서로 다른 유일한 키를 갖는다. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 오른쪽 서브 트리.. 2023. 5. 29.
[자료구조] 힙(Heap) 우선 순위 큐(Priority Queue) 우선순위 큐에서는 우선순위가 가장 높은(또는 가장 낮은) 원소를 먼저 삭제한다. 또 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입할 수 있다. template class MaxPQ{ public: virtual ~MaxPQ(){ }// 가상 파괴자 virtual bool IsEmpty() const = 0;// 우선순위 큐가 공백이면 true 반환 virtual const T& Top() const = 0;// 최대 원소에 대한 참조를 반환 virtual void Push(const T&) = 0;//우선순위 큐에 원소를 삽입 virtual void Pop() = 0;// 최대 우선순위를 가진 원소 삭제 }; 시간 복잡도 IsEmpty(): O(1).. 2023. 5. 29.
[자료구조] 트리(Tree) 트리(Tree) 트리(Tree)는 원소들 간에 1 : N 관계를 가지는 비선형 자료구조이다. 한 개 이상의 노드(node)로 이루어진 유한 집합으로서 노드 중에는 루트(root)라고 하는 노드가 하나 있고 나머지 노드들은 n(>=0)개의 분리집합 T1, ,,, Tn으로 분할될 수 있다. 여기서 T1, ,,, Tn은 각각 하나의 트리이며 루트의 서브트리(subtree)라고 한다. 한 노드의 서브트리의 수를 그 노드의 차수(degree)라고 한다. 예를 들어 트리의 구조가 다음과 같을 때, A의 차수는 3이고, C의 차수는 1, L의 차수는 0이다. 차수가 0인 노드를 리프(leaf) 또는 단말 노드(terminal node)라 한다. 그 외의 나머지 노드들은 비단말 노드(nonterminal node)라 .. 2023. 5. 29.

티스토리툴바