쥬코딩

오늘은 Dijkstra's link state 알고리즘에 대해 알아보겠습니다. link state는 이웃의 정보를 모두에게 전달 즉, broadcast 해줍니다. 다시 말하자면 자신과 연결된 노드의 정보를 모두에게 알려주고, 각각의 라우터는 자신으로부터 다른 노드들까지 최소 길이를 각자 계산하게 됩니다. 아래 그림의 상황에서 Dijkstra알고리즘이 시행되는 과정을 표로 나타내보았습니다. step start D(v), p(v) D(x), p(x) D(w), p(w) D(y), p(y) D(z), p(z) 0 u 2,u 3,u 4,u infinite infinite 1 uv 2 uvx 12,x 3 uvxw 9,w 8,w 4 uvxwz 5 uvxwzy

네트워크 2021. 12. 17. 09:02

오늘은 링크계층과 네트워크계층의 addressing과 fowarding에 대해 알아보겠습니다. datagram이 전달될 때 링크 계층의 헤더에는 다음 노드의 MAC address가 저장되어있습니다. 따라서, 링크 계층의 헤더는 packet이 라우터를 지나갈 때마다 바뀌게 됩니다. 네트워크 계층의 헤더에는 최종 도착지의 IP address이 저장되어있습니다. 따라서, 네트워크 계층의 헤더는 packet이 라우터를 지나갈 때에도 바뀌지 않습니다. datagram이 B에서 A로 전달되는 상황이라고 가정하겠습니다. 위치 (3)에서 source MAC address: 07-00-ED-48-6D-53 destination MAC address: 0F-B5-F5-10-F9-A4 source IP address: 12..

네트워크 2021. 12. 16. 13:33

오늘은 시프트 연산자를 사용해서 알파벳을 이진수로 나타내보겠습니다. 알페벳과 1000000(이진수)를 &연산과 시프트연산을 하면 알파벳을 이진수로 나타낼 수 있습니다. 알파벳과 1000000(이진수)를 &연산 수행 후 1000000(이진수)를 오른쪽으로 1번 시프트를 하고, 다음 비트에 대해 수행을 하면 됩니다. #define _CRT_SECURE_NO_WARNINGS #include void shiftOperation(char ch) { int mask = 0x80; //1000000 for(int i = 0; i > 1; } } void main() { shiftOperat..

c언어 2021. 12. 15. 14:55

오늘은 삽입정렬을 이용해서 오름차순으로 정렬하는 방법에 대해 알아보겠습니다. 오름차순으로 정렬하기 위해서는 정렬할 값과 정렬된 배열의 끝(가장 큰 수)부터 차례대로 비교해가면서 알맞은 자리에 삽입하면 됩니다. 정렬되지 않은 부분은 하늘색, 정렬된 부분은 보라색으로 표시하겠습니다. 처음에는 인덱스가 0인 부분만 정렬된 상태이고 그 뒤의 숫자는 정렬되지 않은 즉, 정렬할 값이라고 생각하면 됩니다. 배열 위의 화살표는 현재 삽입정렬을 할 숫자이고, 배열 밑의 화살표는 삽입정렬 수행 시 비교하는 숫자들과 연결한 것입니다. 현재 삽입정렬를 할 숫자를 key라고 부르겠습니다. 반복문을 돌면서 정렬된 부분(보라색 부분)의 숫자가 key값보다 크면 뒤로 한칸씩 밀어주고, 만약 정렬된 부분(보라색 부분)의 숫자가 key..

알고리즘 2021. 12. 14. 14:49

안녕하세요 지코딩입니다. 오늘은 linked list에 값을 추가 및 삭제하는 방법에 대해 알아보겠습니다. 오름차순의 linked list에 새로운 노드를 추가할 때 필요한 조건은 3가지로 나눌 수 있습니다. 조건 1. 이미 같은 값이 linked list에 존재할 때 조건 2. linked list에 있는 모든 값보다 작을 때, 또는 어떤 값보다 작고, 어떤 값보다는 클 때 (즉, linked list의 중간에 저장되어야 할 때) 조건 3. linked list에 있는 모든 값보다 클 때 (즉, linked list의 맨 마지막에 저장되어야 할 때) 조건 1의 경우에는 새로운 노드를 추가하는 함수를 탈출하면 됩니다. 조건 2 새로운 linked list 생성 전 상태를 그림으로 나타내면 다음과 같습니다..

c언어 2021. 12. 14. 10:00

안녕하세요 지코딩입니다. 오늘은 선택정렬을 이용해서 오름차순으로 정렬하는 방법에 대해 알아보겠습니다. 오름차순으로 정렬하기 위해서는 정렬되지 않은 배열 인덱스 중 가장 작은 값을 선택해서 정렬되지 않은 부분의 맨 앞의 값과 자리를 바꾸면서 진행하면 됩니다. 정렬되지 않은 부분은 하늘색, 정렬된 부분은 보라색으로 표시하겠습니다. 처음에는 배열의 모든 인덱스가 정렬되지 않은 상태입니다. 정렬되지 않은 인덱스 중 가장 작은 값을 찾고 정렬되지 않은 배열 부분의 맨 앞의 값과 자리를 바꿉니다. 위의 과정을 반복하면 다음과 같습니다. 마지막 남아있는 수는 전체 배열 중 가장 큰 수 이면서 정렬되지 않은 배열 인덱스 중 가장 작은 수 이기 때문에 따로 정렬을 하지 않아도 됩니다. 이제 전체 코드를 공유하겠습니다. ..

알고리즘 2021. 12. 13. 11:57

오늘은 오름차순으로 값을 정렬하는 linked list를 만들어보겠습니다. linked list를 생성하기 위해 필요한 것은 구조체와 head입니다. 구조체는 값을 저장할 변수와 다음 노드의 주소를 가르키는 포인터변수로 이루어져 있습니다. head는 위에서 설명한 구조체 타입의 변수이고, linked list의 맨 처음 값을 가르키는 역할을 합니다. (그렇기 때문에 아무값도 저장되어있지 않습니다.) head는 linked list의 맨 앞에 새로운 값을 넣고 싶을 때 유용하기 때문에 사용합니다. 오름차순의 linked list를 생성할 때 필요한 조건은 3가지로 나눌 수 있습니다. 조건 1. linked list를 처음 만들 때 (즉, linked list에 아무것도 없는 상태에서 처음 값을 저장할 때)..

c언어 2021. 12. 13. 09:48

오늘은 백준 10845번 큐 문제풀이를 해보겠습니다. 명령어 하나씩 어떻게 구현할지 설명해보겠습니다. 일단, 인덱스를 -1로 초기화한다. -명령어가 push라면: 정수 하나를 입력받아서 배열의 (인덱스+1) 위치에 넣는다. 그 후, 배열의 인덱스를 하나 증가시킨다. -명령어가 pop이라면: 만약 현재 인덱스가 0보다 작다면(증가되지 않고 처음 초기화한 상태 그대로라면) -1을 출력한다. 아니라면 배열의 인덱스 0에 있는 값을 출력한다. 그 후, 뒤에 저장된 값들을 한칸씩 앞으로 당기고 인덱스 값을 하나 줄여준다. -명령어가 size라면: 현재 인덱스값에 1을 더한 값을 출력한다. -명령어가 empty라면: 현재 인덱스가 0보다 작다면 배열이 비어있다는 의미이기 때문에 1을 출력한다. 아니라면 0을 출력한..

자료구조 2021. 11. 19. 14:27