전체 글
-
[백준] 1753 : 최단경로 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 23:46
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 풀이 전 설계 방향 그래프 탐색 문제이며 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 합니다. 정점의 개수가 20,000개 이고 간선의 개수가 300,000이다 보니 완전 탐색은 불가능하고 정점과의 거리를 갱신시키는 다익스트라 알고리즘을 그대로 적용하면 될 것 같습니다. 정점의 개수가 많기 때문에 인접행렬보다는 인접 리스트를 이용합니다. 또는 fr..
-
[백준] 1238번 : 파티 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 23:46
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해석 N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다. 마을 사이에는 총 M개의 단방향 도루들이 있고, i번째 길을 지나는데 T(i)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 이때 최단거리를 원하며 도로들은 단방향이다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은? 문제 풀이..
-
다익스트라(Dijkstra) 알고리즘알고리즘/알고리즘 2022. 3. 17. 18:44
다익스트라 알고리즘이란? DP를 활용한 최단 경로 탐색 알고리즘입니다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줍니다. 이때 음의 간선은 포함할 수 없습니다. 다익스트라 알고리즘이 DP 문제인 이유는 ' 최단거리는 여러 개의 최단 거리로 이루어져 있기 때문입니다.' 예제 1 예를 들어 다음 그림과 같이 1번 노드부터 다른 노드로 가는 최단 경로를 구한다고 가정해 보겠습니다. 우선 1번 노드와 인접한 2번, 3번, 4번 노드 간의 최단 거리를 구합니다. 경로 1 -> 2의 비용은 3 경로1 -> 3의 비용은 6 경로1 -> 4의 비용은 7 이후, 1번 노드와 인접하면서 가장 비용이 적은 2번 노드를 방문합니다. 경로1 ->3의 비용은 원래 6이었는데 2를 경유해서 가는 경우 4로 ..
-
서비스 메시(Service Mesh)란? + API Gateway와 차이점MSA & 쿠버네티스(Kubernetes) - k8s 2022. 3. 17. 13:22
서비스 메시란? Mesh란 그물,망사라는 뜻을 가지고 있으며, Service Mesh는 Serivce들이 그물처럼 엮여있는것을 뜻합니다. MicroService Architecture를 적용한 시스템의 내부 통신이 그물(Mesh) 네트워크의 형태를 띄는 것에 빗대어 Service Mesh로 명명됩니다. 애플리케이션 계층이 아닌 인프라 플랫폼 계층에 특정 모듈을 삽입하여 애플리케이션에 대한 라우팅, 보안 및 안정성 기능을 추가하는 도구입니다. 서비스 메시는 쿠버네티스와 같은 컨테이너 오케스트레이션 환경에서 일반적으로 애플리케이션 코드(사이드 카 라고 불리는 패턴)와 함께 배치된 확장 가능한 네트워크 프록시 모듈로 구현됩니다. 그림을보면 MicroService와 SideCar로 구성되어 있고, SideCar..
-
[백준] 18222 : 투에-모스 문자열 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 00:01
https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제 해석 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 문자열 X는 다음과 같은 과정으로 만들어진다. 1. X는 맨 처음에 0으로 시작한다. 2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. 3. X의 뒤에 X'을 붙인 문자열을 X로 다시 정의한다. 4. 2~3의 과정을 무한히 반복한다. 입력 첫 번째 줄에 자연수 k (1 ≤ k ≤ 10^18..
-
[백준] 10163 : 색종이 - 자바(JAVA)알고리즘/백준 2022. 3. 16. 00:01
https://www.acmicpc.net/problem/10163 10163번: 색종이 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 www.acmicpc.net 문제 해석 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓인다. 색종이는 비스듬하게 놓이는 경우는 없습니다. 위의 그림에서 4번 색종이를 하나 더 놓았을 때 3번 색종이는 완전히 가려서 보이지 않게 됩니다. 다음과 같이 N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분 면적을 구하는 프로그램을 작성하세요. 문제 풀이 전 설계 https://junuuu...
-
Mock 객체란?테스트코드(Test Code) 2022. 3. 15. 18:56
Mock 객체란? Mock은 사전적 의미로 모조품이라는 뜻을 가집니다. 즉, 제품의 외양을 흉내 낸 모조품을 말하며 소프트웨어에서는 모듈의 겉모양이 실제 모듈과 비슷하게 보이도록 만든 가짜 객체를 Mock 객체라고 합니다. 왜 사용할까요? 테스트 카이스 작성이 어려운 상황과 Mock 객체가 필요한 상황은 종종 일치하곤 합니다. 대부분의 경우 모듈이 가진 '의존성'이 근본적인 원인이 됩니다. 따라서 그 '의존성'을 단절시키기 위해 사용합니다. 예를 들어 다음과 같은 상황에 사용합니다. 1. 테스트 작성을 위한 환경 구축이 어려울 때 다른 부서와 연계 모듈이어서 다른 쪽에서 승인을 해줘야 테스트가 가능한 경우 방화벽으로 막혀 있어서 통과가 어려운 경우 다른 부서에게 모듈을 아직 넘겨받디 못한 경우 오라클 데..
-
[백준] 2563 : 색종이 - 자바(JAVA)알고리즘/백준 2022. 3. 15. 00:01
https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제 해석 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 변과 도화지의 변이 평행하도록 붙입니다. 여러 장의 색종이를 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.(종이가 겹치게 붙을 수 있습니다.) 입력 첫째 줄에 색종이의 수가 주어집니다. 이어 둘째 줄부터 한 줄..