728x90 반응형 분류 전체보기301 크루스칼 알고리즘(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. 객체 지향 프로그래밍의 5원칙(SOLID) 객체 지향 설계를 위해서는 5가지 원칙이 따른다. (앞글자를 따서 SOLID라고 한다) S - SRP(Single Responsibility Principle) 단일 책임 원칙 객체는 오직 하나의 책임을 가져야 한다. (객체는 오직 하나의 변경의 이유만을 가져야 한다.) 다시 말하면 클래스를 수정할 필요가 오직 하나여야한다는 뜻. 예를 들어, 사칙연산 함수를 가지고 있는 계산 클래스가 있다. 이 상태의 계산 클래스는 오직 사칙 연산 기능만을 책임진다. 만일 프로그램이 대대적으로 공사를 들어가게 되더라도 계산 클래스가 수정될만한 사유는 누가 봐도 사칙연산 함수와 관련된 문제 뿐이다. 이처럼 단일 책임 원칙은 클래스의 목적을 명확히 함으로서 구조가 난잡해지거나 수정사항이 불필요하게 넓게 퍼지는 것을 예방하고.. 2019. 4. 24. 힙 정렬(Heap Sort) 힙 정렬 힙 트리 구조(Heap Tree Structure) 를 이용하는 정렬 방법 병합 정렬(Merge Sort)와 퀵 정렬(Quick Sort)만큼 빠른 정렬 알고리즘 힙이란? 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 최대힙이란? '부모 노드'가 '자식 노드'보다 큰 힙 자기 자신 노드의 자식이 되는 노드들이 자신보다 작다. 만약에, 어떤 노드의 경우가 최대 힙의 조건을 만족하지 않아, 최대 힙이 되지 않을 경우 힙 정렬을 수행하는데 이때 힙 생성 알고리즘(Heapify Algorithm) 을 사용한다. 힙 생성 알고리즘은 특정한 '하나의 노드'에 대해서 수행하는 것 또한 해당 '하나의 노드를 제외하고는 최대 힙이 구성되어 있는 상태'라고 가정을 한다는 특징이 있.. 2019. 4. 23. 이전 1 ··· 30 31 32 33 34 35 36 ··· 43 다음 728x90 반응형
