Coding 공부

import sys

input = sys.stdin.readline

N = int(input())


bit_cnt_list = [0]*1024
for _ in range(N):
    num = input().strip()
    temp = 0
    for bit_num in num:
        temp = temp | 2**(int(bit_num))
    bit_cnt_list[temp] += 1
result = 0
for k in range(1,1024):
    for t in range(k,1024):
        if k == t:
            if bit_cnt_list[k] >= 2:
                result = result + (bit_cnt_list[k]*(bit_cnt_list[k]-1))//2
        else:
            if bit_cnt_list[k] != 0 or bit_cnt_list[t] != 0:
                if k&t >0:
                    result = result + bit_cnt_list[k]*bit_cnt_list[t]

print(result)

T = int(input())
dp = [[0]*10 if i !=0 else [1]*10 for i in range(65)]
visited = [0]*64
visited[0] = 1
last_n = 0
for ind in range(T):
    n = int(input())
    if visited[n-1]:
        print(sum(dp[n-1]))
    else:
        for ind in range(last_n+1,n):
            for num in range(9,-1,-1):
                if num == 9:
                    dp[ind][num] = sum(dp[ind-1])
                else:
                    dp[ind][num] = dp[ind][num+1] - dp[ind-1][num+1]
        last_n = max(last_n,n-1)

        print(sum(dp[n-1]))

T = int(input())
dp = [[1]*10 if ind == 0 else [0]*10 for ind in range(64)]
result = [0]*64
result[0] = 10
for ind in range(1,64):
    for num in range(9,-1,-1):
        if num == 9:
            dp[ind][num] = result[ind-1]
        else:
            dp[ind][num] = dp[ind][num+1] - dp[ind-1][num+1]
    result[ind] = sum(dp[ind])

for _ in range(T):
    n = int(input())
    print(result[n-1])

def checkminNumber(index,open1,open2):
    if index > M-1:
        return 0 
    result = dp[index][open1][open2]
    if result != float('inf'):
        return result
    next_open = output_list[index]
    dp[index][open1][open2] = min(abs(open1 - next_open) + checkminNumber(index+1,next_open,open2), abs(open2 - next_open) + checkminNumber(index+1,open1,next_open))
    return dp[index][open1][open2]



N = int(input())

open1,open2 = list(map(int,input().split()))

M = int(input())
dp = [[[float('inf')]*(N+1) for _ in range(N+1)] for _ in range(M)]
output_list = []

for _ in range(M):
    output_list.append(int(input()))
print(checkminNumber(0,open1,open2))

import sys
import collections
input = sys.stdin.readline

def bfs1(x):
    que=collections.deque()
    que.append(x)
    temp=set()
    temp.add(x)
    while que:
        node=que.popleft()
        for i in graph1[node]:
            if i not in temp:
                temp.add(i)
                visit[x]+=1       
                que.append(i)
    return
def bfs2(x):
    que=collections.deque()
    que.append(x)
    temp=set()
    temp.add(x)
    while que:
        node=que.popleft()
        for i in graph2[node]:            
            if i not in temp:
                temp.add(i)
                visit[x]+=1       
                que.append(i)
    return
 

N,M = map(int,input().split())
arr=[list(map(int,input().split())) for i in range(M)]
graph1=[[] for i in range(N+1)]
graph2=[[] for i in range(N+1)]
for i in arr:
    graph1[i[0]].append(i[1])
    graph2[i[1]].append(i[0])
visit=[0]*(N+1)
for i in range(1,N+1):        
    bfs1(i)
    bfs2(i)

cnt=visit.count(N-1)
print(cnt)

Ch 1.2 네트워크 가장 자리

종단 시스템은 웹브라우저 프로그램 웹서버프로그램 전자 메일 클라이언트 프로그램 또는 전자메일 서버 프로그램 같은 애플리케이션을 수행하므로 호스트 라고도 불린다.

• 종단 시스템들은 데스크톱 컴퓨터, 서버, 모바일 컴퓨터 등을 포함한다.
• 호스트는 클라이언트와 서버로도 구분된다.

1.2.1 접속 네트워크

