프로그래밍 공방

문제 www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 문제해결방법 이 문제는 최소 공통 조상(LCA)를 찾아서 푸는 문제였다. 2^i 번째 조상을 저장하는 배열로 만들면서 동일한 방법으로 2^i 까지의 경로에 있는 도로의 길이의 최대, 최소값을 저장하는 배열을 만든다. 두 도시가 주어지면 LCA를 찾으러 올라가면서 도로의 길이의 최대, 최소값을 찾으면서 올라간다. 코드 12345678910111213141516171..

유니캐스트 : unicast 고유 주소로 식별된(MAC) 하나의 네트워크 목적지에 1:1로 트래픽 또는 메시지를 전송하는 방식 목적지 주소가 아닌 다른 호스트가 해당 프레임을 받았을 때 랜카드에서 프레임의 목적지 주소가 자신의 MAC address가 아니라고 판단되면 랜카드가 프레임을 버리게 된다(CPU 까지 올라가지 않아 성능에 저하가 없다.) 브로드 캐스트 : broadcast 송신 호스트가 전송한 데이터가 네트워크에 연결된 모든 호스트에 전송되는 방식 브로드 캐스트 도메인 LAN 상에서 어떤 단말이 브로트 캐스트 패킷을 송출할 때, 이 패킷에 대해 네트워크에서 영향을 받는 영역 브로드 캐스트 주소 IP 주소의 호스트 부분이 모두 1인 것을 브로드 캐스트 주소라고 한다 IP의 목적지 주소가 브로드 캐..

MAC (Media Access Control) address 데이터 링크 계층에서 통신을 위해 네트워크 인터페이스(NIC)에 할당된 고유 식별 주소 MAC 주소는 총 48비트로 구성되어 있다. 주소 표기 방법 00-60-97-8F-4F-86 / 00:60:97:8F:4F:86 / 0060.978F.4F86 위 3개는 모두 같은 호스트를 나타냅니다. 위 주소에서 앞에 24bit(6개의 16진수)는 벤더(생산자)를 나타내는 코드로 OUI(Organizational Unique Identifier)라고 한다. ARP (Address Resolution Protocol) : 주소 결정 프로토콜 네트워크 상에서 IP 주소를 물리적 네트워크 주소로 bind 시키기 위해 사용되는 프로토콜 ARP의 과정 1. 보통 ..

Lower Bound : 찾는 값과 같거나 큰 값이 처음으로 나타나는 위치 (이상) Upper Bound : 찾는 값 보다 큰 값이 처음으로 나오는 위치 (초과) [1, 2, 5, 7, 8, 9, 11, 11, 11, 14] 인 배열에서 11의 Lower Bound와 Upper Bound의 과정은 아래와 같다. Lower Bound Upper Bound Lower Bound / Upper Bound 코드 12345678910111213141516171819public static int lowerBound(int[] arr, int value) { int s = 0, m, e = arr.length-1; while(s

최소 공통 조상 알고리즘은 트리 구조에서 두 정점 a, b에서 가장 가까운 공통 조상을 찾는 알고리즘이다 위 트리에서 두 정점 (4, 7)의 LCA는 1이고, (12, 11)의 LCA는 8이다. 위 트리를 예로 들었을 때, DP를 통해 a와 b의 LCA를 구하는 방법은 다음과 같다. 1. 먼저 트리를 한번 순회하며 각 정점에 대한 깊이와 부모를 정해준다. 2. 계산된 depth의 최댓값을 가지고 각 정점에 대해 2^i 번째 조상을 저장하는 배열을 만든다. 이때, 2^i 번째 조상을 찾아가는 식은 다음과 같다. parent[i][v] = parent[i-1][parent[i-1][v]] * 이 식을 말로 풀어보면 정점 v의 2^i 번째 부모는 정점 v의 2^(i-1) 번째 부모 노드의 2^(i-1) 번째 ..

LAN(Local Area Network) : 근거리 통신망 가까운 지역을 서로 연결하는 네트워크 WAN(Wide Area Network) : 광역 통신망 더 넓은 지역을 서로 연결하는 네트워크 Ethernet : 이더넷 CSMA/CD 기술을 사용해서 통신하는 컴퓨터 네트워크 기술의 하나 CSMA/CD : Carrier Sense Multiple Access / Collision Detection 캐리어 감지 다중 접속 및 충돌 탐지 기술이다. CSMA/CD 과정 1. 네트워크를 사용하려는 호스트는 먼저 현재 네트워크 위에 흐르고 있는 데이터가 있는지 감지한다. 2. 만약 현재 다른 데이터가 전송 중이면 사용할 수 있을 때까지 기다리고 아니면 전송을 시작한다. 3. 여러 군데에서 동시에 전송을 시작해 충..

컴퓨터 네트워크 호스트들이 자원을 공유할 수 있게 하는 디지털 전기통신망 -> 장비들끼리 서로 연결해서 정보 및 자원을 공유할 수 있게 해주는 것 인터넷 : Internet 전 세계적으로 연결된 컴퓨터 네트워크 인터넷의 특징 하나의 프로토콜(TCP/IP)만을 사용한다 인트라넷 : IntraNet 단체의 직원만 접근이 가능한 사설망 (TCP/IP 프로토콜을 사용하는 폐쇄적 근거리 통신망) 엑스트라넷 : ExtraNet 인트라넷과 거의 유사하지만 단체의 직원 외에도 협력 회사나 고객에게 사용할 수 있도록 한 사설망

문제 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제해결방법 이 문제는 DP 문제로 점화식을 세워서 푸는 문제였다. 좌측 상단부터 우측 하단까지 배열을 탐색하며 해당 칸을 우측 하단으로 하는 가장 큰 정사각형의 크기를 기록한다. 예를 들어 위 그림은 배열의 값이 1인 (i, j) 칸을 탐색하는 중 (i-1, j) 칸에 5, (i-1, j-1) 칸에 6, (i, j-1) 칸에 3이 저장되어 있는 상태이다. 이때 셋 중에 가장 작은 값인 3을 선택해야 길이가 4인 가장 큰 정사각형을 만들 수 있다. (회색 점선) 위 내용을 점..

문제 www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제해결방법 이 문제는 다익스트라 알고리즘을 이용해서 풀었다. 1번 정점에서 N번 정점으로 가는 최단 거리를 D(1~N)로 표현한다면, A를 반드시 거쳐서 가는 최단 거리는 다음과 같이 표시할 수 있다. => D(1~A) + D(A~N) 이와 같이, A와 B를 반드시 거쳐서 가는 최단 거리는 아래와 같다. Min(D(1~A)+D(A~B)+D(B~N), D(1~B..

문제 programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 문제해결방법 1. 최대 2명이 탈 수 있기 때문에 가장 무거운 사람과 남은 무게에 맞춰 탈 수 있는 사람 중에 가장 무거운 사람을 태운다. 2. 남은 사람들로 위 과정을 반복하며 구명보트의 수를 세준다. 코드 12345678910111213141516171819202122232425262728293031package Programmers; pu..