저번 포스팅에서 연결그래프의 MST(Minimum Spanning Tree) 를 구하는 방법인 Prim 알고리즘에 대해 소개하고 그 정확성을 증명해보았습니다. https://matt1235.tistory.com/51 Prim 알고리즘 - 1 이번 포스팅에서는 Prim Algorithm을 소개하고, 그 정확성을 증명해보고자 한다. 다음 그림을 보자. 정점이 다섯 개가 있고 간선(edge)이 총 10개 있는 연결 그래프이다. 각 간선의 숫자는 노드에서 노 matt1235.tistory.com 이번 포스팅에서는 Prim을 구현해보겠다. => 우선순위 큐를 이용해 구현 우선순위 큐 (Priority Queue) 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 방식..

이번 포스팅에서는 Prim Algorithm을 소개하고, 그 정확성을 증명해보고자 한다. 다음 그림을 보자. 정점이 다섯 개가 있고 간선(edge)이 총 10개 있는 연결 그래프이다. 각 간선의 숫자는 노드에서 노드까지의 거리를 나타낸다. 위 그래프에서 MST(최소 비용 신장 트리)를 구하라. 용어 신장트리(Spanning Tree) 그래프 내 모든 정점을 포함하는 트리를 의미. 모든 정점이 연결되어 있어야 하고, 사이클을 포함해서는 안된다. 따라서 신장트리는 노드가 n개라면 정확히 (n-1) 개의 간선을 갖는다. 신장트리의 예시로는 다음이 있다. 이처럼 모든 노드가 연결되어 있고, 사이클을 만들지 않으면 Spanning Tree 완성이다. 간선의 수는 자연스레 (노드수 - 1) 이 된다. 우리가 위 문..

이번 포스팅에서는 선택정렬(Selection Sort) 알고리즘을 증명해보자. selection sort 는 알고리즘을 처음 접하면 알게 되는 녀석이다. 하지만 이 역시 수학적으로 엄밀하게 증명해본 적이 없어 이를 증명해보고자 한다. selection sort 소스코드 // Selection Sort int sort(int a[], int n){ int i, j, m, t; for(i=0;i k-1 이라면 a[k-1] < a[x] 가 성립한다. Proof Invariant 수학적 귀납법을 이용해 불변조건을 증명해보자. Base k=0일 때 (1)은 null condition, true. (2)도 null이므로, true. 성립할 조건이 아예 없으면 true이다. 따라서 Invariant 는 성립한다. S..

Spring 이란? 위키백과에는 다음과 같이 나와있다. 자바 플랫폼을 위한 오픈소스 어플리케이션 프레임워크. 동적인 웹 사이트를 개발하기 위한 여러가지 서비스를 제공한다. 즉 스프링은 많은 프레임워크들 중 하나로, 자바로 어플리케이션을 만들 수 있다. 수많은 Framework 중 스프링은 어떤 장점이 있을지 알아보자. 1. POJO 기반의 구성 POJO 란? Plain Old Java Object 특정 라이브러리나 컨테이너 기술에 종속적이지 않게 개발. 2000년 9월에 마틴 파울러, 레베카 파슨, 조쉬 맥킨지 등이 사용하기 시작한 용어 오래된 방식의 자바 객체라는 말로, Java EE 같은 중량 프레임워크를 사용하는 것에 반발해 나온 용어라고 한다. 예를 들면 자바 ORM(Object Relations..

이번 포스팅 내용은 Merge Sort 의 정확성을 증명해보는 것이다. Divide and Conquer - 분할 정복 입력을 나누어 더 작은 문제를 물고, 작은 문제들의 답을 조합해 전체 문제의 답을 만든다. 아주 작은 문제는 어쨌거나 풀린다. mergeSort는 분할 정복 기법을 사용한다. 문제를 더 작은 문제로 나누고, 답을 합칠 때(merge) 재귀가 사용된다. 위처럼 "이미 Sorted 된 두 배열을 합쳐(merge) Sorted 된 배열을 만들자" 가 이 알고리즘의 아이디어이다. 재귀라고 해서 따라 들어가지 않고, 바로 알 수 있도록 증명해보는 연습을 하는 것이다. Recursive MergeSort int sort(int a[], int n){ if(n

많은 테스트코드를 작성할수록, 견고한 서비스를 만들 수 있다는 말을 들었다.  큰 서비스를 다루는 회사 대부분이 테스트코드 작성 경험을 요구하고 있고, 그만큼 테스트코드는 개발자에게 빠질 수 없는 요소가 되었다. 이번 포스팅은 단위테스트에 대한 내용이다. 단위테스트 단위테스트는 어플리케이션에 있는 개별적인 코드, 모듈이 예상대로 잘 작동하는지 단위별로 쪼개서 테스트하는 것이다. 주로 모든 함수와 메서드에 대해 실시한다. 왜 굳이 단위테스트를 해야 할까? 단위테스트를 쓰지 않는다면? 단위테스트를 쓰지 않고 System.out.println() 으로 출력된 값을 내가 확인하면서 테스트를 한다고 해보자. 코드를 작성하고 ,프로그램 (톰캣) 실행 postman 으로 HTTP 요청 요청 결과를 출력해 그 값을 ..