용답노트

DOM이란 HTML 문서를 브라우저가 이해할 수 있도록 만든 Tree 자료구조다.

HTML문서의 계층적 구조와 정보를 표현한다. 뿐만 아니라 DOM을 제어할 수 있는 API, 즉 프로퍼티와 메소드를 제공한다.

참조

• 이웅모, 모던 자바스크립트 Deep Dive(위키북스, 2020)
• https://velog.io/@sj_dev_js/HTML-DOM%EC%9D%B4%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%BC%EA%B9%8C

2계층에서 하는일

• 같은 네트워크(동일한 LAN 대역) 상에 존재하는 서로 다른 장비 간에 통신하는 계층
• 어떤 장비가 다른 장비에게 보내고자 하는 데이터를 전달하는 계층(단, 해당 장비들은 같은 네트워크에 있어야함)
• 통신 시에 오류제어, 흐름제어를 수행한다.
• 참고로 다른 네트워크와 통신할 때는 2계층만으로는 통신할 수 없고  3계층의 도움이 반드시 필요하다.

MAC주소 ( = 2계층에서 사용하는 주소)

• 기기마다 고유한 값을 가짐.
• 참고로 앞에 6자리는 제조사 고유 ID

Ethernet ( = 2계층의 프로토콜)

• 이더넷 프로토콜의 주소는 MAC주소를 쓴다.
• 이더넷 프로토콜의 구성은 아래와 같다.
  • 보내는 사람 MAC주소
  • 받는 사람 MAC주소
  • 이더넷 타입: Data(=페이로드)에 상위프로토콜이 무엇인지 미리 알려주는 역할을 한다.
  • DATA(=페이로드)

네트워크의 모델

TCP/IP 모델

• 현재 인터넷에서 컴퓨터들이 데이터를 주고 받는데 쓰이는 프로토콜의 모음이다.
• 아래는 그냥 참고
  • 4계층 응용
  • 3계층 전송
  • 2계층 네트워크
  • 1계층 네트워크 인터페이스

OSI 7계층 모델

• 표준으로 지정된 모델임. 데이터를 주고 받을 때 데이터의 흐름을 각 구간별로 나눠놓은 형태
• 7계층은 응용 / 표현 / 세션 / 전송 /네트워크 / 데이터링크 / 물리 로 이루어져있음.
• 계층별 프로토콜은 아래와 같음(그냥 참고)

네트워크 모델의 공통점과 차이점

• 위 그림을 보면 TCP/IP의 1계층을 OSI에서는 1,2계층이라고 역할과 기능을 더 세분화 해두었음
• 참고만 할 것.

패킷이란?

패킷의 정의

• 네트워크 상에서 전달되는 데이터를 통칭하는 말
• 패킷은 제어정보와 사용자 데이터(페이로드라고도 부름)로 이루어짐
• 패킷은 여러가지 프로토콜의 조합으로 이루어져 있음(보통 통신할 때 하나의 프로토콜만 사용하기보다는 여러가지 프로토콜을 조합해서 사용함)
• 여러프로토콜을 묶어둔 형태(물론 실제로는 0101110.. 이런 식이겠지만 우리가 보기에는 그렇게 보인다는 것)

패킷의 구조

• 페이로드를 보낼 때 헤더가 붙을 수도 있고 풋터가 붙을 수도 있다. 그러너ㅏ 대부분은 헤더에 페이로드가 붙은 구조다.

• 아래 예시 패킷 그림을 이해해 보자
  • HTTP 페이로드에 TCP 헤더가 붙었다.
  • TCP, HTTP 페이로드에 IPv4 헤더가 붙었다.
  • IPv4, TCP, HTTP 페이로드에 Ethernet 헤더가 붙었다.

캡슐화

• 어떤 노드에서 데이터를 다른 노드를 보낼 때 패킷을 만드는 과정

