개발일지

이번 포스팅에서는 최소신장트리를 찾는알고리즘중 간선을 중심으로 생각해 최소신장트리를 구하는 알고리즘인 크루스칼 알고리즘을 다뤄보도록하겠다. 먼저 크루스칼 알고리즘에 앞서 최소 신장 트리의 개념부터 정의하고 넘어가도록 하겠다. 최소 신장 트리란? 먼저 트리는 그래프의 일종으로 순환하지 않는 형태의 그래프를 트리라고 한다. 이때 신장트리 즉 Spanning Tree는 이런 트리의 형태중 최소의 연결만을 갖는 트리를 신장트리라고 한다. 즉 N개의 정점을 갖는 그래프가 있다면 최소의 연결만을 갖도록 하려면 간선의 수는 N - 1개를 갖는 그래프가 될것이고 이를 신장 트리라고 한다. 이런 하나의 그래프에서 이런 신장트리는 여러개가 나올수 있는데 그중에서 간선의 비용을 최소로 갖는 경우를 최소 신장 트리 (Mini..

언제 사용하는가? unoin-find 유니온 파인드 , 분리집합, 서로소 집합, 합집합등 다양한 이름으로 불리는 이 알고리즘은 그래프의 연결관계를 파악할때 아주 효과적인 알고리즘이다. 여러 노드가 존재한다고 가정할때 그중 두개의 노드를 선택해 연결되어 있는가를 확인할때 적용이 가능하다. 다음과 같이 그래프가 있다고 가정해보자. 이때 임의의 노드 1과 4를 골라 연결관계를 파악하고 싶다면 DFS/BFS 등 여러 탐색 알고리즘이 생각날것이다. 그러나 이러한 그래프가 지하철 노선도와 같이 매우 크다라고 가정할때 임의의 두점을 골라 연결관계를 위해 다른 탐색알고리즘을 사용한다면 가능은 하겠으나 시간이 매우 오래걸린단 단점이 있다. 바로 이럴때 유니온파인드 알고리즘을 사용하면 효과적으로 두 노드의 연결관계를 파악..

이번 프로젝트는 핵심기능부터 먼저 만들어 사용하기 위해 TDD를 사용해 진행하기로 했다. 지금까지 핵심테이블,인터페이스의 구현이 완료되었으니 식단 생성의 핵심기능중 BMR, 일일소비칼로리의 계산기능을 만들기전 단위테스트 먼저 작성하기로 했다. 이전에 생성해온 프로젝트에서는 JUnit4를 사용해 단위테스트를 사용했었는데 이번 프로젝트는 JUnit5를 사용하고 assertj 라이브러리등 테스트코드의 가독성을 높이고 좀 더 사용하기 편한 친구들을 통해 원활한 단위 테스트를 진행하기 위해 별도의 설정을 해주기로 했다. 먼저 JUnit4에서 5로 버전 변경을 위해 pom.xml에서 dependency를 수정해주어야 한다. 기존의 JUnit4로 되어있는 dependency를 지우고, 다음의 dependency를 추..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 최근에 함수형 인터페이스를 공부했었는데 활용하기 좋은 문제 인거 같아 정리해보고자 한다. 문제 분석 3칸씩 n개의 줄로 주어지는 숫자들에서 숫자를 하나씩 골라 더했을 때 최대값, 최소값을 구하면 된다. 이때 숫자를 고르는 조건은 현재 숫자를 고른 행,열을 기준으로 다음 행에서는 현재열과 인접한 열의 숫자만 고르는게 가능하다. 즉 현재 고른숫자가 제일 왼쪽이라면 다음에 고를수 있는 숫자는 왼쪽과 가운데, 제일 오..

이전 포스팅에서 정리했듯 핵심기능의 DB설계가 얼추 마무리 되었으니 이제 스프링으로 넘어가 interface 설계를 진행하겠다. 그전에 스프링 프레임 워크를 사용한 웹서비스의 흐름을 따라 인터페이스 설계의 목적을 설명하도록 하겠다. 왜 인터페이스 설계가 필요한가? 한가지 예시를 들어 설명하도록 하겠다. 현재 진행하는 식단생성기가 완성되었다 가정하고 웹서비스를 이용하는 유저가 식단생성기 웹에 방문해 정보를 입력 후 식단 생성버튼을 클릭했다라고 가정해보도록 하겠다. 이 과정을 클라이언트의 요청이라 부르는데, 클라이언트의 요청이 발생하게 되면 해당 요청에 대한 정보를 서버로 넘기게 된다. 이때 현재 프로젝트에서 사용하기로한 웹서버는 아파치 톰켓 V8.5을 사용하고있고 웹서버를 거쳐 서버컴으로 요청이 전송된다...