전체 글

[네트워크] 3. 네트워크 기술

(쉽게 배우는 데이터 통신과 컴퓨터 네트워크 3장) 3. 네트워크 기술 라우팅 기능 라우팅 시스템: 데이터를 최종 목적지까지 올바른 경로로 중개하는 교환(Switching) 기능 라우팅 시스템의 종류 회선 교환 Circuit Switching 연결형 서비스 제공 아날로그 환경 음성 전화 서비스를 통해 발전 고정 대역폭의 전송률 지원 → 다른 연결에서 이 대역을 사용할 수 없음 네트워크 구조 단순 하나의 연결에 대해 전송되는 모든 데이터가 동일한 경로로 라우팅됨 패킷 교환 시스템 디지털 환경의 컴퓨터 네트워크에서 발전 가변 대역의 전송률 지원 네트워크 구조 복잡 컴퓨터 네트워크 환경 데이터를 미리 패킷 단위로 나누어 전송- 패킷을 기준으로 라우팅 프레임 릴레이 데이터의 전송 속도 향상 1. 라우팅 시스템 ..

[백준] 17135 - 캐슬 디펜스 (자바 Java)

[Gold III] 캐슬 디펜스 - 17135 문제 링크 성능 요약 메모리: 32012 KB, 시간: 312 ms 분류 브루트포스 알고리즘(bruteforcing), 그래프 이론(graphs), 구현(implementation), 시뮬레이션(simulation) 문제 설명 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다...

[백준] 17471 - 게리맨더링 (자바 Java)

[Gold IV] 게리맨더링 - 17471 문제 링크 성능 요약 메모리: 14924 KB, 시간: 136 ms 분류 너비 우선 탐색(bfs), 브루트포스 알고리즘(bruteforcing), 조합론(combinatorics), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 수학(math) 문제 첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다. 셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다. 구역 A가 구역 ..

[백준] 14503 - 로봇 청소기 (자바 Java)

[Gold V] 로봇 청소기 - 14503 문제 링크 성능 요약 메모리: 17312 KB, 시간: 168 ms 분류 구현(implementation), 시뮬레이션(simulation) 문제 설명 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 현..

[백준] 16236 - 아기 상어 (자바 Java)

[Gold III] 아기 상어 - 16236 문제 링크 성능 요약 메모리: 295204 KB, 시간: 664 ms 분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation), 시뮬레이션(simulation) 문제 설명 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 ..

[백준] 1003 - 피보나치 함수 (자바 Java)

[Silver III] 피보나치 함수 - 1003 문제 링크 성능 요약 메모리: 13004 KB, 시간: 116 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1..

[백준] 2096 - 내려가기 (자바 Java)

[Gold V] 내려가기 - 2096 문제 링크 성능 요약 메모리: 236080 KB, 시간: 1228 ms 분류 다이나믹 프로그래밍(dp), 슬라이딩 윈도우(sliding_window) 문제 설명 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 ..

[알고리즘] 플로이드-워샬 알고리즘

플로이드-워샬 알고리즘 모든 쌍 최단 경로 알고리즘: 모든 정점 쌍 사이의 최단 경로를 구하는 방법 단순 최단 경로 알고리즘 m개의 간선을 사용해서 i에서 j까지 이르는 최단거리 모든 정점 k에 대해 최대 m-1개의 간선을 사용해서 i에서 k까지 이르는 최단거리 $d_{ik}^{m-1}$에다가 $w_{kj}$를 더한 값을 구하고, 이 중 가장 짧은 것을 택함 for (i=1 to n) for (j=1 to n) d(i to j, k=0) = w[i][j]; for (m=2 to n-1) for (i=1 to n) for (j=1 to n) d(i to j, k=m) = min(d(i to k, k=m-1) + w[k][j]) 시간 복잡도: $\theta(n^4)$ 플로이드-워샬 $d_{ij}^{k}$ =..

[알고리즘] 위상 정렬 Topological Sort (자바 Java)

위상 정렬 사이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬 간선 (i, j)가 존재하면 정점 i는 반드시 j보다 앞에 위치 방식 1: 큐 활용 topologicalSort(G, V) { for i

[백준] 2293 - 동전 1, 2294 - 동전 2 (자바 Java)

[Gold V] 동전 1 - 2293 문제 링크 성능 요약 메모리: 13068 KB, 시간: 128 ms 분류 다이나믹 프로그래밍(dp) 문제 설명 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 풀이 dp는 왜 해도..