내국인근로자 (정보통신업)

blogger 설정 -> 설정 -> 글 - 글 템플릿 (선택사항) script 형태로도 들어간다! buy me a coffee 태그 넣으려고 사용해 보았음.

 prim의 알고리즘 임의의 노드를 출발노드로 선택 출발 노드를 포함하는 트리를 점점 키워 감 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택

서로소인 집합들의 표현 - 각 직합을 하나의 트리로 표현 예 : 2개의 집합 disjoint한 집합 (sets) = 두 집합이 공집합이다. 집합의 각 원소들이 트리의 노드가 된다. 누가 루트이고 누가 누구의 부모이든 상관이 없다 트리의 각 노드는 자식노드가 아닌 부모 노드의 주소를 가진다. (상향식 트리) 이걸 모든 트리를 하나의 배열로 표현할 때 쓸 수 있도록 배열에 담아서 구현 할 수 있도록 가능하게 설명을 해 주신다... Find-set(v) : 자신이 속한 트리의 루트를 찾음 FIND-SET(x) if x != p[x]     then p[x] <- FIND-SET(p[x]) return p[x] o(h), h는 트리의 높이 h는 최악의 경우 o(n) Union(u,v) 한 트리의 루트를 다른 트리의 루트의 자식 노드로 만듬 UNION(u,v) x <- find-set (u); y <- find-set (v); p[x] <- y; 루트 노드를 찾은 이후에는 o(1) 하지만 루트를 찾는데 O(h) 이거는 그냥 u와 v가 속한 두 집합을 하나로 합치는 법이다 (전체  수도코드에 해당) Weighted Union : 두 집합을 union 할 때 작은 트리의 루트를 큰 트리의 루트의 자식으로 만듬!!!! ㄴ 오... -.-)... 더 큰 데에 그냥 합쳐버리면 전체 트리 레벨이 증가하지도 않음!!! 이것은 각 트리의 크기 (노드의 개수)를 카운트 하고 있어야 함 Path Compression 이거로 union find의 성능을 빠르게 해줄 수 있음! Find(g)  find를 할 때 트리를 위로 따라 올라가야 하는데, 올라가면서 자식 트리들을 다 노드의 자식으로 만드는 방식임! find 작업을 하며, 트리 높이를 줄이는 방식 (find 한 영역에 대해서만 줄어든다) -.-)...

 Kruskal의 알고리즘 에지들을 가중치의 오름차순으로 정렬한다. 에지들을 그 순서대로 하나씩 선택해간다. 단, 이미 선택된 에지들과 사이클(cycle)을 형성하면 선택하지 않는다. n-1개의 에지가 선택되면 종료한다. : 구현이 간단하지는 않다고 한다.  이것은 java 소스를 참조하겠음...

 최소신장트리 (Minimum Spanning Tree) 최소 비용 신장 트리 (MST) 입력 : n개의 도시, 도시와 도시를 연결하는 도로 비용 문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. 무방향 가중치 그래프 중 일부 에지만 선택하여 선택한 에지 기반으로 모든 노드들이 선택되게 한다. 선택된 에지가 다를 수 있어서, 해가 유일하지는 않다. (최소 경로가 여러 개 일 수 있음) 무방향 가중치 그래프로 G=(V,E) 각 에지 (u,v)∈E 에 대해서 가중치 w(u,v) 양수 이게 왜 트리라고 부르냐? 싸이클이 없는 연결된 무방향 그래프가 트리이긴 하다 MST 문제의 답이 항상 트리가 되는 이유는 노드 n개인 트리는 항상 n-1개의 에지를 가져서... 연결이 되어 있긴 함... -.-) 임의의 놈을 루트로 지정을 하고 인접한 노드를 자식으로 그려서 트리처럼 볼 수 있긴 함... Generic MST 알고리즘 어떤 MST의 부분집합 A에 대해서 Au{(u,v)} 도 역시 어떤 MST의 부분 집합이 될 경우 에지 (u,v)는 A에 대해서도 안전하다(safe)고 한다. Generic MST 알고리즘: 1. 처음에는 A=Φ 이다. 2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다. 3. 에지의 개수가 n-1개가 될 때까지 2번을 반복한다. = MST가 유일하지 않기 때문에, safe 요소를 검토해야 하는 건가 보다. 에지를 추가해도, MST 부분 집합이 될 경우에는 안전하다고 하나 보다. 안전한 에지 찾는 법은 그래프의 정점들을 두 개의 집합 S와 V-S로 분할한 것을 컷(cut) (S,V-S)라고 부른다. 에지(u,v) 대해서 u∈S이고, v∈V-S일 때 에지(u,v)는 컷(S,V-S)를 cross 한다고 말한다. 에지들의 부분집합 A에 속한 어떤 에지도, 컷 (S,V-S)를 cross하지 않을 떄 컷(S, V-S)는 A를 존중한다(respect)라고 말한다. = 공집합이 없는, 아무것도 건너가는 에지가 없을 떄 respe...

 DAG (Directed Acyclic Graph) 유향 비순환 그래프(directed acyclic graph, DAG, 유향 비사이클 그래프), 방향 비순환 그래프(방향 비사이클 그래프, 방향성 비사이클 그래프)는 수학, 컴퓨터 과학 분야의 용어의 하나로서 방향 순환이 없는 무한 유향 그래프이다. 즉, 무한히 수많은 꼭짓점과 간선으로 구성되며 각 간선은 하나의 꼭짓점에서 다른 꼭짓점으로 방향을 잇는데 이처럼 어떠한 꼭짓점 v에서 시작하여 끝내 다시 v로 돌아가 순환 반복되는 일정한 방향의 일련 한 간선을 따라가는 방법이 없다 . 다시 말해 DAG는 위상정렬이 있는 유향 그래프이다. 출처: https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%96%A5_%EB%B9%84%EC%88%9C%ED%99%98_%EA%B7%B8%EB%9E%98%ED%94%84 DAG는 방향 사이클(directed cycle)이 없는 방향 그래프 사이클 : 다시 자기 자신으로 돌아오는 경로 예시 : 작업들의 우선순위 예를 들면, 집을 지을 때 기초공사나 기둥세우기, 인테리어 등을 해야한다. 이 때, 기둥을 세우기 전에 인테리어를 할 수 없듯이 다른 것 보다 선행 되어야 하는 것들 표현 하기 위해 DAG가 유용하게 사용된다. 출처: https://new93helloworld.tistory.com/182 위상정렬 (topoligical ordering) DAG에서 노드들의 순서화 v1, v2, ... vn, 단, 모든 (vi, vj)에 대해서 i<j가 되도록 DAG에서는 우선순위를 표현하기 위해 위상 정렬을 사용한다. 위상 정렬이란, 작업을 실제로 한번에 하나씩 순서대로 처리한다면  어떤 순서로 작업해야 하느냐를 표현한 것이다. 즉, 작업의 순서대로 노드를 일렬로 정렬하는 것이다. 출처: https://new93helloworld.tistory.com/182 위상정렬 알고리즘 1 topoligicalSort1(G){...

