본문 바로가기

Computer Science35

BFS / DFS 참고용 블로그 https://yabmoons.tistory.com/99 [ 순열과 조합 구현 ] - 재귀를 통한 구현(1 - 조합) (C++) 브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는결과 값을 찾는 방식이다. 이 글에서는, 순열과 조합을 STL을 사용하지 않 yabmoons.tistory.com https://blog.naver.com/kks227/220786417910 백트래킹(Backtracking) (수정 2019-10-09) 탐색 중에서는 가장 마지막으로 쓰는 글이 아닐까 싶습니다. 이제 DFS와 BFS도 익혔으니, 백트래킹(b... blog.naver.com https://foameraserblue.tistory.com/m/188 PS를 .. 2023. 4. 1.
컴퓨터 네트워크: IPv4 Address - Special Addresses, NAT IPv4 Address 4. Special Addresses classful addressing에서 일부 주소는 특수 목적을 위해 예약되어 있었다. classless addressing 체계는 classful addressing에서 이러한 특수 주소 중 일부를 상속한다. All-zero address 고정 IP 컴퓨터를 껐다 켜도 IP가 바뀌지 않는 것. 사이트 운영 시 사용. ex) 네이버, 다음, 쿠팡, 11번가, 개인쇼핑몰 등... 유동 IP 일반 가정집에서 사용하는 모든 IP. 컴퓨터 부팅 시 마다 누군가에게 할당받아야 함. Dynamic Host Configuration Protocol(DHCP) 클라이언트는 네트워크 부팅과정에서 DHCP 서버에 IP주소를 요청하고 DHCP는 클라이언트에게 동적.. 2021. 12. 2.
컴퓨터 네트워크: IPv4 Address - Classless Addressing(2) IPv4 Address 3. Classless Addressing Variable –Length Blocks Two-Level Addressing Block Allocation Subnetting Example 5.33 (각 subnet의 크기가 다른 경우) 조직에 시작 주소가 14.24.74.0/24인 주소 블록이 부여된다. 조직은 아래와 같이 3개의 subnet에서 사용할 3개의 주소 subblock을 필요로 한다. ■ 120개 주소의 subblock 한 개 ■ 60개 주소의 subblock 한 개 ■ 10개 주소의 subblock 한 개 답 이 블록에는 2^(32 - 24) = 256개의 주소가 있다. 첫 번째 주소는 14.24.74.0/24이고 마지막 주소는 14.24.74.255/24이다. *서.. 2021. 12. 2.
컴퓨터 네트워크: IPv4 Address - Classless Addressing(1) IPv4 Address 3. Classless Addressing Variable –Length Blocks Two-Level Addressing Block Allocation Subnetting Variable-length blocks in classless addressing classless addressing에서는 클래스라는 단위 자체가 없어졌기 때문에 블록의 크기도 유동적이다. Prefix and suffix classless addressing에서 prefix는 network를, suffix는 host를 정의한다. classless addressing에서 prefix 길이는 1~32 사이이다. Example 5.22 전체 인터넷이 4,294,967,296개의 주소를 가진 하나의 블록으로 간주될.. 2021. 12. 2.
컴퓨터 네트워크: IPv4 Address - Classful Addressing IPv4 Address 2. Classful Addressing IP주소(or 인터넷 주소): TCP/IP 프로토콜의 IP layer에서 인터넷에 연결된 각 장치를 식별하기 위해 사용되는 식별자. IPv4 주소: 32bits. 전세계에 하나분인 유일한 주소. 2^32(약 40억)개의 IP주소가 존재. Occupation of address space 2^32 = 약 40억개 주소 존재Class A: 2^31, 약 20억개 , 50% Class B: 2^30, 약 10억개 , 25% Class C: 2^29, 약 5억개 , 12.5% ...(생략) Finding the class of address Q1. 주어진 주소에 대한 Class 찾기 a. 00000001 00001011 00001011 111011.. 2021. 12. 1.
컴퓨터 네트워크: IPv4 Address - Introduction IPv4 Address 1. Introduction IP주소(or 인터넷 주소): TCP/IP 프로토콜의 IP layer에서 인터넷에 연결된 각 장치를 식별하기 위해 사용되는 식별자. IPv4 주소: 32bits. 전세계에 하나분인 유일한 주소. 2^32(약 40억)개의 IP주소가 존재. Dotted-decimal notation 원래 IP주소는 binary 형태의 32bits짜리 숫자이다. 의사소통을 원활하게 하기 위해 이를 byte단위로 끊어 10진법으로 표현하여 사용한다. 2진법 ↔ 10진법 Example 5.1 IPv4 주소 binary 표기법 → dotted-decimal 표기법 a. 10000001 00001011 00001011 11101111 ☞8bit가 다 1이면 255 b. 110000.. 2021. 11. 27.
컴퓨터 네트워크: Options TCP: Transmission Control Protocol 11. Options TCP 헤더에는 최대 40바이트의 optional information이 포함될 수 있다(옵션을 안 쓴 기본 헤더는 20바이트. 따라서 헤더는 20 - 60바이트). 옵션은 대상에 추가 정보를 전달하거나 다른 옵션을 정렬한다. 우리는 크기에 따라 single-byte options과 multiple-byte options 두 가지 범주의 옵션을 정의할 수 있다. Options single-byte options ☞ 아무 일도 안 함 end of option list no operation multiple-byte options maximum segment size window scale factor timestamp SA.. 2021. 11. 27.
컴퓨터 네트워크: TCP timers TCP: Transmission Control Protocol 10. TCP timers TCP timers Retransmission timer: 재전송 타이머, time-out detect 시 사용, packet loss를 detect하면 slow start로 들어감 Persistence timer: 영속 타이머 Keepalive timer TIME-WAIT Retransmission timer time-out detect 시 사용 Persistence timer Lost acknowledgments가 적절히 처리되지 않은 경우 deadlock이 발생할 수 있다. Receiver가 rwnd=0을 보내 Sender가 데이터 송신을 멈춘 상황. Receiving Buffer에 MSS만큼의 공간이 생기거나.. 2021. 11. 11.
알고리즘10. Heapsort 4. Sorting 4-4. Heapsort Heap and Heapsort Heap: 우선순위 큐 구현 방법 max-heap 기준1. insert()2. findMax()3. deleteMax()3가지 함수를 이용해 정렬 Heap data structure는 특수 속성을 가진 binary tree이다. Heap Structure →구조 Partial order tree property(부분 정렬 트리 속성) →순서 Heap Structure binary tree T는 다음 조건을 만족하는 경우에만 heap structure (h = 트리의 height) 1. T is complete at least through depth h-1 →depth h-1까지 트리가 꽉 차 있다 2. All leaves ar.. 2021. 11. 11.
알고리즘: Mergesort 합병 정렬 4. Sorting 4-3. Mergesort 합병 정렬 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있을 때 사용. 정렬 문제의 문제 복잡도 F(n) = O(n lgn) time 합병 정렬의 worst case complexity W(n) = O(n lgn) time W(n) = F(n) : Optimal algorithm 따라서 합병 정렬 알고리즘은 Optimal algorithm 이다. Merging Sorted Sequences Problem 오름차순으로 정렬된 두 리스트 A, B를 새로운 리스트 C로 합친다. Strategy A와 B.. 2021. 11. 11.
컴퓨터 네트워크 실습 소켓 생성 (전화기 생성) #include int socket(int domain, int type, int protocol); 성공 시 파일 스크립터, 실패 시 -1 반환 소켓의 주소 할당 및 연결 (전화기에 번호 부여) #include int bind(int sockfd, struct sockaddr *myaddr, socklen_t addrlen); sockfd: 소켓번호 struct sockaddr *myaddr: 주소(ip, port) 구조체 성공 시 0, 실패 시 -1 반환 연결요청이 가능한 상태로 변경 (전화 받기 가능) #include int listen(int sockfd, int backlog); 일반 소켓을 서버소켓으로 바꿔줌. 일반 소켓은 걸 수만 있고 받을 수는 없음. listen.. 2021. 10. 16.
컴퓨터 네트워크: Congestion Control TCP: Transmission Control Protocol 9. Congestion Control Congestion 링크가 보낼 수 있는 Maximum 값이 100Mbps인 상황에서 TCP connection 1, 2에서 각각 100Mbps, 총 200Mbps가 들어오면 Congestion 발생 Packet delay and network load Delay 데이터 처리 속도가 얼마나 지연되는지 Load 데이터가 얼마나 들어가는지 input의 합이 100Mbps에 가깝게 되면 delay갑자기 증가 Throughput versus network load Throughput (=receiving rate) 데이터를 얼마나 빠르게 받고 있는지 Load 데이터가 얼마나 들어가는지 ex. 50Mbits 데이.. 2021. 10. 14.
반응형

티스토리툴바