​ 접속네트워크는 종단시스템을 그 종단시스템으로부터 다른 먼 거리의 종단시스템까지의 경로상에 있는 첫번째 라우터에 연결되는 네트워크 경로

가정접속 : DSL, 케이블, FTTH, 다이얼-업 그리고 위성

• DSL(digital sub-scriber line) : 각 고객의 DSL 모뎀은 텔코의 지역 중앙국에 위치한 DSLAM(digital subscriber line access multiplexer) 과 교환하기 위해 기존 전화 회선을 이용한다.
  • DSL 모뎀은 디지털 데이터를 받아서 전화서를 통해, 지역 중앙국(CO)로 전송하기 위해 고주파신호로 변환한다.
  • DSL은 다른 주파수 대역으로 인코드 되어, 3개의 분리된 링크인 것처럼 보이게한다. 그래서 하나의 전화회선과 인터넷 연결이 동시에 DSL 링크를 고유할수 있게된다.
  • DSL은 고객쪽에 스플리터가 있어, 데이터와 전화신호를 분리하고, 데이터신호를 DSL 모뎀으로 전송한다.
• 케이블 인터넷 접속 : 케이블 TV회사의 기존 케이블 TV 기반구조를 이용한, 인터넷 서비스이다.
  • 광케이블은 헤드엔드를 이웃-레벨 정션에 연ㄴ결하며, 여기 광 노드에서 각 집에 도착할때까지는 전통적인 동축케이블을 사용한다.
  • 케이블 헤드엔드의 CMTS(cable modem termination sysyem)은 DSL의 DSLAM와 유사한 기능을 한다.
  • 케이블 인터넷 접속은 공유 방송매체이므로, 모든 패킷은 모든 링크의 다운스트림 채널을 통해 모든 가정에 전달되며, 업스트림 또한, 모든패킷이 업스트림 채널을 통해 헤드엔드로 간다.
  • 그러므로,각 사용자가 비디오파일을 동시에 수신하고 있다면, 실제 수신율은 다운스트림 전송율보다 상당히 낮아진다.
  • 그래서 분산 다중 접속 프로토콜로 전송을 조정하고, 충동을 피하기 위한 노력이 필요하다.
• FTTH(Fiber to the Home) : CO(지역 중앙국)으로 부터, 집까지 광 성유 경로를 제공한다.
  • CO(중앙국)에서 하나의 광섬유로 와서, 고객이 있는곳에서 분리가 되어, 제공이된다.
  • 위와 같은 기술을 스플리팅으로 하며, AON(active optical network)과 PON(passive optical network)이 대표적이다.

기업접속 : 이더넷과 와이파이

• 이더넷은 기관에서 이더넷 스위치를 통해, 연결하고 기관 라우터를 통해 기관 IPS로 제공된다.
• 와이파이는 유선으로 연결된 AP의 수십미터 반경에서 무선으로 클라이언트와 연결이 된다.

1.2.2 물리 매체

• 물리매체는 전자파나 광펄스를 전파하여 비트를 전송하는 매체를 의미한다.
  • 유도매체와 비유도매체가 있다.
    • 유도매체 : 광섬유케이블 꼬임쌍선, 동축케이블 (견고한 매체를 따라 파형을 유도)
    • 비유도 매체 : 무선 lan 혹은 디지털 위성채널(대기와 야외공간으로 파형을 전파)
• 꼬임 쌍선
  • 가장 싸고 가장 많이이용하는 전송매체
  • 전화망에서 자주 사용된다.
  • 2개의 절연동선이 각각 약 1mm의 굵기로 규칙적인 나선형태로 배열된다.
  • 꼬임 쌍선의 데이터 전송률은 10Mbps 에서 10Gbps에 이른다.
  • 데이터 전송률은 전송선의 두께와 송신기와 수신기 사이의 거리에 따라 다르며, 짧은 수백m의 거리에서는 광섬유에 비견될 정도로 10Gbps의 속도를 낼수 도 있다.
