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

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개가 연결되어 있...

 좋은 해쉬 함수는     - 현실에서는 키들이 랜덤하지 않다.     - 만약 키들의 통계적 분포에 대해 알고 있다면, 이를 이용하여 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어렵다.     - 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 것이 바람직하다     -> 예시로 사람 이름이 Z로 시작하는 사람이 적고 A로 시작하는 사람이 많은 것 처럼     : 해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야 한다. 해쉬함수 Division 기법 h(k) = k mod m (사실 모든 해쉬함수들이 마지막에 하는 일 -> 마지막에 변환하는 일) ex) m = 20 and k = 91 -> h(k) = 11 장점 : 한번의 mod연산으로 계산, 따라서 빠름 단점 : 어떤 m 값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p 이면 키의 하위 p비트가 해쉬 함수값이 된다. 보통 이 전 단계에서 복잡한 과정을 거쳐서 마지막 과정에 division 기법 적용해서 사용하는데, 이전 단계에서 Multiplication 기법이나 기타등등을 통해서 사용 - 0에서 1 사이의 상수 A를 선택 : 0<A<1 (소수) - kA의 소수 부분만을 택한다 - 소수 부분에 m을 곱한 후 소수점 아래를 버린다. Hash code in Java - java의 Object 클래스는 hashCode() 메서드를 가진다. 따라서 모든 클래스는 hashcode()메소드를 상속받는다. 이 메소드는 하나의 32비트 정수를 반환한다. x.equals(y)이면 x.hashcode()==y.hashcode()이다. 하지만 역은 성립하지 않는다. Object 클래스의 hashCode()메소드는 객체의 메모리 주소를 반환하는 것으로 알려져 있다. 필요에 따라 각 클래스마다 이 메소드를 ov...

아웃룩 기본 설정 시 리본 메뉴에서 파일 탭이 없을 때 설정을 찾는 것이 아니다. 여기서 보면 우측 상단 위쪽의 이 버튼이 있다. [ ... ] 옆의 저 접기 버튼을 눌러서 리본 메뉴를 펴면 된다. 그러면 폴더 탭이 활성화되어 정상 사용 가능하다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import  org.json.simple.JSONObject; import  org.json.simple.parser.JSONParser; import  org.json.simple.parser.ParseException;   public   class  jsonSample {               public   static   void  main( String [] args) {                String  jsonString  =                        "{"                      +   "    \"resultcode\":\"200\","                      +   "...

 Open Addressing에 의한 충돌 해결      - 모든 키를 해쉬 테이블 자체에 저장      - 테이블의 각 칸(slot)에는 1개의 키만 저장           ㄴ 충돌이 생기면 다른 slot에 저장해야 한다.      - 충돌 해결 기법          : linear probing (기본적인 해결책)          : Quadratic probing          : Double hashing Linear Probing - probing은 먼저 해싱을 해서 그 칸이 비어 있으면 저장하고, 이미 다른 키에 의해 차 있을때 순서대로 검사를 해서 빈 슬롯에 저장하는 기법이다. h(k), h(k)+1, h(k)+2,... 순서로 검사하여 처음으로 빈 슬롯에 저장 테이블의 끝에 도달하면 다시 처음으로 circular 하게 돌아감 찾을 때도 자리 가서 보고 없으면 다시 순서대로 검사를 해야 한다. 이 Linear Probing의 단점은 clustering인데, 키들이 연속해서 뭉쳐져 있는 현상을 말한다. 그러면 cluster의 끝에 더덕더덕 붙을 확률이 커져서 cluster가 눈덩이처럼 길게 늘어나는 현상이 생길 수 있다. 그러면 cluster에 길이에 비례하여 속도가 저하되고, 원래 있어야 할 위치보다 멀리 저장되기 때문에 속도도 저하되고 cluster가 점점 커져서 더 느려지고 하는 현상이 발생한다. primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미 Quadratic probing     : 충돌 발생시 h(k), h(k)+1^2, h(k)+2^2 + h(k)+3^2 ... 순서로 시도한다.     - 리니어와 비슷하...

Https랑 Http랑 사용 하는 방식은 같은데 URL에 따라 사용 하면 된다. GET이랑 POST도 어짜피 동일해서 HttpURLConnection 만 GET 예제 만들었음. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 import  java.io.BufferedReader; import  java.io.DataOutputStream; import  java.io.IOException; import  java.io.InputStreamReader; import  java.net.HttpURLConnection; import  java.net.MalformedURLException; import  java.net.URL; import  java.nio.charset.Charset;   import  javax.net.ssl.HttpsURLConnecti...