네트워크 노드와 링크(엣지)들이 서로 연결되어 리소스를 공유하는 구조이며, 그래프 형태로 표현할 수 있다. 노드: 서버, 라우터, 스위치 링크: 유선 or 무선 키워드 네트워크 토폴로지 클라이언트와 서버 패킷 주소와 전송 방식 프로토콜 네트워크 참조 모델 통신이 이루어지는 단계를 계층적으로 표현한 모델 OSI Model 계층 대표 역할 Application HTTP, DNS 등 네트워크 서비스 Presentation 인코딩, 압축, 암호화 Session 세션 관리 Transport TCP, UDP Network 라우팅, IP Data Link 같은 LAN에서의 통신 Physical 비트 전송 TCP/IP Model 응용 계층(Application Layer): OSI 모델에서 세션, 표현, 응용 계층 전송 계층(Transport Layer): OSI 모델에서 전송 계층 인터넷 계층(Internet Layer): OSI 모델에서 네트워크 계층 네트워크 액세스 계층(Network Access Layer): OSI 모델에서 데이터 링크 계층 (+ 물리 계층) 캡슐화와 역캡슐화(Encapsulation, Decapsulation) 캡슐화 데이터가 계층를 거치면서 헤더가 추가되는 과정, 상위 계층로부터 내려받은 패킷을 페이로드로 하고, 각 계층에 포함된 프로토콜의 헤더나 트레일러를 덧붙이는 과정 역캡슐화 캡슐화 과정에서 덧붙인 헤더들을 각 계층에서 확인한 뒤, 제거하는 과정 각 계층마다 패킷을 부르는 명칭이 다르다. ...

문제 https://www.acmicpc.net/problem/14891 풀이 상황 설명이 굉장히 난해하고 비직관적이므로 글을 잘 읽어야 한다. 문제를 겨우 이해하고 나면 알고리즘이나 구현 능력 자체는 크게 요구하지 않는다. 글을 이해하는것 자체가 이 문제의 가장 큰 난관이다. 이 문제에서 톱니바퀴는 현실의 톱니바퀴처럼 움직이지 않는다. 이전 톱니바퀴가 회전하면 다음 톱니바퀴도 회전해야할지 말아야 할지를 이미 돌아간 상태의 이전 톱니바퀴가 아닌 돌기 전의 이전 톱니바퀴의 상태로 판단해야 한다. 코드 class Gear(): def __init__(self, stat): self.__stat = stat self.__top = 0 self.__left = 6 self.__right = 2 def rotate(self, drct): self.__top = (self.__top - drct) % 8 self.__left = (self.__left - drct) % 8 self.__right = (self.__right - drct) % 8 @property def top(self): return self.__stat[self.__top] @property def left(self): return self.__stat[self.__left] @property def right(self): return self.__stat[self.__right] def left_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num - 1, 0, -1): if gears[next_gear].right != gears[cur_gear].left: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break def right_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num + 1, 5): if gears[next_gear].left != gears[cur_gear].right: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break gear1 = Gear(list(map(int, input()))) gear2 = Gear(list(map(int, input()))) gear3 = Gear(list(map(int, input()))) gear4 = Gear(list(map(int, input()))) gears = [None, gear1, gear2, gear3, gear4] k = int(input()) answer = 0 rotate_queue = [] for _ in range(k): num, drct = map(int, input().split()) rotate_queue.append((num, drct)) left_shift(num, drct) right_shift(num, drct) for g, d in rotate_queue: gears[g].rotate(d) rotate_queue = [] rank = 1 for idx in range(1, 5): answer += gears[idx].top * rank rank *= 2 print(answer)

