다익스트라 개념을 잘 모른다면 아래 포스팅을 읽고 오자. https://myeongju00.tistory.com/52 [Algorithm] Java - 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘이란? BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 즉, 그래프에서 출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아 myeongju00.tistory.com 구현에는 인접 행렬 방식, 우선순위 큐 방식이 있다. 노드의 개수를 V라고 할 때 인접 행렬 방식은 O( V^2 ) 우선순위 큐 방식은 O( V log V ) 의 시간 복잡도를 가진다. 따라서 알고리즘 문제풀이 시 우선순위 큐 방식을 주로 사용한다. 인접 행렬 방식 1..

다익스트라 알고리즘이란? BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 즉, 그래프에서 출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. ❓왜 다이나믹 프로그래밍일까? 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용하기 때문이다. 다익스트라 알고리즘 특징 그래프 내부 하나의 정점(노드, Vertex)에서 다른 모든 정점으로 가는 최단 경로를 알려줌 그래프의 간선(Edge)마다 가중치가 존재할 때 사용 ⇒ BFS를 활용한 최단 경로 구하기와 다른 점 간선의 음의 가중치는 존재하지..

이 글은 이동욱 님의 '스프링 부트와 AWS로 혼자 구현하는 웹 서비스' 책 내용을 정리한 것입니다. http://www.yes24.com/Product/Goods/83849117 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 - YES24 가장 빠르고 쉽게 웹 서비스의 모든 과정을 경험한다. 경험이 실력이 되는 순간!이 책은 제목 그대로 스프링 부트와 AWS로 웹 서비스를 구현한다. JPA와 JUnit 테스트, 그레이들, 머스테치, 스프링 www.yes24.com 스프링 시큐리티와 OAuth 2.0으로 로그인 기능 구현하기 스프링 시큐리티는 막강한 인증과 인가(권한 부여) 기능을 가진 프레임워크이다. 스프링 기반의 애플리케이션에서 보안을 위한 표준이라고 보면 된다. 확장성을 고려한 프레임워크로 다양한..

그래프 탐색이란? : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색(DFS)이란? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로 부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사 ⇒ 넓게(wide) 탐색하기 전에 깊게(deep) 탐색 깊이 우선 탐색(DFS)의 특징 자기 자신을 호출하는 순환 알고리즘의 형태 전위 순회(Pre-Order Traversa..

이 글은 이동욱 님의 '스프링 부트와 AWS로 혼자 구현하는 웹 서비스' 책 내용을 정리한 것입니다. http://www.yes24.com/Product/Goods/83849117 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 - YES24 가장 빠르고 쉽게 웹 서비스의 모든 과정을 경험한다. 경험이 실력이 되는 순간!이 책은 제목 그대로 스프링 부트와 AWS로 웹 서비스를 구현한다. JPA와 JUnit 테스트, 그레이들, 머스테치, 스프링 www.yes24.com 1. 템플릿 엔진과 머스테치 템플릿 엔진이란? 지정된 템플릿과 데이터가 합쳐져 HTML 문서를 출력하는 소프트웨어 서버 템플릿 엔진 vs 클라이언트 템플릿 엔진 공통점 : 지정된 템플릿과 데이터를 이용하여 HTML을 생성 차이점 서버 템플릿..

🔗 16953번 A -> B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 📝 접근 방법 및 풀이 처음에는 A를 B로 바꾸는 방식으로 하려 했지만, 거꾸로 B를 A로 바꾸는 로직이 더 빠를 것 같아서 그..

JPA 소개 현대의 웹 애플리케이션에서 관계형 데이터베이스는 빠질 수 없는 요소이다. Oracle, MySQL, MSSQL 등을 쓰지 않는 웹 애플리케이션은 거의 없다. 그러다 보니 객체를 관계형 데이터베이스에서 관리하는 것이 무엇보다 중요하다. 관계형 데이터베이스가 계속해서 웹 서비스의 중김이 되면서 모든 코드는 SQL 중심이 되어 간다. 이는 관계형 데이터베이스가 SQL만 인식할 수 있기 때문인데, SQL로만 가능하니 각 테이블마다 기본적인 (CRUD)를 매번 생성해야 된다. 개발자가 아무리 자바 클래스를 아름답게 설계해도, SQL을 통해야만 데이터베이스에 저장하고, 조회할 수 있다. 결국 관계형 데이터베이스를 사용해야만 하는 상황에서 SQL은 피할 수 없다. JPA는 이런 문제점을 해결하기 위해 등..

🔗 1958번 LCS3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 문제 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라. 입력 첫 줄에는 첫 번..

🔗 9252번 LCS2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 ..

🔗 9251번 LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져..