이번 포스트에서는 음의 가중치를 갖는 간선에서 최단 거리를 구할 수 있는 벨만포드 알고리즘에 대해 살펴보자. 벨만포드(Bellman-Ford) 알고리즘 다익스트라의 한계이전 글에서 다룬 다익스트라 알고리즘은 검증된 그리디한 알고리즘으로 매번 최선의 선택을 하기 때문에 상당히 빠른 시간에 최단 경로를 구할 수 있다. 하지만 나중에 발견된 경로에서 음의 가중치가 발견되면 이전의 선택이 최선이 아니기 때문에 사용할 수 없다. 벨만포드 알고리즘벨만포드는 다익스트라 처럼 가중치 그래프에서 출발점에서 다른 모든 정점까지의 최단 거리를 찾는 알고리즘이다. 단 다익스트라와 달리 음의 가중치를 처리할 수 있으며 간선 중심의 알고리즘이다.벨만포드는 최단 거리의 정점만을 찾아다니지 않고 시작 정점에서 각 정점까지의 최단 거..

이번 포스트에서는 발음이 정말 생소한 다익스트라 알고리즘에 대해서 살펴보자. 이 알고리즘은 에츠허르 다익스트라라는 네델란드 개발자분이 고안한 알고리즘이라고 한다. 튜링상을 받은 어마어마한 분이다.! 다익스트라 알고리즘이란?다익스트라 알고리즘은 특정 시작 정점에서 거리가 최소인 정점을 계속해서 선택해 나가다보면 결과적으로 최단거리를 구할 수 있다는 생각에서 출발한 알고리즘이다.다익스트라 알고리즘은 현재 상태에서 가장 최선이라고 생각되는 정점들을 쭉~탐색해 나가는 그리디 알고리즘이다. 검증이야 이미 다익스트라 아저씨가 잘 해놓은 상태이다. ㅎ아래와 같은 그래프를 생각해보자. 출발점 S에서 목적지 D로 가는 경로는 총 3가지가 가능하다.S->D로 한방에 갈 수도 있지만(W_SD = 50) 이 길은 시골길이어서..

이번 포스트에서는 알고리즘 문제에 자주 나오는 "최단 경로"문제를 해결하기 위한 알고리즘들에 대해서 살펴보자. 최단 경로란? 최단 경로란 그래프를 탐색하면서 임의의 두 정점 사이에 다양한 간선의 조합 중 간선의 가중치의 합이 최단인 경로를 의미한다. 이 최단거리를 구할 때는 크게 간선의 가중치가 없는 경우와 있는 경우 두 가지 경우로 나눌 수 있다. 가중치가 없는 그래프가중치가 없는 경우 즉 모든 정점간의 이동 비용이 동일한 경우는 BFS 탐색이 가장 간단하다. 이때 BFS의 depth가 총 비용이 된다. 예를 들어 아래와 같은 그래프를 살펴보자.만약 서울에서 출발해서 부산에 도착하는데 각 도시 간 이동 비용이 동일하다면 서울에서 원주, 대구를 찍고 부산에 도착하는게 depth(==비용) 3으로 가장 짧..

이번 포스트에서는 vite에서 사용할 수 있는 UI 컴포넌트 라이브러리 중 shadcn이라는 것을 소개하고 프로젝트에 설치해보자.  shadcn-vue shadcn-vue?shadcn-vue은 화면을 만들 때 사용하는 라이브러리이다. (shadcn은 react 용이고 shadecn-vue가 vue 용이다.)그런데 막상 홈피를 방문해보면 살짝은 갸우뚱하게 하는 메시지가 반긴다.앱에 복사해서 붙여넣을 수 있는 아름답게 디자인된 컴포넌트인데 만들어 쓰라니 약간 갸우뚱 하다. docs에서 소개를 보니 이해가 되긴 한다. Tailwind CSS 기반으로 만들어졌다는 것도 기억 할만하다.This is NOT a component library. It's a collection of re-usable componen..

이번 포스트에서는 레거시 스프링 프로젝트를 구성하는 절차를 살펴보자.이 페이지의 내용은 스프링 부트 애플리케이션의 구성을 연습하기 위한 것으로 비지니스 로직 처리는 적절치 않습니다. 기본 프로젝트 구성 maven project 구성아키타입을 생략한 새로운 Maven Project를 생성한다.group id(소속사 domain), artifact id(project 이름)을 기입하고 web 서비스를 위해 packaging을 war로 설정한다. pom.xml에 JDK 설정 및 필요한 의존성 설정다음과 같이 pom.xml 파일을 수정해서 JDK와 필요한 의존성을 설정한다. 4.0.0 com.doding legacyproj 0.0.1-SNAPSHOT war 17 6.1.13 org.spri..

Servlet 3.0에 들어오면서 WAS에서 xml 내용이 제외되기 시작했다. 따라서 web.xml이 제거되고 자바 기반으로 동작할 수 있도록 구조적인 변경이 일어났다.그럼 web.xml의 내용들은 어디로 없어졌을까?  web.xml의 흔적을 찾아서 ServletContainerInitializerWAS는 처음 동작을 시작하면서 web.xml 파일을 로딩해서 애플리케이션(컨텍스트)를 초기화 한다. Servlet 3.0에서 부터는 XML없이 초기화를 진행하기 위해서 java를 실행해야할 필요가 생겼다. 그래서 등장한 친구가 ServletContainerInitializer가 그 역할을 한다. WAS는 classpath에 포함된 ServletContainerInitializer타입의 객체들을 로드해서 onS..

이번 포스트에서는 JDK21에 추가된 Virtual Thread에 대해 살펴보자.  Virtual Thread? 기존의 스레드의 동작 방식자바에는 이미 잘 동작하는 스레드가 있는데 구지 Virtual Thread(V.T)가 필요했던 이유는 무엇일까? V.T의 필요성을 이해하기 위해서는 먼저 기존 스레드의 동작을 살펴볼 필요가 있다.일단 스레드는 기본적으로 OS의 자산이다. 자바께 아니다. Java에서 스레드를 사용할 때는 OS의 스레드와 1:1로 통신할 수 있는 스레드를 만들어서 사용한다. 이를 플랫폼 스레드(Platform Thread:P.T)라고 부른다. 그러다 보니 스레드의 주도권은 OS에 있다. 자바에서 스레드로 뭔가를 하려고 하면 OS와 소통해야 한다는 말이다.기존의 Thread의 문제점과 V..

JDK18 ~ JDK20은 STS로 확정된 기능이 거의 없이 지나갔다. 드디어 2023년 9월 19일 LTS인 JDK21이 다양한 기능을 포함하고 발표되었다.  문법적인 변화 JEP 441: Pattern Matching for switch이제 switch case 문장에서 단순한 값 뿐 아니라 타입, null 여부까지 판단할 수 있게 되었다. 여기서 패턴이라 특정한 형태나 구조를 가진 데이터를 찾아내기 위한 개념으로 생각할 수 있다.  기존의 switch 문장이 int, String 등으로 단순히 값이 같은지를 비교했다면 이제 Object를 파라미터로 받아서 타입 기반으로 처리하거나 when 키워드를 이용해서 조건을 추가할 수도 있게 되었다.// if 문을 이용한 타입 확인 및 활용static Str..