문제 https://www.acmicpc.net/problem/14890 풀이 경사로의 방향을 생각해보면 왼쪽에서 오른쪽으로 올라가는 방향이 있을 것이고, 그 반대인 오른쪽에서 왼쪽으로 올라가는 방향도 있을 것이다. 이러한 경우에는 한 번에 해결하기 보다는 배열을 정방향, 역방향으로 각각 순회하여 경사로를 만들어주는 것이 좋다. 따라서 알고리즘은 다음과 같다. 주어진 2차원 배열을 Transpose한 배열을 하나 더 만든다. 세로 모양의 길을 찾기 위해서이다. 정방향으로 우선 순회한다. 다음에 있는 칸의 높이가 현재 칸보다 같으면 count를 하나 늘리고(count는 경사로를 지을 수 있는지 판단할 때 사용한다.) 1 낮으면 일단은 패스(역방향에서 확인한다), 1 높으면 경사로를 설치할 수 있는지 판단한다. 경사로를 설치할 수 있는지 판단하는 기준은 두 가지이다. 일단 경사로를 설치하기 충분한 공간이 확보되었는가 (count로 충분한 공간이 얼마나 있는지를 알 수 있다.), 만약 가능하다면 이미 그곳에 경사로가 설치되어 있지는 않는가(이는 is_built 배열로 추적한다. 하지만 정방향을 먼저 하므로 지금 상황에선 필요 없다.) 역방향으로 순회한다. 정방향과 같지만 정방향을 순회하면서 경사로를 지은 곳을 유의할 필요가 있다. 코드 def check(line): is_built = [False] * n current_height = line[0] count = 1 for idx in range(1, n): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): is_built[idx - back] = True count = 1 else: return False current_height = line[idx] else: return False current_height = line[n - 1] count = 1 for idx in range(n - 2, -1, -1): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): if is_built[idx + back]: return False is_built[idx + back] = True count = 1 else: return False current_height = line[idx] else: return False return True n, l = map(int, input().split()) graph = [] graph_tranposed = [[0] * n for _ in range(n)] answer = 0 for _ in range(n): graph.append(list(map(int, input().split()))) for row in range(n): for column in range(n): graph_tranposed[row][column] = graph[column][row] for idx in range(n): answer += 1 if check(graph[idx]) else 0 answer += 1 if check(graph_tranposed[idx]) else 0 print(answer)

문제 https://www.acmicpc.net/problem/14499 풀이 특별한 알고리즘이나 문제 해결 기법을 사용할 필요 없이, 순수하게 딕셔너리 자료구조만을 사용해서 풀 수 있는 문제이다. 주어진 주사위의 전개도를 이용하여 각 면에 숫자를 붙이고(면에 써져있는 숫자가 아닌 각 면을 인식하게 해주는 숫자, 이하 ID숫자라고 하겠다.) 이를 방향: ID 숫자의 꼴로 딕셔너리를 생성한다. 또 ID숫자: 면에 적힌 숫자 꼴로 딕셔너리를 하나 더 생성하여 두개의 딕셔너리로 주사위의 방향과 각 면에 적혀있는 숫자를 추적할 수 있다. 코드 import copy def north(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["s", "n", "u", "e", "w", "l"]): dice_drct[new] = original_drct[ori] def south(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["n", "s", "l", "e", "w", "u"]): dice_drct[new] = original_drct[ori] def east(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["w", "e", "n", "u", "l", "s"]): dice_drct[new] = original_drct[ori] def west(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["e", "w", "n", "l", "u", "s"]): dice_drct[new] = original_drct[ori] def change(): if graph[x][y] == 0: graph[x][y] = dice_num[dice_drct["l"]] else: dice_num[dice_drct["l"]] = graph[x][y] graph[x][y] = 0 def check(x, y): if x < 0 or x >= n or y < 0 or y >=m: return False return True n, m, x, y, k = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) orders = list(input().split()) dice_num = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0} dice_drct = {"u": 1, "l": 6, "n": 2, "e": 3, "w": 4, "s": 5} for order in orders: isTrue = False if order == "1": if check(x, y + 1): y += 1 east() change() isTrue = True if order == "2": if check(x, y - 1): y -= 1 west() change() isTrue = True if order == "3": if check(x - 1, y): x -= 1 north() change() isTrue = True if order == "4": if check(x + 1, y): x += 1 south() change() isTrue = True if isTrue: print(dice_num[dice_drct["u"]])

