'파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 비밀 지도

• 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.
  • 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
  • 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
  • "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
  • 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.
  

- 입력: 
  - n = 5
  - arr1    [9, 20, 28, 18, 11]
  - arr2    [30, 1, 21, 17, 28]
- 출력    ["#####","# # #", "### #", "# ##", "#####"]

2. 풀이 - 이진수 OR 연산

1) OR 연산

비트 연산자 OR를 이용하여 이진수를 계산하는 문제다.

두 개의 지도를 합칠 때, 둘 중 하나라도 벽(’#)이면 벽(’#)이 나오고,

둘 중 모두가 공백(” “) 일 경우에 공백(” “)이 나온다.

‘이진수 1’을 벽(’#’)으로, ‘이진수 0’을 공백(” “)으로 치환하면 된다.

하나의 지도가 10100(2), 다른 지도가 00001(2)라고 할 때,

두 이진수를 OR(|) 연산하면 10101(2)이 된다. 각 자릿수를 계산해보면 쉽게 이해가 될 것이다.

for i in range(len(arr1):
    bin_or = bin(arr1[i] | arr2[i])[2:].zfill(len(arr1))

bin() 매서드를 사용해서 십진수를 이진수로 바꾸면 문자열 타입이 출력된다.

또한 앞부분에 이진수임을 표시한 ‘0b’라는 문자가 같이 붙어서 출력된다.

예를 들어 ‘ bin(arr1[i] | arr2[i]) ‘를 입력하면,

'0b1111'이 출력되는 식이다.

앞에 ‘0b’를 제거하기 위해 슬라이싱( [2:])을 사용했다.

그리고 작은 숫자의 경우 OR연산 결과 5자리가 모두 채워지지 않을 수 있다.(ex. 1001(2))

따라서 지정된 자리수를 채우지 못할 경우 앞에 0을 넣어주는 zfill() 함수를 사용하여 자릿수를 맞춰준다.

2) 문자열 변환 및 정답 출력

answer = []

for i in range(len(arr1):
    bin_or = bin(arr[i] | arr[i])[2:].zfill(len(arr1))

    answer.append(bin_or.replace('0', ' ').replace('1', '#')

replace(’바꾸기 전’, ‘바꾼 후’) 함수를 활용하여 ‘0’을 공백(’ ‘)으로 ‘1’을 ‘#’으로 바꿔준다.

그런 다음 정답 리스트에 추가를 해주면 최종 답이 완성된다.

전체 코드는 아래와 같다.

3) 전체 코드

def solution(n, arr1, arr2):
    answer = []

    for i in range(len(arr1)):
        or_bin = bin(arr1[i] | arr2[i])[2:].zfill(len(arr1))
        answer.append(or_bin.replace('0', ' ').replace('1', '#'))

    return answer

| '파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 코스 스케줄(리트코드 207)

- 문제: 0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1], 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라
    - Input: numCourses = 2, prerequisites = [[1,0]]
    - Output: true

선행 수강해야하는 과목(prerequisites)을 고려했을 때, 특정 개수(numCourse)의 수업을 모두 들을 수 있는지 여부를 판단하는 문제다.

위 예시에서 ‘numCourses = 2’이므로 2개의 수업을 들어야 된다.

‘prerequisites = [[1,0]]’ 조건에서 1번 수업을 듣기 위해서는 0번 수업을 먼저 수강해야 한다.

즉 위의 경우는 수업을 들을 수 있으므로 ‘참’이다.

하지만 만약 조건이 numCourses = 2, prerequisites = [[1,0], [0,1]]이라고 한다면,

1번 수업을 듣기 위해 0번 수업을 먼저 들어야 하고, 동시에 0번 수업을 듣기 위해 1번 수업을 사전에 들어야 하므로, ‘거짓'이 된다.

2. 풀이 - DFS로 순환구조 판별

이 문제는 순환 구조 여부를 판단해야 한다.

a강의를 듣기 위해 b강의를 먼저 수강해야 하고,

b강의를 듣기 위해 a강의를 먼저 수강해야 한다면,

a와 b가 서로 연결되는 구조가 만들어지며,

순환구조로 구성될 경우 ‘False’를 리턴한다.

1) 그래프 생성

graph = collections.defaultdict(list)

for a, b in prerequisites:
    graph[a].append(b)

우선 입력값으로 주어진 수강 순서(변수 prerequisites)를 그래프 형태로 바꿔준다.

defaultdict 자료형을 이용하며, 도식화하면 아래와 같다.

2) 순환구조 판단

