Study

1.4 패킷 교환 네트워크에서의 지연, 손실과 처리율 네트워크는 반드시 두 end system 간에 처리율(전달될 수 있는 초당 뎅디터의 양)을 제한하여 end system 간에 지연을 야기하며 실제로 패킷을 잃어버리기도 한다. 1.4.1 패킷 교환 네트워크에서의 지연 개요 패킷은 한 호스트에서 일련의 라우터를 통과하며 다른 호스트까지 도달함. 경로를 따라 한 노드(호스트 혹은 라우터)에서 다음 노드로 전달될 때 다양한 지연을 겪음. nodal processiong delay(노드 처리 지연) queuing delay(큐잉 지연) transmission delay(전송 지연) propagation delay(전파 지연) 이 모두를 합쳐 total nodal delay 지연 유형 라우터 A에서 B로 보내질 때 패킷이 앞선 노드에서 도착하면 라우터 A는 패킷 헤더를 조사해서 적당한 출력 링크를 결정하고(processing delay) 만약 선택된 링크가 이용되고 있더나 큐에서 대기하는 패킷이 있다면 큐로 들어간다(queuing delay). 링크를 이용할 수 있으면 패킷을 보낸다. 패킷의 길이가 L비트, 링크의 전송률이 R bps면 transmission delay는 L/R이다(transmission delay). 비트가 링크에 전해지면 목적지인 라우터 B까지 전달되야 한다. 이 전파 속도는 링크의 물리 매체에 따라 다르다(propagation delay). 전송 지연과 전파 지연 비교 전송지연 전송률과 패킷 길이 라우터가 패킷을 내보는데 필요한 시간 한 개의 패킷 내에서 첫번째 비트부터 마지막 비트까지 라우터를 빠져나오는데 걸리는 시간. 이전에 말했듯, 첫번째 비트는 마지막 비트가 도착할때까지 저장되어있어야 함. 마지막비트가 라우터에 도착하고나서야 첫번째 비트는 다음 목적지로 전송된다. 전파지연 비트가 한 라우터에서 다음 라우터로 전파되는데 걸리는 시간 링크의 물리적 길이 라우터를 빠져나와 다음 라우터까지 도달하는데 걸리는 시간. 패킷이 라우터에 저장되는 시간으로부터 다음 라우터에 저장될때 까지의 시간은 전송지연과 전파지연의 합. 당연히 마지막 비트가 전송되기도 전에 앞선 비트가 다음 라우터에 도착할 수도있다. 1.4.2 큐잉 지연과 패킷 손실 다른 지연들과 달리 큐잉 지연은 패킷마다 다를 수 있다. 여러 패킷이 동시에 비어있는 큐에 도착한다면, 처음 큐에 들어간 패킷과 마지막에 들어간 패킷의 큐잉 지연은 크게 차이난다. 따라서 큐잉 지연은 통계 측정을 일반적으로 사용한다. 큐잉 지연은 트래픽이 큐에 도착하는 비율, 링크의 전송률 ,도착하는 트래픽의 특성에 따라 달라진다. 예시 패킷이 큐에 도착하는 평균율 : a 패킷/초 전송률(비트가 큐에서 밀려나는 비율) : R 비트/초 모든 패킷 : L 비트 따라서 평균율의 단위를 비트로 바꾸면 La 비트/초 이다. 트래픽 강도(traffic intensity) : La/R (트래픽 강도) > 1 인 경우 비트가 큐에 도착하는 평균율이ㅐ 비트가 큐에서 전송되는 비율을 초과한다. La/R > 1이면, La > R이므로 큐에 도착하는 비트의 수가 다음 목적지로 전송되는 비트보다 많다. 큐에서 처리되는 비트보다 쌓이는 비트가 많아지므로, 점차 큐잉 지연은 커질것이다. 따라서 트래픽 공학에선, 트래픽 강도가 1보다 크지 않게 시스템을 설계하라는 규칙이 있다. (트래픽 강도) ≤ 1인 경우 패킷이 주기적으로 도착한다면, 쌓이는 것보다 처리되는 것이 빠르기 떄문에 큐잉 지연이 없을 것이다. 하지만 패킷이 몰려서(버스트) 도착한다면 큐잉 지연은 존재할 것이다. 이게 반복되면 몰려서 도착하는 패킷의 횟수만큼 점차 큐잉 지연이 늘어날 것이고, 이에 따라 평균 큐잉 지연을 계산할 수 있다. 실제로, 큐에 도착하는 프로세스는 랜덤하다.\ 또한 이 예시에선 큐가 무한한 패킷을 담을 수 있다고 가정했다. 하지만 트래픽 강도가 1에 가까울 수록, 큐잉 지연이 기하급수적으로 늘어나는 건 알아둬야 함. 패킷 손실 실제로 큐는 무한한 패킷을 담을 수 없다. 따라서 큐잉지연이 무한하게 증가하지 않는다. 패킷이 도착했을 때 큐가 꽉 차있다면, 패킷은 버려지고(drop), 잃어버리게(lost) 된다. 트래픽 강도가 높을 수록, 손실 패킷의 비율은 증가한다. end system에 입장에선, 패킷이 네트워크 코어로 전송되었으나 목적지에 나타나지 않는 것 처럼 보인다. 1.4.3 종단 간 지연 위 과정들은, 단일 라우터에서를 초점으로 두었다. 출발 호스트와 목적 호스트 사이에 N-1개의 라우터(즉, N개의 링크)가 있다고 가정. d(proc) = 각 라우터와 출발지 호스트의 처리 지연 R 비트/초 = 각 호스트와 출발지 호스트에서의 전송률 d(prop) = 각 링크에서의 전파 지연 L = 패킷 크기 d(trans) = L/R (전송지연) d(end-end) = 종단 간 지연 = N * (d(proc) + d(trans) + d(prop)) Traceroute 컴퓨터 네트워크에서의 지연을 느낄 수 있는 진단 프로그램’ 종단 시스템, 애플리케이션 그리고 그 밖의 지연 이외에도 다른 중요한 지연들 도 있다. 종단 시스템에서 매체를 공유하기 위해 프로토콜의 일부로 전송을 의도적으로 지연 시킬 수도 있다. media packetization delay(미디어 패킷화 지연)은 VoIP(Voice-over-IP)에서 송신 측은 먼저 패킷을 인터넷으로 보내기 전에 패킷을 인코딩된 디지털 음성으로 채워야 한다. 1.4.4 컴퓨터 네트워크에서의 처리율 지연과 패킷 손실 외에 컴퓨터 네트워크에서 성능과 연관된 요소는 throughput(처리율) 이다. instantaneous throughput(순간적인 처리율), average throughput(평균 처리율) 예시 서버 → 라우터 → 클라이언트로 연결되어있다고 가정해보자. 서버와 라우터간의 링크 속도는 R(s)고, 라우터와 클라이언트의 링크 속도는 R(c)이다. 서버는 라우터로 R(s)의 속도로 비트를 보내고, 라우터는 클라이언트로 R(c)의 속도로 전송한다. R(s) < R(c) 일때, 결국 클라이언트는 서버로부터 R(s)의 처리율로 비트를 받는다. R(s) > R(c) 일때, 서버가 라우터로 아무리 빨리 보내더라도 결국 클라이언트는 R(c)의 속도로 비트가 처리되는 것처럼 느낀다. 따라서 이 네트워크의 처리율은 min{R(c), R(s)} 가 된다. **bottleneck link(병목 링크)**의 전송률이 처리율이 된 상황이다. 이처럼 일직선으로 되어있는 네트워크에서 서버가 클라이언트로 파일을 전송하는 경우의 처리율은 링크 속도 중 최솟값이고, 이는 병목 링크의 전송률이다. 10개의 서버와 10개의 클라이언트가 있다고 가정해보자. 서버와 클라이언트간의 연결은 모두 단 하나의 코어 링크를 지난다고 생각해보자. 어떤 서버가 어떤 클라이언트에게 파일을 전송하든, 코어 링크를 지나야 한다. R(s) : 서버와 코어링크 사이의 링크 속도 R(c): 클라잉너트와 코어 링크 사이의 링크 속도 R : 코어 링크의 링크 속도 만약 R이 R(s)와 R(c)보다 월등히 크다면, 코어 링크가 끼치는 영향은 무의미하다. 따라서 병목은 R(s)와 R(c) 중 최솟값이 된다. 하지만 R이 R(s), R(c)와 비슷하다면? R(s) = 1 Mbps, R(c) = 2 Mbps고 R = 5 Mbps 라면 어떨까? 공통된 코어 링크는 10개의 서버-클라이언트 쌍에게 전송률을 나눈다. 하나의 통신은 500 Kbps를 가지게 된다. 그렇다면 병목은 R(s)나 R(c)가 아니라 공통된 코어링크가 된다.