문제 https://www.acmicpc.net/problem/12100 풀이 최대 20 * 20 크기의 보드에서 2048 게임을 하는 것이다. 최대 5번의 이동만 한다고 문제에 주어져 있으므로, 모든 경우를 탐색하여 문제를 풀 수 있다. 이 문제에서 주의해야할 점은 다음과 같다. 이동하는 방향에서 가까운 숫자부터 이동해야한다. 한 번의 이동동안 이미 합쳐진 숫자는 다시 합쳐지지 않는다. 이 두가지 조건만 잘 생각하면서 작성하면 된다. 코드 import Foundation func dfs(_ size: Int) { if size == 5 { for row in 0..<n { for column in 0..<n { answer = max(answer, graph[row][column]) } } return } for i in 0..<4 { let currentGraph = graph shift(i) dfs(size + 1) graph = currentGraph } } func shift(_ order: Int) { var isMerged = [[Bool]](repeating: [Bool](repeating: false, count: n), count: n) if order == 0 { for row in 0..<n { for column in 0..<n { if graph[row][column] != 0 { var newRow = row while newRow > 0 { if graph[newRow - 1][column] == 0 { let temp = graph[newRow][column] graph[newRow][column] = graph[newRow - 1][column] graph[newRow - 1][column] = temp newRow -= 1 } else if graph[newRow][column] == graph[newRow - 1][column] { if isMerged[newRow - 1][column] { break } let temp = graph[newRow][column] graph[newRow][column] = graph[newRow - 1][column] graph[newRow - 1][column] = temp * 2 graph[newRow][column] = 0 isMerged[newRow - 1][column] = true break } else { break } } } } } } if order == 1 { for column in 0..<n { for row in (0..<n).reversed() { if graph[row][column] != 0 { var newRow = row while newRow < n - 1 { if graph[newRow + 1][column] == 0 { let temp = graph[newRow][column] graph[newRow][column] = graph[newRow + 1][column] graph[newRow + 1][column] = temp newRow += 1 } else if graph[newRow][column] == graph[newRow + 1][column] { if isMerged[newRow + 1][column] { break } let temp = graph[newRow][column] graph[newRow][column] = graph[newRow + 1][column] graph[newRow + 1][column] = temp * 2 graph[newRow][column] = 0 isMerged[newRow + 1][column] = true break } else { break } } } } } } if order == 2 { for row in 0..<n { for column in 0..<n { if graph[row][column] != 0 { var newColumn = column while newColumn > 0 { if graph[row][newColumn - 1] == 0 { let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn - 1] graph[row][newColumn - 1] = temp newColumn -= 1 } else if graph[row][newColumn] == graph[row][newColumn - 1] { if isMerged[row][newColumn - 1] { break } let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn - 1] graph[row][newColumn - 1] = temp * 2 graph[row][newColumn] = 0 isMerged[row][newColumn - 1] = true break } else { break } } } } } } if order == 3 { for row in 0..<n { for column in (0..<n).reversed() { if graph[row][column] != 0 { var newColumn = column while newColumn < n - 1 { if graph[row][newColumn + 1] == 0 { let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn + 1] graph[row][newColumn + 1] = temp newColumn += 1 } else if graph[row][newColumn] == graph[row][newColumn + 1] { if isMerged[row][newColumn + 1] { break } let temp = graph[row][newColumn] graph[row][newColumn] = graph[row][newColumn + 1] graph[row][newColumn + 1] = temp * 2 graph[row][newColumn] = 0 isMerged[row][newColumn + 1] = true break } else { break } } } } } } } var n = Int(readLine()!)! var graph = [[Int]]() for _ in 0..<n { graph.append(readLine()!.split(separator: " ").map { Int(String($0))! }) } var answer = 0 dfs(0) print(answer)

문제 https://www.acmicpc.net/problem/13460 풀이 기울이는 방향에 따라서 구슬이 이동하므로, 구슬이 이동할 수 있는 방향은 상하좌우임을 알 수 있다. 이 때, 한 번 기울일 때 마다 구슬의 최종 위치는 하나가 나오므로, BFS를 이용해서 문제를 해결할 수 있다. 문제의 조건을 정리하면 다음과 같다. 한 칸에는 구슬 한 개만 들어갈 수 있다. 한 번 기울이면 구슬이 더 이상 움직이지 못할 때 까지 움직인다. 10번 이하의 횟수로만 기울인다. 1, 2 조건을 조합하면 구슬이 다른 구슬을 만나도 벽을 만난것과 같음을 알 수 있고, 따라서 구슬이 겹친 경우에는 처리를 해줘야 한다. ...

문제 https://www.acmicpc.net/problem/5558 파파고 번역 올해도 JOI 마을의 치즈 공장이 치즈 생산을 시작하여, 쥐들이 둥지에서 얼굴을 내밀었다. JOI 마을은 동서남북으로 구획 정리되어 있고, 각 구획은 둥지, 치즈 공장, 장애물, 공터 중 하나이다. 쥐들은 둥지에서 출발하여 모든 치즈 공장을 방문 하여 치즈를 한 개씩 먹는다. 이 마을에는 N개의 치즈 공장이 있는데, 모든 공장이 한 종류의 치즈만을 생산한다. 치즈의 단단함은 공장마다 다르고 단단함도 다르다 1부터 N까지의 치즈를 생 산하는 치즈공장이 마침 하나씩 있다. 증가 쥐들의 첫 번째 체력은 1이고, 치즈를 한 개 먹을 때마다 그들의 체력은 1증가 하지만, 쥐들은 자신의 체력보다 더 단단한 치즈를 먹을 수는 없다. 쥐는 동서남북으로 이웃한 구역으로 1분이면 이동할 수 있지만, 장애물 구역에는 들어갈 수 없다. 치즈 공장을 치즈를 먹지 않고 지나갈 수도 있다. 치즈를 다 먹을 때까지 걸리는 가장 짧은 시간을 요구하는 프로그램을 작성하라. 쥐가 치즈를 먹 는 데 걸리는 시간은 무시할 수 없다. 풀이 처음에 문제를 읽었을 땐, 치즈를 먹는 순서를 어떻게 정해야 하나 싶었지만, 시작 할 때 쥐의 체력이 1 고정이므로 고민할 필요 없이 1, 2, 3, …, N 순서대로 먹으면 된다. ...