• 데이터를 보낼 때는 캡슐화(인캡슐레이션)을 통해서 패킷을 만들어 보낸다.
• 데이터를 받을 때는 디캡슐레이션을 통해서 패킷을 까본다.
• 위의 그림으로 데이터 보내기 위한 캡슐화 과정을 이해해 보자.
  • 네이버 웹툰 쿠베라 721화를 보고 싶은 상황.
  • 데이터: '네이버웹툰 쿠베라 721화를 보여줘' 라는 요청이 담긴 데이터
  • TCP: 네이버 웹서버와 통신해야 하므로 TCP를 인캡슐레이션 (통신순서 3번째)
  • IPv4: 네이버 웹서버라는 멀리 있는 서버와 통신해야하므로 IPv4를 인캡슐레이션(통신순서 2번째)
  • Ethernet: 우선은 가까운 곳과 통신해야하므로 Ethernet을 인캡슐레이션(통신순서 1번째)
• 즉, 인캡슐레이션은 상위계층에서 하위계층으로 내려가면서 프로토콜을 붙인다.
  • 순서가 뒤바뀔 수는 없다. (2-3-4 순서로 되어있음. 역순은 불가)
  • 순서의 생략도 없다.(1-2-4 같은 것 불가)
  • 같은 계층이 연속으로 붙는 경우는 가능(2-3-3-4 이런건 가능)

• 반대로 캡슐화된 패킷을 받았을 때 디캡슐레이션 과정을 거쳐 속에 담긴 데이터를 확인하는 흐름은 아래와 같다.
  •  하위프로토콜 부터 하나씩 확인을 한다.
  • 이더넷을 까보고, 그 뒤에 IPv4를 까보고, 그 다음에 TCP를 까보면 데이터가 나온다.  

네트워크란?

• device가 서로 데이터를 공유할 수 있게하는 통신 망
• '통신' 그 자체를 의미하는 것으로 가장 포괄적인 용어다
• 흔히 사용하는 인터넷도 네트워크의 종류 중 하나다. 인터넷 뿐만 아니라 블루투스, 인트라넷, 기기 간 랜선, 라디오나 무전기의 주파수 직접 연결 등도 모두 네트워크다.  

네트워크의 크기에 따른 분류

• 네트워크를 크기에 따라 분류하면 LAN, WAN, MAN PAN 등으로 분류한다.
• LAN(Local Area Network): 가까운 지역을 하나로 묶은 통신 망
• WAN(Wide Area Network): 가까운 지역끼리 묶인 LAN과 LAN을 하나로 묶은것.
  

  

• MAN(Metropolitan Area Network): 
• PAN(Personal Area Network): 예시로는 bluetooth, 기기 간 랜선 연결 등이 있다.

네트워크 연결 형태에 따른 분류 

• Star형: 중앙 장비에 모든 노드가 연결된 형태
• Mesh형: 여러 노드들이 서로 그물처럼 연결된 형태
• Tree형: 마치 나무의 가지처럼 계층 구조로 연결된 형태
• 기타: 링형, 버스형, 혼합형 등등

네트워크의 통신 방식

• 유니캐스트: 가장 보편적인 사용. 1:1 로 통신
• 멀티캐스트: 1:N 방식으로 통신
• 브로드캐스트: 같은 네트워크에 있는 모든 대상과 통신

네트워크 프로토콜

프로토콜의 정의

• 어떤 네트워크에서 노드와 노드가 통신할 때, 서로 데이터를 주고 받는 양식이 바로 프로토콜이다.
• 예를 들어 우체국에서 택배를 주고 받을 때는 보내는 사람 연락처, 받는사람 주소 등이 포함된 송장 양식을 따라야 하는 것처럼, 네트워크에서 통신을 하기 위해서는 정해진 양식을 따라야한다.

프로토콜의 종류