이미 방문했던 경로는 ‘traced’ 변수에 저장하고,

재귀 호출을 진행하면서 해당 경로가 ‘traced 변수'에 존재할 경우(중복일 경우) False를 리턴하는 구조다.(#3)

우선 그래프에 키값(a)을 대상으로 for 반복문을 실행하고, dfs 함수를 호출한다.(#1)

키에 속한 경로들을 나타내는 value(b) 대상으로 for 반복문을 실행하고, 재귀 함수를 호출한다.(#2)

경로 탐색을 마친 후 해당 경로는 ‘traced’에서 삭제한다.(# 4)

만약 삭제를 하지 않으면 for 문이 실행되는 과정에서 부모가 아닌 형제 노드가 방문한 경로를 중복 경로로 판단할 수 있기 때문이다.

이 과정을 통해 순환 경로의 존재 여부를 판단한다.

traced = set()  # 3-1

def dfs(i):
    if i in traced:  #3-2
        return False

    set.add(i)

    # 2 
    for b in graph[i]: 
        if not dfs(b):
            return False
    # 4
    set.remove(i)

    return True

# 1
for a in list(graph):
    if not dfs(a):
        return False

3) 전체 코드

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(list)
        # 그래프 구성
        for x, y in prerequisites:
            graph[x].append(y)

        traced = set()

        def dfs(i):
            # 순환 구조이면 False
            if i in traced:
                return False

            traced.add(i)
            for y in graph[i]:
                if not dfs(y):
                    return False
            # 탐색 종료 후 순환 노드 삭제
            traced.remove(i)

            return True

        # 순환 구조 판별
        for x in list(graph):
            if not dfs(x):
                return False

        return True

1.  IP 주소의 특징

• (계층형) IP 주소가 ‘어떤 네트워크에 속하는 어떤 컴퓨터에 해당하는지’를 구분하기 위해 주소를 계층형으로 구분함
• (IP 주소 할당 주체) IP 주소는 ‘네트워크 관리자’가 컴퓨터에 할당함
• (IP 주소 할당 시점) IP 주소는 네트워크에 접속할 때마다 할당됨
• (논리 주소의 종류)
  • MAC 주소와 마찬가지로 유니캐스트, 멀티캐스트, 브로드캐스트가 있음
  • 유니캐스트 주소 중에서 네트워크를 표시하는 번호는 접속되어 있는 네트워크에서 유일해야 함
• (유일성) 네트워크 상 주소는 ‘네트워크 번호’와 ‘컴퓨터 번호’를 조합해서 유일해
  • 네트워크 번호는 접속되어 있는 모든 네트워크에서 유일함
  • 컴퓨터 번호는 네트워크 내에서 유일

2.  IP 주소 구성

• (IP 주소 구성)
  • IP 주소는 32비트로 구성됨
  • 8비트마다 10진수로 표기하고, 옥텟(Octet)으로 구분함

3. IP 주소의 클래스

• (네트워크 번호 관리) 체계적인 분류를 위해서 ICANN(The Internet Corporation for Assigned Names and Number)에서 실제 네트워크를 사용하는 조직에 할당
• (클래스) ICANN로부터 네트워크 번호를 할당받는 기관의 규모에 따라 대출 IP 주소의 범위를 결정하는 것
• (클래스의 특징)
  • (클래스 분류) IP 주소를 조직의 규모에 따라 A~E로 나누고 그 범위의 주소를 할당함
  • (클래스 식별) 클래스별 IP 주소는 최초 옥텟의 맨 앞 몇 비트로 구분함
  • (네트워크 번호와 컴퓨터 번호)
    • 네트워크 번호 부분의 비트수가 적으면 컴퓨터 번호 부분의 비트수가 많아짐
    • 따라서 규모가 큰 기관일수록 A클래스에 가까운 범위의 IP 주소를 할당 받음
• (클래스풀 어드레싱) 클래스로 나누어 IP를 할당하는 방식을 클래스풀 어드레싱(Classfull Adressing)이라고 함

4. 예약 완료 주소

• (호스트 번호) 네트워크 번호는 ICANN이 관리하는 반면, 컴퓨터 번호, 즉 호스트 번호는 네트워크 관리자가 임의로 설정함
• (네트워크 주소)
  • 호스트가 속한 네트워크 자체를 표시하는 주소임
  • 컴퓨터 번호의 비트를 모두 1로 설정함
  • 다른 컴퓨터가 사용하지 못하는 고유 주소
• (브로드캐스트 주소)
  • 네트워크 참여자 전체가 수신하는 주소임
  • 컴퓨터 번호의 비트를 모두 0으로 설정함
  • 다른 컴퓨터가 사용하지 못하는 고유한 주소

'하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴' 참조

1. 3계층의 역할과 개요

1) 네트워크

• (세그먼트) 라우터 없이 분배(허브)로 연결되어 있는 범위를 말하며, 라우터와 라우터 간의 범위라고 표현할 수 있다.
• (네트워크) ‘3계층’에서 사용하는 네트워크란 용어는 세그먼트와 동의어로 라우터와 라우터로 분배된 그룹을 의미함

2) 인터넷 작업

