분류 전체보기
최소 신장 트리 (Minimum Spanning Tree, MST) 최소 신장 트리는 가중치 무방향 그래프에서 최소 비용으로 모든 정점을 연결하는 트리이다.사이클이 없음 : 그래프의 모든 정점을 포함하면서 사이클이 없는 그래프 형태로 구성된다. 특징 MST는 연결 그래프에서 정의되며 그래프가 연결되지 않은 경우 MST를 구할 수 없다.간선의 개수가 항상 V-1(정점의 개수 - 1)이다.MST는 유일하지 않을 수 있으며, 동일한 가중치를 가지는 여러 MST가 존재할 수 있다. 크루스칼 알고리즘 (Kruskal's Algorithm) 모든 노드를 연결할 때 필요한 최소 간선 수는 N-1개이며, 이것이 최소 신장 트리의 요구사항이다. 따라서 총 N-1개의 간선을 선택해야 한다.간선을 가중치 순으로 정렬한 뒤,..
트랜잭션은 작업에서 예외가 발생할 경우 Rollback 처리를, 모두 성공할 경우 Commit 처리하는 실행 단위이다.Spring에서는 트랜잭션과 관련된 기술들을 제공하며, 주로 @Transactional 어노테이션을 통해 쉽게 사용할 수 있다.이번 포스팅에서는 Transacrtional을 Spring의 트랜잭션의 동작 특성과, 트랜잭션 전파라는 키워드를 위주로 살펴보려고 한다. Spring이 제공하는 트랜잭션 기능 1. 트랜잭션 동기화데이터베이스와의 작업이 트랜잭션 컨텍스트 내에서 일관되게 처리될 수 있도록 도와준다. 이는 여러 데이터베이스 작업이 하나의 트랜잭션 안에서 수행되도록 동기화하는 것을 의미한다. 예를 들어, 하나의 서비스 메서드에서 두 개의 다른 데이터베이스 테이블을 업데이트해야 한다고 ..
위상 정렬(Topological Sort) 사이클이 없는 그래프에서 노드의 순서를 찾는 알고리즘그래프 내의 노드들 간의 선후 관계를 결정하여, 어떤 작업들이 먼저 수행되어야 하는지 순서를 정하는 것이 목표이다.작업의 선후 관계를 결정해야 하거나 특정 순서로 작업을 처리해야 하는 문제에서 사용된다. 특징위상 정렬은 방향 그래프에서 사용된다. 노드들 간의 방향성이 있는 의존 관계를 표현하기 위해서 위상 정렬을 수행하는 것이기 때문이다.그래프에 사이클이 없어야 한다. 사이클이 존재하면 위상 정렬이 불가능하다.이 점을 이용하여 반대로 위상 정렬을 수행하여 사이클을 탐지할 수 있다.위상 정렬 결과는 항상 유일하지는 않다. 즉 동일한 그래프에 대해 여러 가지 정렬 결과가 나올 수 있다.시간 복잡도는 O(V+E), ..
유니온-파인드(Union-Find) 유니온-파인드 알고리즘은 집합을 결합(Union, 합집합)하고 해당 Element가 소속된 집합을 찾아내는(Find) 알고리즘이다.서로소 집합(Disjoint-Set) 알고리즘이라고도 불린다.그래프에서도 유용하게 사용되어 노드 간의 연결 관계를 확인하는 등으로 응용되어 자주 사용된다. 해당 알고리즘은 두 가지 기본 연산으로 구성된다.Union 연산: 여러 노드 중 두 노드를 선택하여 이들을 하나의 집합으로 연결한다. 이 연산을 통해 서로 연결된 노드들이 같은 집합에 속하게 된다.Find 연산: 특정 노드의 대표 노드를 찾아낸다. 두 노드의 대표 노드를 찾아낸다면 해당 노드들이 같은 집합에 속해 있는지를 확인할 수 있다. 유니온-파인드의 용도 집합 소속 여부 판단: 임의..
우리는 흔히 Controller, Service, Repository 등의 계층별 모듈로 구분하여 프로그램을 작성한다.이번 포스팅에서는 Layer 별 테스트 코드를 어떻게 작성하면 좋을지에 대한 전략에 대해서 작성해보려고 한다. 해당 포스팅의 내용은 무조건 계층별로 테스트 코드는 이렇게 작성해야 한다는 것이 아닌, 그저 테스트 코드를 작성하는 수만가지 전략 중 하나라는 것을 엄두하고 구경하면 좋을 것 같다. 기본사항 프로파일 분리application.yml의 프로파일을 Test 전용으로 나누어 독립적인 DB를 사용할 수 있게 하자.테스트 시 실제 환경(DB)에 영향을 주지 않고 데이터베이스를 초기화하거나 필요한 데이터를 주입하여 테스트할 수 있도록 하기 위해서이다.spring: profiles: ..
레이어드 아키텍쳐 (3-tier Layered Architecture) 우리는 흔히 Spring Framework를 이용하여 Controller, Service, Repository 등의 계층별 모듈로 구분하여 프로그램을 작성하였다. 해당 구조를 3-tier Layered 아키텍쳐라고 한다.해당 구조는 각 계층이 서로 독립적으로 동작하고 각 계층의 역할을 명확하게 구분하여 유지보수성과 확장성을 높이는 것을 목표로 한다. 이번 포스팅에서는 프로그램을 작성할 때, 계층별로 집중해야 하는 포인트에 대해서 알아보려고 한다. Presentation Layer 사용자와 애플리케이션 간의 인터페이스 역할을 담당하는 계층이다. 사용자의 요청을 수신하고, 이를 비즈니스 로직으로 전달하며, 결과를 사용자에게 반..
테스트 코드의 필요성 수동 테스트의 문제점 수동으로 테스트 한다는 것은 곧 사람이 직접 테스트를 수행한다는 것이다. 특정한 케이스를 직접 넣어보고, 출력이나 로그 따위를 살펴보거나 디버깅을 해보는 행위, 우리가 늘상 해오던 과정이다. 그러나 사람이란 누구든 실수를 하며, 편협된 시각을 가지고 있다. 이로 인해 커버하지 못하는 영역이 있을 수 있으며, 이는 늦은 피드백, 유지보수의 난이도 상승, 소프트웨어 신뢰성 하락으로 이어진다. 테스트 코드의 필요성 테스트 코드의 정체성은 "빠른 피드백", "자동화", "안정성", "공유"로 압축할 수 있다. 빠른 피드백 : 개발자는 Production Code(실제 코드)와 Test Code 사이의 피드백을 통해 품질을 개선해 나갈 수 있다. 개발자가 코드를 작성하고..
진행중인 프로젝트의 데브서버에 CI/CD 파이프라인을 구축하는 작업을 맡게 되었다.이전 포스팅에서 AWS EC2에 스프링 프로젝트를 Docker 컨테이너 사용과 함께 가장 심플한 형태로 배포해 본 적이 있다.이번 포스팅에서의 목표는 해당 내용의 연장선으로 자동적으로 Git에 소스코드가 Push되면 이를 자동으로 배포하는 CI/CD 파이프라인을 구축해보려고 한다. (+ 데브서버이기에 AWS 프리티어 사용 한도 이내에서만 하는 것을 목표로 했다. 따라서 AWS CodeDeploy 등 다른 과금이 나가는 서비스를 사용하지 않고 기본제공 EC2 + EBS만을 사용한다) Docker에 대해서 기본적인 이해가 있다고 가정하고, 아래의 AWS 배포 과정의 연장선으로 진행하기 때문에 이해가 되지 점이 있다면 아래의 포..
플로이드 워셜( Floyd-Warshall)가중치가 존재하는 그래프의 시작 정점으로부터 다른 정점들까지의 최단 거리를 구하는 알고리즘. 모든 정점 쌍 사이의의 최단 거리를 탐색한다. 특징시작 정점으로부터 나머지 정점의 최단거리를 알아내는 다익스트라나 벨만-포드와 달리 모든 정점들 간의 거리를 탐색한다.Edge 가중치가 음수일 경우에도 사용 가능 (단 음수 싸이클이 있으면 안됨)시간 복잡도 : O(N^3) (N = 노드의 개수) → 노드의 개수가 200개 내외로 주어지는 경우에 사용을 고려할 수 있다.동적 계획법을 활용하여 부분해를 활용하여 문제를 해결하는 방식을 사용한다.A -> B -> C의 최단 거리를 구할 때, A->B와, B->C의 최단 거리를 안다면, A->B->C의 최단 거리를 알 수 있다. ..