문제 https://www.acmicpc.net/problem/15591 풀이 문제가 복잡하게 설명되어 있다. 중요한 것은 모든 노드가 연결되어 있고 웨이트를 가진 엣지가 존재하지만, 두 노드간의 거리는 경로상의 가장 작은 웨이트를 가진 엣지가 된다. 따라서 웨이트가 있다 해서 다익스트라를 쓸 필요가 없다. 들어오는 쿼리마다 BFS를 이용하여 그래프를 탐색하고 두 노드간의 거리는 실시간으로 업데이트 해주면 된다. 코드 from collections import deque def bfs(k, v): queue = deque() queue.append((v, 987_654_321)) isVisited = [False] * (n + 1) isVisited[v] = True answer = 0 while queue: cur_node, cur_usado = queue.popleft() for next_node, next_usado in graph[cur_node]: if isVisited[next_node]: continue if cur_usado < next_usado: next_usado = cur_usado if next_usado >= k: queue.append((next_node, next_usado)) isVisited[next_node] = True answer += 1 print(answer) n, q = map(int, input().split()) graph = {} for _ in range(n - 1): pi, qi, ri = map(int, input().split()) if pi in graph: graph[pi].append((qi, ri)) else: graph[pi] = [(qi, ri)] if qi in graph: graph[qi].append((pi, ri)) else: graph[qi] = [(pi, ri)] for _ in range(q): k, v = map(int, input().split()) bfs(k, v)

문제 https://www.acmicpc.net/problem/10021 풀이 “모든 필드를 파이프 네트워크로 연결하는 데 필요한 최소 금액"에서 MST 문제임을 알았다. 크루스칼 알고리즘을 쓰면 쉽게 풀릴 문제다. 우선 각 노드간의 거리를 알 수 없으므로 모든 경우의 수를 계산해야 한다. 필드의 개수가 2000개 이하이므로 O(n^2)의 연산을 해도 충분하다. 그 이후에는 크루스칼 알고리즘을 적용하면 되는데, 제약조건 중 하나가 비용이 C 미만인 파이프는 만들지 않는다는 것이다. 따라서 두 노드간 거리가 C 미만인 엣지는 존재하지 않는 것으로 해야한다. 코드 def find(field): if parent[field] == field: return field else: parent[field] = find(parent[field]) return parent[field] def union(a, b): pa = find(a) pb = find(b) if pa != pb: parent[pa] = pb def squared_euclidean_length(a, b): return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2 n, c = map(int, input().split()) fields = [] mapping = {} for idx in range(n): xi, yi = map(int, input().split()) fields.append((xi, yi)) mapping[(xi, yi)] = idx edges = [] parent = list(range(n)) for i in range(0, len(fields) - 1): for j in range(i + 1, len(fields)): distance = squared_euclidean_length(fields[i], fields[j]) if distance >= c: edges.append((mapping[fields[i]], mapping[fields[j]], distance)) edges.sort(key = lambda x: x[2]) answer = 0 count = 0 for edge in edges: if find(edge[0]) != find(edge[1]): union(edge[0], edge[1]) answer += edge[2] count += 1 print(answer if count == n - 1 else -1)

문제 https://www.acmicpc.net/problem/14226 풀이 현재 상태를 나타내는 변수를 화면에 있는 이모티콘의 개수, 클립보드에 저장되어 있는 이모티콘의 개수로 나타낼 수 있다. 각각의 연산이 모두 1초가 걸리므로 BFS를 사용할 수 있다. BFS를 사용하려면 노드에 방문했는지를 판별할 방법이 필요한데, 여기에선 Array보다는 Set을 쓰는것이 효율적이다. 두 개의 정수가 노드를 구성하므로 2차원 배열을 만들면 되겠지만, 이런 방식으로 한다면 배열의 크기가 너무 커질 뿐더러 효율적인 배열의 크기를 정하기도 머리가 복잡해진다. 따라서 방문한 노드를 Set에 저장해서 contains()함수로 방문 여부를 판단하는 방식을 이용한다. ...