• (네트워크 분할 이유)
  • (브로드캐스트 문제) 네트워크 내에 컴퓨터의 수가 많아지면 브로드캐스트 신호 발생이 잦아져 신호 처리 횟수가 증가함
  • (네트워크 분할) 라우터를 넘어서는 브로드캐스트는 송신되지 않으므로, 브로드캐스트의 범위를 제한할 수 있음
• (인터넷 작업) 네트워크 간에서 데이터 송수신을 인터넷 작업(Internetwork)이라고 함

2. 인터넷 프로토콜

1) 3계층의 역할과 IP

• (어드레싱) 어떤 어드레스를 어떻게 배당할지에 관한 작업으로 3계층을 위한 주소가 필요함
  • (물리주소) 2계층에서 사용하는 주소로 MAC 주소가 대표적임
  • (논리주소) 3계층에서 사용하는 주소로 사용자의 위치정보를 나타냄
  • (차이점) 주소에 ‘위치 정보’가 포함되었는지 여부
  • (어드레스 구성) 물리주소와 논리주소의 조합, 즉 어디 네트워크(위치)에 어떤 컴퓨터(기기)에 대한 정보로 구성됨
• (라우팅) 수신처에 연결되어 있는 네트워크의 경로를 선택하여 데이터를 보내는 작업

2) 인터넷 프로토콜

• (IP 의미) 어드레싱과 라우팅에 의하여 인터넷 작업을 수행하기 위한 프로토콜
• (IP 버전) ‘IPv4’와 ‘IPv6’로 나뉘며 두 버전 사이에 호환성은 없음
• (IP 데이터그램) 4계층 PDU에 IP 헤더가 붙은 PDU를 IP 데이터그램(Datagram)이라고 함

| '파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 일정 재구성(리트코드 332)

- 문제: [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순(Lexical Order)로 방문한다.
  - Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
  - Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

티켓의 출발지와 도착지가 주어질 때, 가능한 여행 경로를 구하는 문제다.

만약 출발지에 도착지가 두개 이상이라면, 알파벳 순서가 빠른 곳으로 간다.

JFK에서 갈 수 있는 곳은 ‘SFO’와 ‘ATL’ 두 곳인데,

‘ATL’이 알파벳 순서가 빠르기 때문에 이곳을 먼저 방문한다.

따라서 JFK → ATL → JFK → SFO → ATL → SFO 순서대로 방문한다.

2. 풀이 - 재귀함수를 활용한 DFS 탐색

1) 그래프 만들기

이동 가능한 경로를 그래프로 나타내야 한다

출발점을 key로 도착 가능한 지역들을 value로 입력한 딕셔너리 형태로 구성한다.

# 그래프 사전식 순서대로 구성
        dict = collections.defaultdict(list)

        for a,b in sorted(tickets):
            dict[a].append(b)

코드를 살펴보면,

우선 ‘defaultdict’ 매서드로 빈 그래프(dict)를 만든다.