깊이우선순회 (DFS) 1. 출발점 s에서 시작한다. 2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다. 3. 2번을 계속 반복한다. 이 것을 끝까지 반복한 뒤에, unvisited 의 이웃 노드가 없다면, 직전 노드로 되돌아가서 반복하는 방식으로 구현하면 된다. * 검색을 통한 공부.  참조: https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html 이것은 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식이다. 예시로 미로를 탐색할때 아예 한 방향으로 갈 수 있는데까지 가다가, 갈 수 없게 되면 다시 제일 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법이다. 그러므로 wide하게 탐색하기 전에 deep하게 탐색하는 것이다. 이것도 모든 노드를 방문하고자 하는 경우에 선택하는 방식인데. 이거 구현하는게 BFS보다 간단하긴 한데, 검색 속도 자체는 느리다. 이건 수도 코드를 보면 DFS(G, v)      visited[v] <- yes;     for each node adjacent to x do          if visited[v] = NO then               DFS(G, u);      end end 이건 되돌아가는 것이 중요한 코드인데, 만약에 disconnected인 그래프이거나, 방향 그래프면 DFS에 의해서 모든 노드가 방문되지 않을 수도 있어서 이것도 반복 시켜 줘야 하는 방식이다. 근데 얘는 시간에 대한 기대가 낮아서 DFS는 이해 가능. 이거 재귀 호출 식으로 구현 할 수도 있고 스택 같은데 넣어놓고 사용해도 되긴 한다... (근데 재귀로 짤...

 그래프 순회 (Graph Traversal) 순회     그래프의 모든 노드들을 방문하는 일 대표적 두 가지 방법     BFS (Breadth - First Search (너비우선순회))     DFS (Depth - First Search (깊이우선순회)) BFS는 동심원 형태로 노드를 방문하는 건데     이거는 모든 노드를 결국 다 방문하기는 하는데,     출발 노드를 주어지게 해 놓고 (없으면 임의 노드를 출발점으로 삼음)     인접한 노드를 먼저 탐색하는 방법이다.     출발노드 -> 모든 이웃 노드 -> 이웃 노드1의 모든 노드 .. -> 이웃노드 n의 모든 노드     이런 식으로 방문하는데,     속하지 않는 노드를 추가하는 방식으로 구현한다.     큐를 이용해서 너비우선순회를 하려면,     이미 방문한 노드를 check 하도록 해 놓고 (start 노드부터 check로)     큐에다가 start 노드를 첫번째로 삽입하고,      아직 방문되지 않은 노드를 찾아서 check로 바꾸고 또 삽입하고 하는 방식으로     루프를 돌려서 방문되지 않은 노드가 전체에 아무것도 없을 때까지 돌리면 됨 너비우선순회 수도코드는 도움을 받았음 (치기 귀찮았습니다...) BFS pesudo code 그래프 G, 출발 노드 S 00 BFS ( G , s ) 01   Q <- null ; 02   Enqueue ( Q , s ); 03   while Q != null do 04     u <- Dequeue ( Q ); 05     for each v adjacent ...

https://repo.spring.io/release/org/springframework/spring/ 위 URL로 가서 버전에 맞는 걸로 다운받은 뒤에 압축 해제한 zip 안에 있는 lib 쓰면 되는데, 필요한 거는 api 찾아보면 나온다. 라이브러리 뭐 쓰는지 모르면 https://www.findjar.com/ 위 URL에서 검색 하면 알려줌. ModelAndView MockUP으로 만들어 보려다가 또 찾기 귀찮아서 기재

 그래프 (Graph) (무방향) 그래프 G = (V,E) V : 노드 (node) 혹은 정점 (vertex) E : 노드쌍을 연결하는 edge 혹은 link 개체들 간의 이진관계를 표현 n = |V|, m = |E| 방향 그래프와 가중치 그래프 방향그래프(Directed Graph) G = (V,E) - 에지 (u,v)는 u로부터 v로의 방향을 가짐 가중치 그래프 - 에지마다 가중치(weight)가 지정 ㄴ 노드의 모든 에지마다 가중치라고 부르는 value를 지정해 주는 그래프이다.     노드에다가 직접 부여하지는 않고 에지에 부여함 그래프의 표현 인접행렬(adjacency matrix), 인접리스트 인접행렬 : 근처에 있는 애부터 시작해서 모든 노드를 조회하는 방식이다. = 연결 관계를 이차원 배열로 만들 수 있다. n x n 배열을 a[0][0] 부터 a[n][n] 까지 정의할 수 있음. 인접리스트 (adjacency list) 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트 - 저장 공간 : O(n+m) - 어떤 노드 v에 인접한 모든 노드 찾기 : O(degree(v)) 시간 - 어떤 에지 (u,v)가 존재하는지 검사 : O(degree(u)) 시간 참고 : https://sarah950716.tistory.com/12 방향그래프 인접행렬은 비대칭 인접 리스트는 m개의 노드를 가짐 가중치 그래프의 인접행렬 표현 - 에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장 - 에지가 없을 때 혹은 대각선: 특별히 정해진 규칙은 없으며, 그래프와 가중치가 의미하는 바에 따라서 표현 경로와 연결성 - 무방향 그래프 G= (V,E)에서 노드 u와 노드 v를 연결하는 경로(path)가 존재할 때 v와 u는 서로 연결되어 있다고 말함 모든 노드 쌍들이 서로 연결된 그래프를 연결된 그래프라고 한다 .(Connected graph) 연결 요소 (Connected component) : 노드 3개가 연결되어 있...