• 어떤 통신을 하고 싶은지에 따라서 사용하는 양식이 모두 다르다. 각 상황에 따라 아래와 같은 프로토콜(양식)들이 존재한다.
• 가까운곳과 연락할 때: 이더넷이라는 프로토콜 사용 / MAC주소 사용
• 멀리있는곳과 연락할 때: ICMP, IPv4, IPv6, ARP 등의 프로토콜 사용 / IP주소 사용
• 특정 프로그램으로 연락할 때: TCP, UDP 프로토콜 사용 / 포트주소(포트번호라고 주로 부름) 사용.
  예를들어 영수네 집에 메세지를 전달하는 것 까지는 IP주소로 이동했지만, 해당 메세지를 카톡으로 보낼지 페이스북으로 보낼지는 포트주소가 결정된다.
• 실제 통신할 때는 어느 하나의 양식을 쓰는 것이 아니라 여러가지의 양식을 합해서 통신하는 경우도 많음.

참고

• 우리 집에서 구글 DNS 서버까지 통신을 어떻게 하는지 추적해보자

• 위 그림에서 첫째줄에 tracert는 ip를 추적하는 프로그램이고, 8.8.8.8은 구글의 DNS서버 IP주소다.
• 1번에 있는 192.168.0.1 은 우리집의 iptime 주소
• 2번은 통신은 가능하지만 ip 추적을 차단해 두어서 ip 주소는 보이지 않는다.
• 3번~9번은 우리집에서 구글DNS서버까지 가는길에 있는 통신 허브들이다.
• 10번 구글 DNS서버 도착.

문제

• https://www.acmicpc.net/problem/6987

오답노트

• 첫 풀이
  • 제시된 월드컵 대진에서 팀별로 1씩 빼보는 방식으로 모든 경우를 탐색하여 그러한 대진표가 가능한지를 판단하려고 했음.
  • 해당 풀이대로 하면 팀별로(6) * 승무패에 대해서(3) * 다른 팀과 대진(6) 했을 경우에 수 에 대해서 뻴 수 있는게 있는지 모두 확인해보면서 최종적으로 15전 이 되었을 때 모두 0이 되는지 확인하기 때문에 (6*3*6)^15 라는 매우 큰 시간 복잡도를 가진다. 
  • 다만, (6*3*6)^15를 모두 확인하는 것은 아니고 1) 15전이 되지 않았더라도 뺄수 있는게 없으면 멈추고, 2)정답을 찾으면 바로 멈춘다 는 것을 고려해서 진행하였음.
  • 이렇게 할 경우, 입력으로 가능한 대진이 들어왔을 경우에는 금방 YES라고 출력하지만, 입력으로 불가한 대진이 들어올 경우에는 NO를 출력할 때까지 어마어마한 시간이 걸린다.
• 개선
  • 시간 복잡도를 대략으로라도 계산해보고, 15전이 되지 않아서 멈추는 경우의 수가 있다고 하더라도 너무 경우의 수가 많으니 다른 방법을 고안해 봤어야한다.
  •  1)15전이므로 모든 월드컵 대진에 대해서 3가지(승무패)에 대해서 탐색하되, 2)해당 대진이 주어진 입력과 요소가 하나라도 다르면 무조건 멈춤
  • 이렇게 하면 가능한 대진 and 요소와 일치하는것에 대해서만 탐색이 진행되기 때문에 훨씬 적은 시간 복잡도로 해결 가능(15개의 대전만 뽑아서 진행하기 때문에 이전 풀이에서 처럼 불가능한 대진에 대해서 탐색하는 시간이 자연스럽게 사라짐)

코드1(시간 초과)

import sys
sys.stdin=open("input.txt","rt") 
readl = sys.stdin.readline

