분류 전체보기 (247) 썸네일형 리스트형 [Algorithm] Kruskal's Algorithm (크루스칼 알고리즘) 1. Kruskal's Algorithm 크루스칼 알고리즘은 edge를 그리디하게 선택하여 MST를 구성하는 알고리즘이다. edge를 가중치 기준으로 오름차순으로 정렬한 후 가장 작은 edge부터 순서대로 subtree에 추가하여 MST를 구성한다. 이때 해당 edge가 cycle을 이루는지 확인을 해야하는데, 이때 union-find 알고리즘은 사용하는데, 각 정점에 index를 주어서 정점들이 연결될 때마다 해당 그룹의 정점들이 모두 같은 index를 가지도록 하여 이를 비교하여 같은 index를 가지는 경우 cycle로 인식한다. 2. 크루스칼 알고리즘 구현 1) 그래프의 간선을 오름차순으로 정렬한다. 2) 가장 작은 간선을 선택하여 cycle을 그리는지 확인한다. 3) cycle을 그리는 경우는 .. [Algorithm] Floyd-Warshall's Algorithm (플로이드-와샬 알고리즘) 1. Floyd-Warshall's Algorithm 플로이드 와샬 알고리즘은 모든 정점간의 최단 거리를 구하는 All pairs shortest path solving 알고리즘이다. 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 최단 거리를 구한다. 두 정점의 최단 거리를 구할 때 다른 모든 정점을 후보로 각 정점들을 거쳐갈 때의 거리를 비교하여 최소가 되는 경로를 찾는다. 소스 코드를 보면 가장 간단한 알고리즘이다. 2. 플로이드 와샬 알고리즘 구현 플로이드 와샬 알고리즘은 모든 정점 쌍에 대해서 다른 정점들을 중간 경로로 거치는 경로의 거리를 비교하여 최단 거리를 구한다. 1) 먼저 현재 그래프의 간선들을 기준으로 각 정점간의 거리를 저장할 행렬을 초기화한다. 2) 중간 경로가 될 정점을 선택한.. [Algorithm] Bellman-Ford Algorithm (벨만 포드 알고리즘) 1. Bellman-Ford Algorithm 벨만 포드 알고리즘은 다익스트라 알고리즘과 같이 한 정점으로부터 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과의 차이점은 음수 가중치를 가진 간선이 그래프에 존재해도 적용이 가능하다는 점이다. 그러나 음수 간선이 사이클을 이루는 경우에는 최단 거리를 찾을 수 없기 때문에 동작하지 않는다. 벨만 포드 알고리즘은 두 경로 사이의 최단 경로를 구할 때 모든 간선을 대상으로 edge relaxation을 수행한다. edge relaxation은 두 경로 사이에 더 가까운 경로가 있다면 해당 경로의 거리로 간선을 경감하는 작업이다. 그래프에서 s, u 두 정점 사이의 최단 거리 경로는 s -> u로의 바로 연결되는 간선을 통한 경로일 수도.. [Algorithm] Dijkstra's Algorithm (다익스트라 알고리즘) 1. Dijkstra's Algorithm 다익스트라 알고리즘은 한 정점으로부터 다른 정점으로의 최단 경로를 찾는 알고리즘이다. 매반복마다 현 시점에서 가장 가까운 정점을 찾아 해당 정점에 인접한 간선들을 통해 경로를 찾아 확장해 나가는 방식이다. 그래프의 방향 유무는 상관없으나 간선이 음수 가중치를 가지는 경우에는 사용할 수 없다. 2. 다익스트라 알고리즘 구현 1) 초기에 출발점으로부터 해당 정점으로의 거리를 저장할 공간과 방문여부를 저장할 공간을 선언한다. 2) 해당 배열에서 출발점은 0, 나머지 정점은 무한대로 초기화한다. 3) 최단 거리를 저장하는 배열에서 미방문 정점 중 가장 거리가 가까운 정점을 선택한다. 4) 해당 정점을 방문한 정점으로 저장한다. 5) 선택된 정점에 간선으로 연결된 인접한.. [Linux] shell basic command 1. manual - man (manual) 명령어에 대한 설명과 옵션들을 보여준다. ex) man [command] - clear clear the terminal screen 2. Navigating file system - pwd (print working directory) 현재 위치의 전체 경로를 출력한다. - ls (list) 현재 디렉토리 안에 있는 폴더와 파일들을 출력한다. ex) ls [-l, long] [-a, all] [directory_name] - open 해당 경로의 디렉토리를 파일 탐색기로 연다. ex) open . - cd (change directory) 경로로 준 위치, 디렉토리로 이동한다. '.'은 현재 경로, '..'은 상위 경로를 의미한다. '~'는 home dire.. [Python] argparser CLI에서 프로그램을 실행시킬 때 argument로 '-c', '--help' 등과 같은 옵션들을 줄 수 있다. 파이썬에서는 이러한 argument를 파싱하는 모듈로 argparse를 제공한다. argparse 모듈을 사용하여 사용자 친화적인 cli interface를 쉽게 작성할 수 있다. 이 모듈은 옵션으로 가능한 arguments를 정의하고, sys.argv를 어떻게 파싱할 것인가를 설정한다. 그리고 자동으로 help와 usage, issue error 등의 옵션을 생성해준다. 1. ArgumentParser class argparse.ArgumentParser(prog=None, usage=None, description=None, epilog=None, parents=[], formatter_c.. [Docker] Docker Compose compose는 multi-container Docker applications을 정의하고 실행하는 도구이다. docker compose에서는 YAML 파일을 통해 애플리케이션 서비스를 설정할 수 있다. compose 사용법은 기본적으로 3가지 단계를 거친다. app의 환경을 Dockerfile로 정의하여 어느 곳에서는 재사용할 수 있도록 한다. app의 서비스들을 docker-compose.yml 파일에 정의하여 독립된 환경에서 함께 동작할 수 있도록 한다. 'docker compose up' 명령어를 통해 전체 app을 실행시킨다. docker-compose binary를 사용하여 'docker-compose up' 명령어를 사용해도 된다. - docker-compose.yml version: "3... [Docker] Dockerfile 개념 정리 1. Dockerfile Dockerfile은 새로운 도커 이미지를 빌드할 때 사용하는 파일이다. Docker는 Dockerfile에 작성되어 있는 명령어를 읽어들여 자동으로 이미지를 빌드할 수 있다. Dockerfile은 텍스트 문서로 사용자가 이미지를 빌드하기 위한 명령어 들로 구성되어있다. Dockerfile을 실행하기 위해서는 'docker build' 명령어를 사용하여 실행한다. docker build 명령어 실행 시, Dockerfile에 작성되어 있는 명령어들로 도커 이미지를 빌드한다. 2. Usage 'docker build' 명령어는 Dockerfile의 내용과 context를 통해 이미지를 빌드한다. 빌드 context는 해당 위치의 PATH 또는 url에 있는 파일들의 집합을 의미한다.. 이전 1 ··· 17 18 19 20 21 22 23 ··· 31 다음