suyeonme

다익스트라 알고리즘(Dijkstra Algorithm)이란? 그리디 알고리즘/다이나믹 프로그래밍을 이용한 대표적인 그래프의 최단 경로(Shortest Path)를 구하는 알고리즘이다. 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다. 다익스트라 알고리즘은 하나의 최단 거리를 구할 때 이전에 구했던 최단 거리 정보를 그대로 사용한다. 최단 거리는 여러개의 최단거리로 이루어져있다고 볼 수 있다. 따라서 다익스트라 알고리즘은 다이나믹 프로그래밍 기법을 사용한다. * 인공 위성 GPS에 가장 많이 사용된다. 그래프의 최단 경로를 구하는 알고리즘 비교 알고리즘 특징 BFS 간선의 가중치가 모두 같은 그래프의 경우 다익스트라 알고리즘(Dijkstra A..

크루스칼 알고리즘(Kruskal Algorithm)이란? 최소 비용으로 모든 노드를 연결하기 위해서 사용하는 알고리즘으로 대표적인 최소 신장 트리(MST, Minimum Spanning Tree)를 만드는 대표적인 알고리즘이다. 가장 적은 비용(weight)을 탐욕적(Greedy Algorithm)으로 확인하여 가장 적은 비용으로 사이클이 발생하지 않게 모든 노드를 연결한다. 시간복잡도는 O(E log E)이다. 간선을 가중치순으로 정렬하므로 E log E만큼의 시간이 소요된다. (=퀵정렬의 시간 복잡도) 반복문에서 V-1만큼의 시간이 소요된다. 최소 신장 트리(MST, Minimum Spanning Tree)란? 신장 트리(Spanning Tree): 그래프의 모든 정점을 연결하고 사이클이 없는 그래프..

합집합 찾기(Union Find) 알고리즘이란? 대표적인 그래프 알고리즘으로, 여러개의 노드가 존재하는 경우 두 개의 노드를 선택하여 선택된 노드가 서로 같은 그래프에 속하는지 확인하는 알고리즘이다. 서로소 집합(Disjoint-Set) 알고리즘이라고도 불리운다. 크루스칼 알고리즘(Kruskal Algorithm)등 고급 그래프 알고리즘에 사용된다. 사이클(Cycle)이 있는지 확인하는 문제 구현 방법 노드의 부모가 자기 자신이 되도록 초기화한다. 두개의 노드를 연결한다. 이 때 더 작은 노드가 부모가 되도록 합친다. -- unionFind 재귀를 사용하여 두개의 노드가 같은 그래프에 속해있는지 확인한다. -- findParent 알고리즘 구현 // 부모노드를 찾는다. const getParent = (..

태그(Tag)란? 태그란 커밋을 참조하기 쉽도록 이름을 붙이는 것으로, 즉 커밋을 태깅(tagging)하는 것이다. 주로 배포 브랜치(release branch)에서 서비스의 버전을 지정할 때 사용한다. 서비스의 버전이 1.0이라면 서비스 1.0을 릴리즈할 때 태깅을 한다. 그 이후 신규 기능은 커밋으로 관리를 하다가 서비스 1.1을 릴리즈할 때의 커밋에 태깅을 할 수 있다. 이런식으로 배포 브랜치를에 태그를 달아서 서비스의 버전을 명시하거나 문제가 생겼을 때 해당 부분을 롤백(rollback)하는등의 행위를 할 수 있다. 태그의 종류 Lightweight Tag: 이름만 붙일 수 있는 태그(커밋번호가 곧 태그)로, 임시로 태그를 생성하거나 메타 데이터를 제공하고 싶지 않은 경우 사용한다. Annotat..

Servlet이란? 클라이언트의 요청(request)을 처리하고 응답(response)을 반환하는 Servlet 클래스를 따라는 자바 프로그램이다. Servlet 특징 HttpServletRequest로 HTTP 요청을 쉽게 다룰 수 있다. (query string, 메세지 바디 조회등) HttpServletResponse로 HTTP 응답을 쉽게 다룰 수 있다. (status code, content-type, cookie, redirect등) 개발자는 서블릿을 사용하여 HTTP를 쉽게 핸들링할 수 있다. Servlet 예시 코드 @WebServlet(name = "requestParamServlet", urlPatterns = "/request-param") public class RequestServ..

문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정..

Redis란? Redis란 Remote Dictionary Server, REDIS의 약자로, In-memory 기반의 데이터베이스이다. key-value 쌍으로 데이터를 저장하는 NoSQL 데이터베이스이며 메모리에 데이터를 저장하기 때문에 빠른 속도를 보장한다. Redis는 메모리에 데이터를 저장하기 때문에 휘발성 데이터베이스이다. 따라서 주로 빠른 응답을 위해 RDBMS에 있는 데이터를 캐시하는 용도로 사용한다. 리스트형 데이터의 입력/삭제가 RDBMS에 비해 10배정도 빠르다. Redis의 데이터 타입 String Lists Sets (유니크한 값만 취급하는 배열) Sorted sets Hashs (중첩이 허용되지 않는) Redis의 command redis-cli에서 나가고 싶은 경우, quit을..

docker-compose.yml docker-compose.yml 파일의 volumns에 ./init.sql:/docker-entrypoint-initdb.d/init.sql와 같이 추가하면 컨테이너가 시작할 때init.sql 파일이 실행된다. version: '3.8' services: db: image: mysql:8.0 restart: always environment: MYSQL_DATABASE: ${DB_NAME} MYSQL_ROOT_PASSWORD: ${DB_PASSWORD} ports: - '3306:3306' volumes: # 데이터 베이스 초기화(init.sql) - ./init.sql:/docker-entrypoint-initdb.d/init.sql volumes: db: drive..