• 동축 케이블
  • 꼬임쌍선 처럼 동축케이블은 2개의 구리선으로 되어있으나, 두 구리선이 평해하지 않고 동심원 형태를 이루고 있다.
  • 일반적으로 꼬임 쌍선보다 더 높은 데이터 전송률을 얻을 수 있다.
  • TV시스템에 흔히 사용된다.
  • 동축케이블은 유도 공유매체로 사용할 수 있다. 여러 종단시스템은 케이블에 직접 연결할 수 있고, 모든 종단시스템은 다른 종단시스템이 전송하는 모든것을 수신한다.
• 광섬유
  • 비트를 나타내는 빛의 파동을 전하는 가늘고 유연한 매체이다.
  • 단일 광성유는 10~100기가의 전송률을 가지며, 100KM까지느 신호 감쇠현상이 적고, 전자기성 간섭에 영향을 받지 않으며, 도청하기 어렵다.
  • 인터넷의 백본과 해저케이블에 자주 쓰인다.
  • 그러나 송,수신기, 스위치의 광장비가 고가이므로, 랜이나 가정처럼 근거리 전송에는 이용하기 어렵다.
• 지상 라디오 채널
  • 라디오 채널은 전자기 스팩트럼으로 신호를 전달한다.
  • 물리선로를 설치할 필요가 없고, 벽을 관통할수 있으며, 이동 사용자에게 연결성을 제공하고 먼거리 까지 신호를 전달할수 있다.
  • 주변환경에 영향과 전달되는 거리에 많은 영향을 받아, PATH LOSS(경로 손실)과 shadow fading(경로상의 손실), 다중경로 페이딩, 간섭을 받을 수 있다.
• 위성 라디오 채널
  • 정지위성과 저궤도 위성을 통해 통신을 하는 시스템
    • 정지 위성은 보통 DSL접속 또는 케이블 기반 인터넷접속을 할수 없는 지역에서 이용된다.
    • 정지위성은 긴 신호 전파 지연을 일으키는 단점이 있다.
    • 저궤도위성은 지구 위 한곳에 고정되지 않고, 지상국뿐만 아니라, 자기들끼리도 통신이 가능하다. 많은 저궤도 통신시스템이 개발 중에 있다.

def gcd(A,B):
    if not A%B:
        return B
    return gcd(B,A%B)


N, M = map(int,input().split())
ab = M//N
list_a = []
last_N = int(ab**(1/2))
for number_a in range(last_N,0,-1):
    if not ab%number_a:
        number_b = ab//number_a
        if gcd(number_a,number_b) == 1:
            list_a.extend([number_a,number_b])
            break
print(*[ i*N for i in list_a])

N = int(input())
K = int(input())
arr = list(map(int,input().split()))
arr.sort()
diff = [0]*N
for i in range(N-1):
    diff[i] = arr[i+1] - arr[i]

diff.sort()
print(sum(diff[:len(diff)-(K-1)]))

N = int(input())

arr = [int(input()) for _ in range(N)]

dp = [[0 for _ in range(3)] for _ in range(N)] 
if N>2:
    dp[0][1] = arr[0]
    dp[1][1] = arr[1]
    dp[1][2] = dp[0][1] + arr[1]



    for ind in range(2,N):
        
        dp[ind][0] = max(dp[ind-1][0],dp[ind][0],dp[ind-2][2],dp[ind-2][1],dp[ind-1][1])
        dp[ind][1] = max(dp[ind][1],dp[ind-1][0]+arr[ind],dp[ind-2][1]+arr[ind],dp[ind-2][2]+arr[ind],dp[ind-2][0]+arr[ind])
        dp[ind][2] = max(dp[ind][2],dp[ind-1][1]+arr[ind])
    print(max(list(map(max,dp))))
else:
    print(sum(arr))

N = int(input())

arr = [0]+[int(input()) for _ in range(N)]

dp = [0]*(N+1)

dp[1] = arr[1]

for ind in range(2,N+1):
    if ind == 2:
        dp[ind] = dp[ind-1] + arr[ind]
    else:
        dp[ind] = max(dp[ind-3]+arr[ind-1]+arr[ind],dp[ind-2]+arr[ind],dp[ind-1])

print(dp[N])