728x90 반응형 2019/0446 프림 알고리즘 최소 비용 신장 트리(Minimum Spanning Tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리이다. MST를 이용하면, 도로 건설이나 전기 회로 설계, 통신 인프라 구축 등의 문제를 가장 효율적으로 처리할 수 있다. 프림 알고리즘은 시작 정점에서부터 출발해서 신장 트리 집합을 단계적으로 확장해 나가는 방법 동작 순서는 다음과 같다. 1. 시작 단계에서는 시작 정점만이 MST(최소 비용 신장 트리) 집합에 포함된다. 2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 3. 위의 과정을 트리가 (N-1)개 의 간선을 가질 때까지 반복한다. 프림 알고리즘의 시간 복잡도 인접 행렬과 최소 비용값들이 들어가 있는 배.. 2019. 4. 26. Union-Find(합집합 찾기) Union-Find 는 대표적인 그래프 알고리즘이다. Disjoint-Set이라고 해서 서로소 집합 알고리즘이라고도 부른다. 여러 개의 노드가 존재할 때, 두 개의 노드를 선택해서 현재 이 두 노드가 서로 같은 그래프에 속하는 지 판별하는 알고리즘 처음에 여러 개의 노드가 서로 자유롭게 존재한다. 이와 같이 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 첫 번째 행은 '노드 번호'를 의미하고 두 번째 행은 '부모 노드 번호'를 의미한다. 즉, 자신이 어떠한 부모에 포함되어 있는지를 의미한다. 이와 같이 1과 2가 연결되었다고 한다. 이러한 '연결성'을 우리가 프로그래밍 언어로 어떻게 표현할 수 있을 지에 대한 내용이 바로 Union-Find라고 생각하자. 2번째 인덱스의 값에 '.. 2019. 4. 26. 크루스칼 알고리즘(Kruskal Algorithm) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘 중 하나. 흔히, 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 한다면 적용되는 알고리즘이다. 이 그래프는 노드의 갯수가 7개 이고 간선의 갯수가 11개이다. "크루스칼 알고리즘의 핵심 개념은 간선을 거리가 짧은 순서대로 그래프에 포함시켜본다." 가장 먼저 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차례대로 그래프에 포함 시킨다. 다음의 알고리즘에 맞게 그래프를 연결하면 가장 적은 비용으로 모든 노드를 연결한 그래프인 '최소 비용 신장 트리'가 만들어진다. 1. 정렬된 순서에 맞게 그래프에 포함시킨다. 2. 포함시키기 .. 2019. 4. 26. 플로이드 와샬(Floyd Warshall) 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용한다. "거쳐가는 정점을 기준으로 최단 거리를 구하는 것" 위의 그래프에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열에 출력하면 이 테이블이 의미하는 것은 현재까지 계산된 최소 비용이다. 이러한 이차원 배열을 반복적으로 갱신하여 최종적으로 모든 최소 비용을 구해야 한다. 반복의 기준이 '거쳐가는 정점' 인 것이다. 노드 1을 거쳐가는 경우 노드 1을 거쳐가는 경우는 위와 같이 6가지 공간만 갱신해준다. 즉, 예를 들어 2에서 3으로 가는 경우에는 2에서 3으로 가는 경우의 비용과 (2에서 1로 가는 경우) + (1에서 3으로 가는 경우)의 비용을 더한 값을 비교한다. 더 작은 값으로 교체한다. 2. 노드 2를.. 2019. 4. 26. 객체 지향 vs 절차 지향 객체지향 기법이란? 기계적인 부품들을 조립하여 제품을 만들듯이 소프트웨어를 개발할 때에도 객체들을 조립해서 작성할 수 있도록 하는 기법이다. 장점으로는? 소프트웨어의 재사용 및 확장이 용이 유지보수가 쉽다. 구성요소로는? 객체(Object), 클래스(Class), 메시지(Message)가 있다. 객체란? 실제로 존재하는 구체적인 대상 또는 시스템 객체는 다른 객체와 구분되며 유일하다. 객체는 상태 (Attribute)와 행위(Method)를 가진다. 데이터와 데이터를 처리하는 함수를 묶어 놓은 하나의 소프트웨어 모듈이다. 데이터는 객체가 가지고 있는 정보로 속성이나 상태 분류 등을 나타낸다. 속성으로는 상태, 변수, 상수, 자료구조라고도 한다. 함수는 객체가 수행하는 기능으로 객체가 갖는 데이터를 처리하.. 2019. 4. 25. 트랜잭션 트랜잭션(Transaction)이란, 질의(query)를 하나의 묶음 처리해서 만약 중간에 실행이 중단되면 처음부터 다시 실행하는 Rollback을 수행하고, 오류없이 실행을 마치면 Commit을 하는 실행 단위 한 번 질의가 실행되면 질의가 모두 수행되거나 모두 수행되지 않는 작업수행의 논리적 단위이다. 예를 들어, 친구에게 인터넷 뱅킹으로 만원을 송금한다. 나의 계좌에서 만원을 줄이고, 친구의 계좌에 만원을 증가시켜야 한다. 오류로 인하여 나의 계좌에서는 만원이 줄었는데, 친구의 계좌에서는 증가되지 않으명 어떻게 될까? 이러한 경우가 생기지 않게 하기 위해 중간에 오류가 발생하면 다시 처음부터 송금하도록 하는 것이 바로 Rollback 이다. 즉 송금 과정 전체를 하나의 트랜잭션이라고 볼 수 있다. .. 2019. 4. 25. 싱글턴 패턴(Singleton Pattern) 싱글턴 패턴이란? 전역 변수를 사용하지 않고 객체를 하나만 생성하도록 하며, 생성된 객체를 어디에서든지 참조할 수 있도록 하는 패턴 Singleton 하나의 인스턴스만을 생성하는 책임이 있다. getInstance 메소드를 통해 모든 클라이언트에게 동일한 인스턴스를 반환하는 작업을 수행 싱글톤 패턴을 쓰는 이유 고정된 메모리 영역을 얻으면서 한번의 new 로 인스턴스를 사용하기 때문에 메모리 낭비를 방지할 수 있다. 또한 싱글톤으로 만들어진 클래스의 인스턴스는 전역 인스턴스이기 때문에 다른 클래스의 인스턴스들이 데이터를 공유하기 쉽다. DBCP(DataBase Connection Pool)처럼 공통된 객체를 여러개 생성해서 사용해야 하는 상황에서 많이 사용. 각 액티비티나 클래스 별로 주요 클래스들을 일.. 2019. 4. 24. 이전 1 2 3 4 5 ··· 7 다음 728x90 반응형