중요한 것은 도착 지점들이 알파벳 순으로 정렬돼야 한다는 점이다.

따라서 입력값(tickets)을 먼저 정렬하면 key의 문자열이 빠른 순으로 정렬되고, key가 같을 경우 value가 빠른 순으로 정렬된다.

그 후, 딕셔너리에 출발점을 key로, 도착지를 value로 입력한다면,

도착지는 알파벳 순으로 정렬되어 있을 것이다.

2) 재귀호출 및 dfs 탐색

‘JFK’에서 출발하여 도착 가능한 경로 중 알파벳이 빠른 곳에 먼저 방문한다.

앞서 도착지를 미리 정렬했기 때문에 도착지 리스트 중 맨 앞의 것을 추출(pop())하면 된다.

위 그림에서는 ‘ATL’이 첫 번째 도착지에 해당할 것이다.

추출한 값 ‘ATL’을 다시 입력값으로 넣어 재귀 함수를 호출하면,

이번에는 알파벳이 가장 앞선 도착지 ‘JFK’가 되고 해당 값을 추출하여 재귀 호출하는 과정을 반복한다.

마지막 지점까지 도착했다면, 마지막 지점부터 경로 리스트(route)에 차례대로 담는다.

route = []

      # value의 첫 번째 값을 읽어 어휘순 방문
      def dfs(a):
          while dict[a]:
              dfs(dict[a].pop(0))

          route.append(a)

      dfs('JFK')

3) 결과 출력 및 전체 코드

위와 같이 마지막 지점부터 경로 리스트에 담기면, 결국 경로가 거꾸로 저장된다.