def DFS(start, graph,matchCnt,ans,tc):
    if ans[tc]!=-1: return
    if matchCnt ==15:
        for i in range(6):
            if sum(graph[i]) > 0 :
                ans[tc]=0
                return
        ans[tc]= 1
        return
    for i in range(start, 6): #각 팀에 대해서 하나씩 빼보며 확인(앞팀부터 순차대로)
        for j in range(3): #승무패
            if graph[i][j] : #0이 아닌 경우에만
                graph[i][j]-=1
                for k in range(6): #본인 제외한 다른 5개팀에서 뺄수있는게 있는지 확인.
                    if i ==k: continue
                    #승무패 경우에 따라 나누기
                    if j == 0 :
                        if graph[k][2]: 
                            graph[k][2] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][2] +=1
                    elif j == 1:
                        if graph[k][1]: 
                            graph[k][1] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][1] +=1
                    elif j == 2:
                        if graph[k][0]: 
                            graph[k][0] -=1
                            DFS(start, graph, matchCnt+1, ans, tc)
                            graph[k][0] +=1
                graph[i][j]+=1
    return



ans = [-1,-1,-1,-1]
graph=[]
for tc in range(4):
    test = list(map(int, readl().split()))
    for cal in range(6):
        graph.append(test[3*cal:3*(cal+1)])
    for i in range(6):
        if sum(graph[i]) > 5 :
            break
    else:
        DFS(0, graph,0,ans, tc)
    graph=[]
    

print(*ans)

코드2 (정답)

import sys
import itertools
sys.stdin=open("input.txt","rt") 
readl = sys.stdin.readline

teamList =[0,1,2,3,4,5]
matchList = list(itertools.combinations(teamList,2))

#matchList = [ab ac ad ae af bc bd be bf ... ...]
#borad: graph와 일치하는지 확인을 위한 이중리스트
#matchCnt: 경기 진행 횟수, DFS가 끝나면 1이 추가됨. 15가 되는순간, 15번의 경기를 치룬 이후이므로 종료.
#tc: testcase number
def DFS(board,matchCnt,tc):
    if ans[tc] != -1:
        return
    if matchCnt == 15:
        ans[tc] = 1
        return
    team1 = matchList[matchCnt][0]
    team2 = matchList[matchCnt][1]

    #승,무,패 한 경우에 대해서
    for i in range(3): 
        board[team1][i] += 1
        board[team2][2-i] += 1 
        #graph와 일치하는지 확인
        if board[team1][i] <= graph[team1][i] and  board[team2][2-i] <= graph[team2][2-i]: 
            DFS(board,matchCnt+1,tc)
        board[team1][i] -= 1
        board[team2][2-i] -= 1

ans = [-1,-1,-1,-1]
for tc in range(4):
    graph=[]
    board=[[0 for i in range(3)] for j in range(6)]
    tmp = list(map(int, readl().split()))
    for cal in range(6):
        graph.append(tmp[3*cal:3*(cal+1)])
    for i in range(6):
        if sum(graph[i]) > 5 :
            break
    else:
        DFS(board, 0, tc)

for i in range(4):
    if ans[i] == -1:
        ans[i] = 0
print(*ans)

문제

• https://www.acmicpc.net/problem/11501

알게 된 내용

• 리스트의 최대(or 최소)값을 가지는 index를 획득하는 방법(풀이1으로 풀면서 필요했던 내용)

 index_max = max(range(len(values)), key=values.__getitem__)

풀이1(로직 개선 필요)

• 전체 range에서 최대값의 index를 확인 및 저장
  • 처음~해당 index까지 주식 모아서 판매.
• 저장된 최대index~끝 을 확인하여 최대값의 index 확인
  • 자기 자신일 경우 넘어감.
  • 아닐경우
    • 현재index~최대값의 index까지 주식 모아서 판매.

풀이2(정답)

• 맨 뒤에서 부터 확인한다.
• 맨 뒤의 값을 max에 저장
• 하나씩 앞으로 가면서 값을 확인
  • 현재 max보다 클 경우, max 값 갱신
  • 현재 max보다 작을 경우, 현재 max 값과의 차이 만큼 수익에 더함

