![]()
본 내용은 Computer networking : a top-down approach 책을 바탕으로 정리하였습니다. Index 1. 인터넷, 네트워크 프로토콜이란 무엇인가? 2. Network edge, core 3. 네트워크에서의 딜레이, 손실, 처리량 4. 프로토콜 레이어 5. 네트워크의 역사 1. 인터넷, 네트워크 프로토콜이란 무엇인가? 1.1 인터넷이란? "수많은 네트워크들을 연결하는 네트워크"라는 의미에서부터 시작되었으며 클라이언트와 서버가 있고, TCP/IP라는 기본 프로토콜을 통해 제공되고 있다. 1.2 인터넷의 구성 요소 구조적 관점에서 인터넷을 구성하는 요소들은 크게 3가지가 있다. 1. host : end system 이라고도 하며, 연결된 수많은 컴퓨팅 단말들을 의미한다. ex) 컴퓨..
![]()
접두사를 찾는 문제로 트라이를 이용하여 간단하게 풀 수 있는 문제입니다. 트라이란? https://suhwanc.tistory.com/98 주어진 문자열들을 (0 ~ 9) 정렬한 후, 뒤에서 부터 트라이에 이 문자열이 있는지 find 하고 없으면 insert를 반복해 전화번호 목록의 일관성을 찾아내면 됩니다. 소스 코드 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 #include #include #incl..
![]()
보통 우리가 많은 양의 정수, 실수형 배열에 대한 구간 합, 최대치 등을 구할 경우 구간 트리(세그먼트 트리, 펜윅 트리)를 만들어 O(log n) 만에 검색을 할 수 있게 된다. 하지만 문자열을 다룰 때에는 정수, 실수 등 크기가 정적인 변수들을 다루는 것과 좀 다른데 문자열의 경우 문자열 변수를 비교하는 데에 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문이다. (정수처럼 한 번에 비교가 되는 자료형이 아니기 때문입니다.) 따라서 정수형 배열에서 원하는 원소를 찾을 때 O(log n)이 걸렸다면, 같은 알고리즘으로 원하는 문자열을 찾으려면 문자열의 길이 |S|을 곱한 O(|S| log n) 이 걸리게 된다. 이런 문제를 해결하기 위해 문자열을 찾는 문제에서 우리는 더 나은 자료 구조를 찾을 ..
![]()
PageRank란? PageRank는 하이퍼링크 구조를 가지는 문서에 상대적 중요도에 따라 가중치를 부여하는 방법이다. PageRank Algorithm은 더 중요한 페이지가 더 많은 사이트로부터 링크를 받는다는 것에 비롯되었는데, 만약에 page A, B, C, D 가 있을 때 page A에서 원하는 결과를 찾지 못해서 page B로 방문했을 경우 page B는 임의의 확률 x 1/3 만큼의 pagerank를 받게 된다. 이렇게 PageRank 값을 page 간에 주고받는 것을 반복하다 보면, 전체 웹 페이지가 특정한 PageRank값에 수렴하는데, 이를 통해 최종 PageRank값을 계산할 수 있다. 식으로 나타내면, 초기 PageRank r 을 설정하고, 인접 행렬(각 page 간 방문 빈도) L을..
![]()
이번엔 eigen vector와 eigen value에 대해 알아보려 한다. eigen vector란? eigenvector란 우리말로 고유 벡터라고 하는데, 선형 변환(transform)이 일어난 후에도 방향이 변하지 않는 영 벡터가 아닌 벡터이다. eigen value란? eigenvalue는 우리말로 고윳값이라 하며, eigenvector의 길이가 변하는 배수를 선형 변환의 그 eigenvector에 대응하는 eigenvalue라고 부른다. 여기서 주의할 점은 길이가 변하는 것이지 방향의 변화는 없다는 것이다. 이 둘을 식으로 나타내자면, matrix A에 대하여, Ax = λx (lambda는 상수)가 성립하는 0이 아닌 x vector가 존재할 때 λ를 matrix A의 eigenvalue, x..
![]()
오늘은 PIL(Python Image Library) 모듈을 사용하여 python에서 이미지를 다루어 보려고 한다. 1. 이미지 불러오기 먼저 이미지 파일(. png,. jpeg 등)이 필요한데, 나는 병아리 이미지(png 파일)를 가져왔다. 이 이미지의 크기는 256x128 이며 보통 [너비, 높이] 순서이다. 그럼 이제 python에서 이미지를 가져와보자. 1 2 3 4 from PIL import Image image = Image.open("img.png") image.show() 위 코드를 입력하고 실행하면 위와같은 사진이 열린다. 잘 불러왔다는것을 알 수 있다. 2. 이미지 array 변환 그럼 이 사진을 array로 바꿔보자. numpy.asarray 함수로 이미지를 array로 바꿀 수 있..
![]()
ac 코드입니다 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 #include #include using namespace std; //현재 다른 점에 지배당하지 않는 점들의 목록을 저장 //coords[x] = y map coords; //새로운 점(x,y)가 기존의 다른 점들에 지배당하는지 확인한다. bool isDomianted(int x, int y) { //x보다 오른쪽에 있는 점 중 가장 왼쪽에 있는 점을 ..
![]()
오늘은 그람 슈미트 직교화와 반사 행렬에 대해 알아보자. 1. gram-schmidt 직교화우선 gram-schmidt 직교화의 의미를 위키백과에 검색해보면"내적 공간에서 유한 개의 일차 독립 벡터 집합을 정규 직교 기저로 변환하는 방법이다"라 한다.(출처 : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%8C-%EC%8A%88%EB%AF%B8%ED%8A%B8_%EA%B3%BC%EC%A0%95) 의미를 조금 해석해보자면,1) 일차독립 벡터 집합은 벡터 집합 내의 모든 벡터들이남은 다른 벡터들의 일차 결합으로 나타낼 수 없는 벡터들의 집합을 의미하는데 여기서 일차 결합이란, 벡터들과의 사칙연산을 말한다. 따라서 예를 들어 v = [[1,0,0], [0,1,0], [0,0..
AC 코드 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 #include #include using namespace std; int main() { int c; scanf("%d", &c); while (c--) { stack st; string s; cin >> s; bool check = true; for (int i = 0; i
![]()
AC 코드입니다. 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 #include #include #include #include using namespace std; int waysToBuy(const vector& psum, int k) { const int MOD = 20091101; int ret = 0; vector count(k, 0); //overflow를 방지 for (int i = 0; i
데큐(dequeue) 를 이용한 간단 풀이입니다 AC 코드 1234567891011121314151617181920212223242526272829303132333435363738#include #include #include using namespace std; int main(){ int c; scanf("%d", &c); while (c--) { int n, k; scanf("%d %d", &n, &k); int ans; deque dq; for (int i = 2; i
AC 코드입니다. 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 #include #include #include using namespace std; const int INF = 987654321; int n, k, m, l; //prerequisite[i] = i번째 과목의 선수과목 집합 int prerequisit..
