전공공부
-
위상정렬 (topological sorting)전공공부/알고리즘&자료구조 2020. 1. 26. 18:31
참고: https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html [알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 위상 정렬(Topological Sort)을 이용한 기본적인 해결 방법 위상정렬 순서 1. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다. 초기에 간선의 수가 0인 모든 정점을 큐에 삽입 2. 선택된 정점과 여기에 부속된 모든 간선을 삭제 선택된 정점을 큐에서 삭제 선택된 정점에 부속된..
-
2. 데이터 전송기술과 전송미디어전공공부/컴퓨터 네트워크 2020. 1. 20. 14:22
목차 1. 데이터 전송과 신호의 개념 2. 신호 전송과 정보이론 3. 데이터 전송과 전송모드 4. 다중화 기법과 교환기술 5. 전송미디어와 전송특성 1. 데이터 전송과 신호의 개념 신호(signal)란? 정보의 전송은 실제로는 신호의 전송 과정이다. 신호란 정보의 전송과 관련된 개념으로, 전자기 신호는 전압이나 전류에 대한 파형으로 나타난다. 신호는 에너지 신호와 전력 신호, 랜덤 신호와 결정 신호, 주기신호와 비주기 신호 등으로 구분 2. 신호 전송과 정보이론 정보이론 정보원과 통신채널에 관한 현대적 정보이론의 통계적 모델: Shannon에 의하여 기초 확립 정보이론: 정보의 '수량화', 정보를 전송할 수 있는 '통신채널의 용량', 전송효율의 향상과 에러의 감소를 위한 '부호화 기술'등 기본이론 포함 ..
-
1. 데이터통신과 네트워크의 개요전공공부/컴퓨터 네트워크 2020. 1. 20. 13:42
목차 1. 데이터통신의 개념 2. 네트워크의 구조 및 동작 3. 네트워크 표준화 4. 유무선 네트워크의 발전 및 진화 1. 데이터통신의 개념 초연결 사회란? 스마트폰이나 웨어러블 초소형 컴퓨터 같은 모바일 기기를 통해 사람과 사물, 동물, 데이터, 프로세스 등 모든 것이 인터넷으로 긴밀하게 연결된 사회 사물인터넷, 사물지능통신(M2M: Machine to Machine) 유 무선 통신 네트워크로 연결된 기기들이 사람의 개입 없이 센서 등을 통해 수집한 정보를 서로 주고받아 스스로 일을 처리 데이터 통신과 네트워크 데이터(data)란? 이를 만들어서 사용하는 사용자들에 의해 합의된 형식으로 facts, concepts, instructions 등을 표현 한것 데이터통신(data communication)이..
-
순열과 조합전공공부/알고리즘&자료구조 2020. 1. 12. 22:33
조합 출력 문제 출처:https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 소스코드 순열 출력 문제 출처:https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다. www.acmicpc.net 소스코드
-
확장 유클리드 호제법전공공부/알고리즘&자료구조 2020. 1. 12. 22:24
유클리드 호제법을 활용하여 최대공약수를 구할 수 있다. 그리고 유클리드 호제법을 응용하여 일차방정식의 해를 쉽게 구할 수 있는 방법이 확장 유클리드 호제법 방법이다. ax + by = c 라는 방정식이 있다고 하자. 1. 좌변과 우변의 공약수가 있는 경우 약분을 하고, 우변의 값이 gcd(a,b)의 배수인 경우 gcd(a,b)로 변경한 후 해를 구한다. 그래서 gcd(a,b)가 서로소인 경우 우변을 1로 놓을 수 있다. 반대로 예를들어 162x+42y=19의 경우 19가 gcd(162,42)=6의 배수가 아니므로 해가 존재하지 않는다. a,b,c가 입력값으로 주어져 있다고 하자 먼저 확장 유클리드 호제법을 적용하기 전에 gcd(a,b)의 값이 1이라면 그렇다면 먼저 방정식을 ax + by =1 로 변환 ..
-
트라이 (Trie)전공공부/알고리즘&자료구조 2020. 1. 12. 21:53
출처: https://www.crocus.co.kr/1053 [Crocus] 트라이(Trie) 자료구조 목차 1. 트라이(Trie)란? 2. 트라이(Trie) 이해하기 3. 트라이(Trie)의 단점 4. 트라이(Trie) 접목하기 5. 트라이(Trie) 문제 풀어보기 트라이(Trie)란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합.. www.crocus.co.kr 트라이 (Trie)란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 자료구조이며, 우리가 원하는 원소를 찾는 작업을 O(n)에 (단어길이 만에) 해결 할 수 있는 자료구조이다. 알파벳을 저장하려면 Trie 구조체 안에 Trie* next[26] 과 같이 포인터배열로 정의 할 수 있다. 그리고 f..
-
세그먼트 트리 (segment - tree)전공공부/알고리즘&자료구조 2020. 1. 12. 21:33
세그먼트 트리는 해당 포스트에 설명이 잘 돼있다. 출처: http://isukorea.com/blog/home/waylight3/216 세그먼트 트리(Segment Tree) / 인덱스 트리(Index Tree) :: 강의/IT/알고리즘 :: ISU 블로그 void update_range(int node, int begin, int end, int left, int right, int diff) { update_lazy(node, begin, end); if (end
-
최소, 최대 힙 (min & max heap)전공공부/알고리즘&자료구조 2020. 1. 12. 21:09
출처:https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 자료구조 ‘힙(heap)’이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이..