1. 기본 union find 알고리즘의 문제점 기본적인 union find 알고리즘을 사용할 경우 union을 수행하면.. 예를 들어 최악의 경우 위와 같은 union이 형성될 수 있다. 1의 대표자를 찾을 때, 2번, 3번, 4번을 확인하고 나서야 5번을 확인하여 1의 대표자가 5이구나 라는 것을 알 수 있다 이렇게 구성되는 경우 노드의 개수가 v개이고 간선의 개수가 m개이면 최악의 경우 O(VM)이라는 비효율적인 알고리즘이 된다. 특히 모든 1,2,3,4,5의 루트 노드가 5번인데 굳이 하나씩 거슬러 올라가서 전부 확인해야하나? union 그래프가 위와 같이 구성된다면, 2,3,4의 루트 노드는 단 1번만 5를 검사하면 바로 알 수 있으므로 효율적이다. 2. 경로압축(path compression)..
1. 그래프 기본 개념 간단히 복습 크루스칼 알고리즘 >>> 그리디 알고리즘 위상 정렬 알고리즘 >>> 큐, 스택자료구조를 이용 ---------------------------------------------------------------- 그래프(graph)란 노드(node)와 노드 사이 연결된 간선(edge)의 정보를 가지고 있는 자료구조 알고리즘 문제를 풀 때, "서로 다른 개체(객체)가 연결되어있다"라고 한다면 그래프 알고리즘을 가장 먼저 떠올려야한다. 예를 들어 "여러개의 도시가 연결되어 있다"라고 한다면 그래프 알고리즘을 의심할 필요가 있다 ----------------------------------------------------------------- 그래프 자료구조 중 트리 자료구조..
1. 기본 스택 구현 방문배열 visited 초기화 첫 시작정점 v를 방문 처리 그 후 탐색 반복문 수행 v에 인접한 정점 w중에서 아직 방문하지 않은 w를 찾으면, 이미 방문한 v를 스택에 넣고 v를 w로 교체한 후에, w를 방문처리하고 바로 break 그 후 다시 w에 인접한 정점중에서 방문하지 않은 정점을 찾으면, w를 스택에 넣고 새로운 정점으로 교체한 뒤에 방문처리하고 반복 수행 더 이상 방문할 곳이 존재하지 않는다면 스택이 비어있는지 검사한다 스택이 비어있다면, 전체 탐색을 종료 스택이 비어있지 않다면, 하나씩 pop하여 다시 인접한 정점중에서 방문하지 않은 정점이 존재하는지 탐색 수행 visited = [0] * n def dfs(v,visited): visited[v] = 1 stack =..
1. 그래프의 기본 구조 그래프는 노드(node)와 간선(edge)으로 표현되고 이때 노드를 정점(vertex)이라고도 말한다 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다'(adjacent)라고 말한다 노드를 도시, 간선을 도로라고 생각해보자. A라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해서 A와 B를 연결하는 도로(간선)를 거친다고 이해하면 쉬울 것이다 2. 프로그래밍에서 그래프를 표현하는 방식 인접행렬(adjacency matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접리스트(adjacency list) : 리스트로 그래프의 연결 관계를 표현하는 방식 인접행렬 방식은 2차원 배열에 각 ..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A,B,C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. ..
1. 패키지 설치 ggplot2 패키지는 다양한 시각화 그래프를 지원 install.packages('ggplot2')는 ggplot2 패키지를 설치 library(ggplot2)는 ggplot2의 내장 데이터 및 함수를 활용하기 위해 라이브러리를 활성화 시킴 install.packages에는 ''가 들어갈 수 있지만 (안들어가도 됨) library에는 ''가 들어가면 안된다 > install.packages('ggplot2') Installing package into ‘/cloud/lib/x86_64-pc-linux-gnu-library/4.1’ (as ‘lib’ is unspecified) trying URL 'http://rspm/default/__linux__/focal/latest/src/co..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