따라서 최종 결과 값을 뒤집어서 알파벳 순서대로 다시 정렬한다. 전체 코드는 아래와 같다.

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """ 

        # 그래프 사전식 순서대로 구성
        dict = collections.defaultdict(list)

        for a,b in sorted(tickets):
            dict[a].append(b)

        route = []

        # value의 첫 번째 값을 읽어 어휘순 방문
        def dfs(a):
            while dict[a]:
                dfs(dict[a].pop(0))

            route.append(a)

        dfs('JFK')

        # 다시 뒤집어서 어휘순 결과대로 리턴
        return route[::-1]

'파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 조합의 합(리트코드 39)

- 문제: 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다. 
  - Input: candidates = [2,3,6,7], target = 7
  - Output: [[2,2,3],[7]]

배열(candidates)의 요소를 더해서 특정 수(target)를 만드는 문제다.

중복해서 수를 뽑을 수 있다는 점이 중요한 조건이다.

위 예를 보면 2, 3, 6, 7 중에서 임의로 숫자를 뽑아 더한 다음 7을 만든다.

‘2+2+3 = 7 ‘과 ‘7 = 7’ 두 가지 경우의 수가 발생하므로,

정답은 [ [2, 2, 3] , [7] ] 이 된다.

2. 풀이 - DFS로 그래프 탐색

1)

풀이 과정의 일부를 도식화 하면 위 그림과 같다.

숫자 2부터 경로를 찾아나간다.

다음 경로의 후보로 ‘자기 자신 + 뒤에 나열된 수’가 된다.

2의 경우 [2, 3, 4, 5]이고,

3의 경우 [3, 4, 5]가 될 것이다.

2)

위 과정을 재귀함수로 구현한다.

csum은 구하고자 하는 값(target)에서 탐색한 경로의 값의 차이다.

예를 들어, 맨 처름 숫자 2를 선택했으면, 앞으로 ‘7-2 = 5’만큼을 더 찾아야 한다.

‘index’는 ‘자기자신 + 뒤에 나열된 수’의 순서를 나타낸다.

마지막으로 ‘path’는 지나온 경로를 담고 있으며, 정답을 충족할 경우 ‘result’ 변수에 담기게 된다.

3)

위의 예에서, 2를 총 네번 선택하는 경로를 선택(7-2-2-2-2 = -1)한다면,

값이 1만큼 초과하여 오답이 되어 해당 경로는 탐색이 종료된다.

이번에 2를 세 번 선택할 경우를 살펴보면,

‘7-2-2-2 =1 ‘로 값이 1만큼 부족하기 때문에 오답이 된다.

인덱스를 1만큼 증가시켜서 ‘2’ 세 번, ‘3’ 한 번을 탐색할 경우

‘7-2-2-3 = 0’으로 정답에 해당하며, ‘result’ 변수에 담긴다.

이처럼 경로의 값들을 더했을 때 원하는 값(target)을 초과할 경우, 탐색을 종료한다.

경로의 합이 원하는 값과 일치할 경우, 해당 경로를 정답 리스트에 추가한다.

3. 전체 코드

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        result = []

        def dfs(csum, index, path):

            # 종료 조건
            if csum < 0:
                return

            elif csum == 0:
                result.append(path)
                return 

            # 자신부터 하위 원소까지의 나열 재귀 호출
            for i in range(index, len(candidates)):
                dfs(csum-candidates[i], i, path + [candidates[i]])


        dfs(target, 0, [])

        return result

‘하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴)’ 참조

1) 버퍼링

• (버퍼) 데이터를 일시적으로 기록하는 장치
• (버퍼링)
  • 스위치에 수신처(포트)가 동일한 프레임(신호)이 도달할 경우 충돌을 방지하는 기법
  • 충돌할 것 같은 프레임을 버퍼에 일시적으로 저장함
  • 하나의 프레임을 먼저 송신한 후, 버퍼에 저장한 나머지 프레임을 송신함
• (버퍼의 용량 제한) 스위치에 수신처가 같은 프레임이 연속적으로 도달할 경우 버퍼가 부족해지므로 송신을 중지함
  • (백 프레셔) 스위치가 반이중 방식을 사용할 경우 스위치는 송신처에 ‘JAM 신호’(신호 충돌 알림)를 보내서 송신을 중지시킴
  • (IEEE802.3x) 스위치가 전이중 이더넷에 대응하면 스위치는 송신처에 ‘PAUSE 프레임’을 보내어 송신을 중지시킴

2) 전이중 이더넷

• (반이중 통신)
  • ‘누군가가 송신 중’일 때는 송신이 불가능하고, ‘자기가 송신 중일 때는 수신이 불가능'한 통신 방식으로 무전기의 통신 방식과 유사함.
  • ‘CSMA/CD’가 반이중 통신(Half-Duplex) 방식을 사용함
• (전이중 통신) 송신과 수신을 동시에 할 수 있는 통신 방식
• (전이중 이더넷)
  • (의미) 스위치를 사용해 전이중 통신을 하는 것을 전이중 이더넷이라고 함
  • (효용) 허브와 달리 스위치를 사용할 경우 충돌이 발생하지 않기 때문에 CSMA/CD를 사용할 필요가 없음

‘하루 3분 네트워크 교실(아미노 에이지, 김현주, 영진닷컴)’ 참조

1) 허브와 스위치

• (케이블과 허브) 케이블(UTF 또는 광파이버)은 ‘송신’ 신호와 ‘수신'신호가 구분되어 전송되므로 충돌이 발생하지 않으며, 실질적인 충돌은 허브에서 발생
• (스위치) 충돌을 방지하기 위한 방법으로 신호를 보내는 타이밍이 겹치지 않게 하는 것과, 신호가 지나는 길이 나누는 방법이 있는데 스위치는 허브 대신 사용하여 후자의 기능을 담당함

2) MAC 주소 필터링

• (스위치 기능) 수신한 프레임을 따로 구분하여 송신하는 역할을 하며 ‘MAC 주소 필터링'과 ‘버퍼링' 두가지 방법을 사용함
  • (MAC 주소 필터링) 서로 다른 수신처(포트)에 대한 프레임(신호)이 스위치에 동시 도달한 경우 사용
  • (버퍼링) 서로 같은 수신처(포트)에 대한 프레임(신호)이 스위치에 동시 도달한 경우 사용
• (MAC 주소 필터링)
  • (학습) 스위치가 수신한 프레임의 송신처 MAC 주소를 기록하여 포트와 MAC를 연관 지으며 이를 ‘어드레스 테이블’로 나타냄
  • (스위칭) 프레임을 수신한 스위치는 프레임의 MAC 주소를 확인하고, MAC 주소에 대응하는 포트에만 프레임을 송신하여 충돌을 방지함!