2024년 1월 15일 알고리즘 문제풀이 문제 피보나치 수 난이도 Lv. 2 코드 1 2 3 4 5 6 7 8 def solution(n): dp = [0 for _ in range(n+1)] dp[1] = 1 if n<2: return dp[n] for i in range(2,n+1): dp[i] = (dp[i-1]+dp[i-2])%1234567 return dp[n]

1.3 네트워크 코어 1.3.1 패킷 교환 end system : message 교환 packet: message의 분할 packet은 통신 링크와 packet switch를 거침 저장-후-전달 store-and-forward transmission : switch가 한 패킷 내의 모든 비트를 받아야만 전송 시작 초당 R비트의 속도로 총 L 비트을 전송하는건 L/R초 소모. 이 방식으로, L비트 짜리 패킷 1개가 엔드시스템 → 라우터 → 엔드시스템 으로 갈떄 걸리는 시간은 2L/R 받고 저장하는데 L/R + 다시 보내는데 L/R 전체 이 방식이 아니라 받는 비트별로 보내면 L/R 일 것. L 비트짜리 패킷이 3개라면? L/R 초 후 : 출발지가 송신, 라우터가 수신 2L/R 초 후 출발지가 2번째 패킷 송신, 라우터가 첫번째 패킷 송신과 두번째 패킷 수신, 목적지가 첫번째 패킷 수신 결국 4L/R 걸린다. 일반화해서, 출발지부터 목적지까지 N개의 링크로 구성(N-1개의 라우터가 존재한다는 의미)되어있고 전송률이 R이라면 종간 간 지연은 NL/R 큐잉 지연과 패킷 손실 각 패킷 스위치는 여러개의 링크를 가질 수 있음 각 링크에 대해 output buffer(output queue)를 가짐. 송신받은 패킷을 보낼려는 링크가 다른 패킷을 전송하고 있다면 output buffer에서 대기 : queuing delay output buffer 조차도 꽉차있다 : packet loss 흔한 일 : 출발지 → 라우터 는 100Mbps지만 라우터 → 목적지가 15Mbps라면 기다려야함 포워딩 테이블과 라우팅 프로토콜 보내야 할 링크를 아는 방법: IP 주소(계층적 구조 like 우편주소) forwarding table 패킷이 라우터에 도착하면 올바른 출력링크를 찾기 위해 주소의 일부를 조사 주소를 이용해 forwarding table 검색 그 패킷을 출력링크로 보냄 인터넷은 자동으로 forwarding table을 설정하는데 이용하는 routing protocol을 갖고 있음. 1.3.2 회선교환 데이터를 이동시키는 방식 : circuit switching, packet switching(지금까지 본것) circuit swtiching(회선 교환) 통신 session 동안 resource들을 reserve. 전화망 : circuit(회선)이 송수신자간의 연결 상태를 유지해서 guaranteed된 전송률 보장 각 링크가 여러개의 회선을 가져 이 중 하나를 reserve 할 수 있음 (전송용량의 1/n) 회선 교환 네트워크에서의 다중화 FDM(frequency-division multiplexing, 주파수 분할 다중화), TDM(time-division multiplexing, 시분할 다중화) : 회선을 동시에 공유할 것인가? 시간마다 번갈아가면서 전체를 쓸것인가? FDM 링크를 통해 설정된 연결은 링크의 주파수 스펙트럼을 공유. 대역폭(bandwidth): 링크가 연결되는 동안 각 연결에 대해 고정제공하는 주파수 대역의 폭 FM 라디오는 88Mhz~108MHz 사이를 공유(방송국마다 할당) TDM 시간을 일정 주기의 프레임으로 구분, 각 프레임은 고정된 수의 시간 슬롯으로 나눔 단점 : silent period(비활용기간) ⇒ 통화할때 이야기를 주고받지 않아도 다른 네트워크자원으로 쓸 수 없이 연결되어있음 : 낭비? A 에서 B로 n비트를 보낼떄, 모든 링크가 k개의 슬롯을 가지고 전송률이 v인 TDM 이라면? 각 회선의 전송률은 v/k (v만큼을 k개가 나눠쓰니까) 전송시간은 n/(v/k)초 가된다. 패킷 교환 대 회선 교환 패킷교환의 장점 패킷 교환이 회선 교환 전송 용량의 공유에서 더 효율적이다. 패킷 교환이 더 간단하고 효율적이며 회선 교환보다 더 구현 비용이 적다. 패킷교환의 단점 가변적이고 예측할 수 없는 종단 간의 지연(주로 불규칙적이고 예측할 수 없는 큐잉 지연에서 발생) 때문에 패킷 교환이 실시간 서비스(ex. 전화 통화)에는 적당하지 않음. 패킷교환이 효율적인 이유 패킷교환은 요구할떄만 링크의 사용을 할당하기 때문이다. 1.3.3 네트워크의 네트워크 종단 시스템은 접속 ISP를 통해 인터넷에 연결된다. 하지만 이는 인터넷 망에서 극히 일부에 불과하다. 접속 ISP들이 연결되어야 하기 떄문에, 네트워크의 네트워크 개념이 탄생했다. ISP들이 전 세계에 있는 모든 ISP들과 연결하는 것은 비용적으로 비효율적이다.(네트워크 구조 1) 가장 상위에 단 1개에 글로벌 ISP도 존재하기 힘들다. 이 지위를 얻기 위해 경쟁할 것이고, 두 경쟁은 서로 연결하지 않을 것이기 때문에, 다른 글로벌 ISP를 이용하는 end system간 통신은 불가능해진다.(네트워크 구조 2) 12개 정도의 1계층 ISP - 국가 ISP - 지방 ISP 순으로 연결(네트워크 구조 3) 여기에 Pop, 멀티홈, 피어링, IXP가 추가되어야 한다(네트워크 구조 4) 콘텐츠 제공자 네트워크도 추가된다.(네트워크 구조 5)

