오뚝이개발자

개념 위상정렬이란 directed graph에서 꼭짓점을 방향성을 거스르지 않도록 정렬하는 방법이다. 실생활에서 대표적인 예시가 바로 선수과목(prerequisite)이다. 알고리즘 구현하는 방법은 아래와 같다. 연결성에 대한 정보를 가지고 인접리스트를 만든다. 이를 기반으로 in-degree(해당 vertex로 들어오는 선의 갯수) 정보를 담은 배열을 만든다. in-degree가 0인 vertex를 stack에 담는다. stack에서 pop하고 해당 vertex와 연결된 점들의 in-degree를 -1 한다. 3과 4를 반복하며 stack에서 pop 해줄 때마다 answer 리스트에 담으면 해당 결과가 위상정렬의 결과가 된다. 아래와 같은 그래프가 있다고 하면, in-degree(진입차수) 리스트는 아..

정렬 방법 중 가장 빠른 것은 O(nlogn)의 시간복잡도를 갖는다고 생각할 수 있다. 하지만 이보다 빠른 O(n)의 시간복잡도를 갖는 정렬방법도 있다. 바로 계수 정렬 다른 말로, 카운팅 정렬이다. 하지만 이러한 계수 정렬은 약간 제한된 조건 하에서 사용가능하다. 1 5 2 3 2 5 1 4 4 2 5 1 위와 같은 수가 나열되어있고 이를 정렬해보자. 그런데 자세히 보면, 위에서 등장하는 수의 범위가 1~5까지라는 것을 알 수 있다. 이처럼 수의 범위가 정해져 있는 경우 계수 정렬을 사용하면 효율적으로 정렬할 수 있다. 카운팅 정렬이란 말 그대로 수가 등장하는 횟수를 카운트 하는 것이다. 카운팅이 다 끝나면 크기 순서대로, 해당 수가 등장하는 횟수만큼 print해주면 된다. 위의 경우, 등장하는 수를 ..

DFS를 활용해 connected component의 갯수를 구하는 것이 필요할 때가 있다. 이럴 땐 탐색을 하면서 각 unit별로 구분을 해서 갯수를 카운트 해주면 된다. 정확히는 이를 union find 알고리즘이라고 한다. 예제를 통해 이해해보자. 아래 문제는 프로그래머스에 수록된 문제이다. programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr def dfs(start, n, visited, computers): fo..

학습목차 보안서비스 메시지와 대상에 대한 4가지 보안서비스 암호 대칭키 암호방식과 공개키 암호방식의 개념과 차이점 디지털 서명 필요성과 방법 가상사설네트워크(VPN) VPN의 필요성과 효과 보안서비스 암호학은 메시지의 기밀성(confidentiality), 무결성(integrity), 인증(authentication), 부인방지(non-repudiation)를 제공한다. 기밀성 : 메시지를 암호화 하는 것. 즉, 송수신자가 교환하는 메시지가 의도한 수신자에게만 유효하게 하는 것. 다른 말로 privacy 무결성 : 수신자에게 메시지가 정확히 보낸 그대로 도착하는 것. 전송 도중 우연히 혹은 의도적으로 변경이 없어야 함 부인방지 : 송신자가 자신이 보냈던 메시지에 대해서 부인할 수 없도록 하는 것(“나 그..

학습 목차 네트워크 관리 시스템 NMS/EMS의 차이점과 5대 관리기능 SNMP 인터넷 관리 표준의 구성요소 관리 프로토콜의 동작 모델 SNMP의 동작 8개 프로토콜 메시지의 종류와 의미 UDP 포트의 용도 네트워크 관리 시스템(NMS; Network Management System) 기관이 정한 요구사항을 만족하기 위해 네트워크 장비에 대해 모니터링, 시험검사, 설정, 문제진단을 하는 것 네트워크 관리를 수행하는 시스템을 NMS 단위 장비 집합을 관리하는 시스템을 EMS(ELement Management System)이라 함 NMS의 5가지 종류 구성관리(Configuration Management) 네트워크 관련 장비들의 구성현황 파악 및 설정관리 행위 네트워크 구성도를 잘 관리하는 것 장애관리(Fa..

학습 목차 TCP의 기능 수송 프로토콜로서 제공하는 서비스 세그먼트 형태 각 필드의 의미와 주요기능 연결설정과 해제 흐름제어 TCP의 기능 TCP는 프로세스간 통신, 스트림 전달 서비스(UDP는 하나의 메시지를 만들어 전달 but TCP는 바이트의 스트림을 전송), 전이중 통신(송수신 양방향), 연결지향서비스, 신뢰성 있는 서비스를 제공 연결설정과 해제 과정 존재 데이터의 안전한 도착을 확인하는 ACK를 사용해 신뢰성 있는 전송을 제공 프로세스 간의 통신을 위해 포트 번호 사용 스트림 전달 서비스 : TCP는 데이터를 바이트의 나열로 전달함 효율성을 위해 여러 바이트를 블록으로 구성된 세그먼트로 만들어 전송 TCP의 특징 TCP는 모든 바이트에 번호를 부여한다. 시작번호는 0~2^32 - 1 사이의 임의..

학습 목차 프로세스 간의 통신 수송계층 프로토콜과 프로세스 간의 통신의 읨 포트번호의 종류와 클라이언트/서버 모델 사용자 데이터그램 프로토콜(UDP) 메시지 형태와 필드 설명 UDP의 특징과 사용되는 영역 각 계층별 프로토콜의 데이터 전달 데이터링크 계층 : 이웃한 두 노드 사이의 프레임 전달에 관여(node-to-node) 네트워크 계층 : 두 호스트 사이의 패킷 전달에 관여(host-to-host) 수송 계층 : 프로세스 사이의 메시지 전달에 관여(process-to-process), 포트번호(프로세스의 구별을 위해 사용되는 논리적 포트번호, 실제 물리적 포트가 아님)가 프로세스간의 전달에 사용됨 클라이언트/서버 구성 프로세스 간의 통신은 클라이언트/서버 구성을 통해 이루어진다. 포트 번호는 수송 계..

학습 목차 멀티캐스팅 멀티캐스팅의 의미와 주소 사용 멀티캐스트 그룹관리 그룹관리 프로토콜을 사용한 가입/탈퇴/모니터링 방법 멀티캐스트 라우팅 멀티캐스트 라우팅의 라우팅 종류와 방법 멀티캐스트 라우팅의 트리 구성 방법 멀티캐스팅 멀리캐스팅 전송은 하나의 송신자와 그룹에 속한 다수의 수신자와의 통신형태(일대 다의 관계) 송신자는 유니캐스트 주소를 사용 BUT 목적지는 그룹 주소인 D클래스 주소 사용 다중 유니캐스팅(Multiple Unicasting) 유니캐스팅을 이용해 멀티캐스팅과 유사한 효과를 내도록 동작하는 것으로 그룹에 속한 대상이 10곳이면 10곳에 모두 보내는 방식. 그러나 목적지가 많아지면, 처음 패킷과 마지막 패킷 간 지연시간이 발생 이에 따라 대역폭을 소모(멀티캐스팅으로 1개만 보내면 되는 ..