미확인도착지 -> 다익스트라로하면 경로가 1개만 저장되고 다른 경로를 체크할수 없음.

알게 된 내용

• deque는 O(1) 로 맨앞에 요소를 추가할 수 있다. q.appendleft(x)
• deque는 정렬기능이 없다. 정렬 불가임.
• 빈 리스트는 list.sort() 동작하지 않는다. a = sorted(list) 이런식으로 써야함.

A = []
B = deque(A.sort()) #불가능
B = deque(sorted(A)) #가능

오답노트

• 문제가 길고 조건이 많아서, 자칫해서 문제를 잘못이해하면 몇시간을 통째로 날릴 수 있음. 코드 작성 전에 아래와 같이 조건을 잘 정리해 두었던 것이 도움이 되었음

#봄: 나이만큼 양분 먹고 / 나이 1 증가 / 여러 나무가 있으면 어린나무부터 양분먹기 / 양분없으면 사망 
#여름: 죽은나무 나이 나누기2 만큼 양분추가(소수점 버림)
#가을: 5의 배수 나이인 경우 나무 번식 / 인접한 8개 칸에 나이 1인 나무 생성
#겨울: 주어진 양분 배급

• 8방향 이동을 r, c 가 0일 때와 n-1 일때 조건을 세워서 풀었음. -> 아래와 같이 작성하면 가독성도 좋고 실수할 가능성도 낮음.

#이동
dx=[-1, 0, 1,-1, 1,-1, 0, 1]
dy=[-1,-1,-1, 0, 0, 1, 1, 1]

for i in range(8):
    nx=r+dx[i]
    ny=c+dy[i]
    if 0<=nx<n and 0<=ny<n:
        tree[nx][ny].appendleft(1)

코드

import sys
from collections import deque
sys.stdin = open("input.txt", "r") 

n, m, k = map(int,sys.stdin.readline().split())
A=[False for _ in range(n)]
for _ in range(n):
    A[_]=list(map(int,sys.stdin.readline().split()))

#현재 양분 값 저장하는 배열
B=[[5 for i in range(n)] for j in range(n)]

#트리 배열 생성
#트리 배열 각 노드의 값 == [1나무의 나이,2나무의 나이,..., x나무의 나이]
tree=[[[] for c in range(n)] for r in range(n)]
for _ in range(m):
    x,y,z = map(int,sys.stdin.readline().split())
    tree[x-1][y-1].append(z)

#처음 한번만 정렬
for i in range(n):
    for j in range(n):
        tree[i][j] = deque(sorted(tree[i][j]))
#이동
dx=[-1, 0, 1,-1, 1,-1, 0, 1]
dy=[-1,-1,-1, 0, 0, 1, 1, 1]

for y in range(k):
    sons=[] #번식하는 나무 담아둘 곳.
    for r in range(n):
        for c in range(n):
            cnt_tree = len(tree[r][c]) #현재 땅의 나무 개수 체크
            if cnt_tree ==0:
                B[r][c]+=A[r][c]
                continue
            #봄
            tmp=deque()
            die=0
            for age in tree[r][c]:
                if age > B[r][c]:# 잔여 양분 체크
                    die+= age//2 #죽은나무 나이 나누기2만큼 양분추가(소수점 버림)
                    continue
                B[r][c]-=age
                tmp.append(age+1)
            tree[r][c]=tmp

            #여름
            B[r][c] += die 
            
            #가을
            for t in tree[r][c]:
                if t%5 == 0: sons.append((r,c))
            #겨울
            B[r][c]+=A[r][c]
    #가을 적용
    for son in sons:
        (r,c) = son
        for i in range(8):
            nx=r+dx[i]
            ny=c+dy[i]
            if 0<=nx<n and 0<=ny<n:
                tree[nx][ny].appendleft(1)
#나무 개수 카운트
ans =0
for i in range(n):
    for j in range(n):
        ans += len(tree[i][j])
print(ans)