2024년 1월 12일 알고리즘 문제풀이 문제 햄버거 만들기 난이도 Lv. 1 코드 배열을 순회하면서 순서대로 필요한 재료가 나오면 만들 수 있는 갯수를 하나 추가해주고, 해당 재료들을 제거해주었다. 이 방법은 틀렸는데, 재료가 연속해서 나와야 하기 떄문이다. 연속이라고 써놓지 좀… 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(ingredient): answer = 0 arr = [1,2,3,1] while True: idx = 0 for x in range(len(ingredient)): if idx ==4: answer += 1 break if ingredient[x] == arr[idx]: idx += 1 ingredient[x] = 10 else: if idx == 4: answer += 1 else: return answer 그래서 하나씩 배열로 옮기면서, 최근 옮긴 4개로 햄버거를 만들 수 있다면 만들고 제거하도록 로직을 바꾸었다. ...

2024년 1월 11일 알고리즘 문제풀이 문제 자릿수 더하기 난이도 Lv. 1 코드 1 2 3 4 5 6 def solution(n): answer = 0 arr = list(str(n)) for x in arr: answer += int(x) return answer

2024년 1월 2일 알고리즘 문제풀이 문제 N-Queen 난이도 Lv.2 코드 그 어렵다고 소문난 N-Queen 문제. 정글 때 공부했던 문제였는데 그새 까먹었나보다. 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 def solution(n): answer = 0 def check_width_row(p,q,arr): for i in range(n): if arr[i][q] == '0': arr[i][q] = False if arr[p][i] == '0': arr[p][i] = False def check_right_down(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n: if arr[p+i][q+i] == '0': arr[p+i][q+i] = False i += 1 def check_left_up(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q+i >= 0 and q+i < n: if arr[p+i][q+i] == '0': arr[p+i][q+i] = False i -= 1 def check_right_up(p,q,arr): i = 0 while p-i >= 0 and p-i < n and q+i >= 0 and q+i < n: if arr[p-i][q+i] == '0': arr[p-i][q+i] = False i += 1 def check_left_down(p,q,arr): i = 0 while p+i >= 0 and p+i < n and q-i >= 0 and q-i < n: if arr[p+i][q-i] == '0': arr[p+i][q-i] = False i += 1 def check(p,q,arr): check_width_row(p,q,arr) check_right_down(p,q,arr) check_right_up(p,q,arr) check_left_up(p,q,arr) check_left_down(p,q,arr) arr[p][q] = True def search(x,arr): for i in range(n): if arr[x][i] == '0': check(x,i,arr) flag = True break else: flag = False return flag for i in range(n): w = [['0' for _ in range(n)] for _ in range(n)] w[0][i] = True check(0,i,w) k = 1 while k < n: tmp = search(k,w) if tmp: k += 1 else: break if k == n: print(w) answer += 1 return answer 보드판을 string ‘0’을 배치시켜 만들었다. 원래 숫자로 넣었는데 False일 떄와 0일때가 같이 취급되어서 따로 만들었다. 아무 선택되지 않은 좌표는 ‘0’, 공격당할 수 있기 때문에 놓을 수 없는 곳은 False, 퀸이 위치한 곳은 True로 설정하였다. 우선 임의의 좌표 (p,q)에 퀸을 놓았을 때 퀸이 공격할 수 있는 곳을 False 처리하는 코드를 작성했다. 임의의 좌표의 좌 우 대각선을 바꿔주는 함수를 각각 만들고 하나의 함수로 합쳤다(check). search는 특정 행에서 퀸을 놓을 수 있는 열을 찾아 존재하면 boolean값을 반환해주는 함수이다. ...

2024년 1월 1일 알고리즘 문제풀이 문제 최솟값 만들기 난이도 Lv.2 코드 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 from heapq import heappop, heappush def solution(A,B): n = len(A) arr_A = [False for _ in range(n)] arr_B = [False for _ in range(n)] arr = [] def dfs(tmp,arr_A,arr_B): if arr and tmp > arr[0]: return if not arr_A.count(False) and not arr_B.count(False): if not arr or tmp < arr[0]: heappush(arr,tmp) for i in range(n): if arr_A[i]: continue for j in range(n): if arr_B[j]: continue arr_A[i] = True arr_B[j] = True dfs(tmp+(A[i]*B[j]),arr_A,arr_B) arr_A[i] = False arr_B[j] = False dfs(0,arr_A,arr_B) return arr[0] 처음엔 DFS로 시도했다. 여러 case가 규칙성 없이 나타날 수 있다고 생각했기 때문이다. 하지만 시간초과가 발생했다. 불필요한 탐색을 줄이기 위해, 값을 최소힙에 저장하도록 했다. DFS 과정 상 재귀 중에 이미 최소힙에 존재하는 최솟값을 넘어선 경우 탐색을 중단하도록 했다. 하지만 시간초과가 계속 발생했다. ...

2023년 12월 29일 알고리즘 문제풀이 문제 신규 아이디 추천 난이도 Lv.1 코드 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 def solution(new_id): arr = ['1','2','3','4','5','6','7','8','9','0','-','_','.'] # 1단계 new_id = new_id.lower() # 2단계 tmp = [] for i in new_id: if i.islower() == True or i in arr: tmp.append(i) new_id = ''.join(tmp) # 3단계 if len(new_id) >1: tmp = [] for i in range(len(new_id)-1): if new_id[i] == '.' and new_id[i+1] == '.': continue tmp.append(new_id[i]) tmp.append(new_id[-1]) new_id = ''.join(tmp) # 4단계 if new_id: if new_id[0] == '.': if len(new_id) == 1: new_id = '' else: new_id = new_id[1:] # 4단계 if new_id: if new_id[-1] == '.': if len(new_id) == 1: new_id = '' else: new_id = new_id[:len(new_id)-1] # 5단계 if new_id == '': new_id = 'a' # 6단계 if len(new_id) >= 16: new_id = new_id[:15] # 6단계 if new_id[-1] == '.': new_id = new_id[:len(new_id)-1] # 7단계 if len(new_id) <= 2: while len(new_id) < 3: new_id = new_id + new_id[-1] return new_id 문제에 주어진 대로, 순차적으로 해결하면 큰 어려움은 없는 문제였다. 다만 중간중간, 문자열이 존재하지 않게 되는 상황이 발생할 수 있기 때문에 이를 따로 처리하는 로직이 필요하다. 시간 많이 잡아먹는 문제라 좋은 연습이 됐다.

2023년 12월 28일 알고리즘 문제풀이 문제 문자열 내 p와 y의 개수 난이도 Lv.1 코드 1 2 3 4 def solution(s): a = s.count('p') + s.count('P') b = s.count('y') + s.count('Y') return a == b 이 문제에선 p 와 y만 포함됐지만, 대문자나 소문자 자체를 어떻게 셀 지 궁금해져서 찾아보니 islower() 와 isupper() 를 사용하면 boolean 값으로 반환된다고 한다.

2023년 12월 26일 알고리즘 문제풀이 문제 줄 서는 방법 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 import math def solution(n, k): answer = [] arr = list(range(1,n+1)) while n>0: tmp = math.factorial(n-1) a = k//tmp k = k%tmp if k: answer.append(arr[a]) arr.pop(a) else: answer.append(arr[a-1]) arr.pop(a-1) n -= 1 return answer 순열에 정의를 알면 접근방식 자체는 그리 어렵지 않지만, 코드로 구현하는 게 꽤나 까다로웠다. 순열은 결국 앞에서부터 올 수 있는 경우의 수를 정해주고 곱하는 방식이다. 4명이 줄을 서는 방법은 4! = 4 x 3 x 2 x 1이다. 왜 이렇게 나오냐면, 맨 앞에 올 수 있는 후보는 4개 이고, 그 다음은 3개, 2개, 1개 이기 때문이다. ...