전체 글
-
데이터베이스 Index란?CS/데이터베이스 2022. 3. 18. 00:20
인덱스(Index)란? 보통 배열에서 많이 썼던 단어로 "색인"이라는 뜻을 가집니다. 데이터베이스에서의 인덱스란 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상하기 위한 자료구조입니다. 우리가 책에서 원하는 내용을 찾을때 모든 페이지를 찾아보는 것은 오랜 시간이 걸립니다. 따라서 책의 저자들은 책의 맨 앞 또는 맨 뒤에 색인을 추가합니다. 데이터베이스의 인덱스는 책의 색인과 유사합니다. 데이터베이스에서도 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 돕고 있습니다. 인덱스를 사용하는 이유? 인덱스를 사용하지 않은 컬럼을 조회해야 하는 상황이라면 전체를 탐색하는 Full Scan을 수..
-
[백준] 5639 : 이진 검색 트리 - 자바(JAVA)알고리즘/백준 2022. 3. 18. 00:01
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 해석 이진트리는 다음의 조건을 만족한다. 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 부모 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 부모 노드의 키보다 크다. 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 후위 순회한 결과를 구하는 프로그램을 작성하라. 문제 풀이 전 설계 이진 검색 트리를 전위 순회한 결과를 통해 이진트리를 생성한다. 생성한..
-
[백준] 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...