Concept 기존 dp 메모이제이션을 활용한 LIS에서 시간복잡도를 줄이기 위해 이분탐색을 활용 기존 LIS에서 앞쪽 수열을 보고 큰 값을 찾고 값을 갱신하는데 드는 시간인 O(N)을 줄일 수 없을까에서 비롯된 방식 사전지식으로 LowerBound 이분탐색에 대한 이해와 O(N^2)방식의 이해가 요구. Feature 시간복잡도의 경우 모든 원소를 탐색하는 시간 O(N)에 대해 이분탐색 O(NlogN)을 수행함으로 총 O(N * NlogN)이므로 O(NlogN)의 시간으로 최장 증가 수열을 구할 수 있음. Implement 1. 각각의 원소 i에 대해서 현재 기록된 lis배열의 끝 인덱스와 비교하여 i가 더 크다면 뒤에 추가 2. i가 더 작을 경우 이분탐색을 통해 해당 원소가 들어갈 수 있는 자리를 탐..

문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 풀이 DP Knapsack 문제 접근법 전형적인 Knapsack문제라 처음 배열의 행을 최대 BYTE 수인 10,000,000으로 두고 풀이하려함. 하지만 시간복잡도가 N이 최대 100이라 O(NM)이면 1억을 넘기 때문에 시간초과가 나기에 포기. 두번째로는 1차원 dp배열의 값을 최대 비용으로 두고 접근. 해당 문제에서 앱은 최대 100개, 비용은 각 앱 당 최대 100까지 나오기 때문에 최대 1..

문제 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net 풀이 부분집합으로 풀이가 가능한 문제 DP Knapsack으로 접근해봤던 문제임 접근법 Knapsack으로 풀어보자고 권유를 받아 DP 상향식으로 접근 세준이의 최대체력은 100으로 각 체력을 행으로 주어지는 사람을 열로 2차원 dp배열을 초기화 각 j번째 사람에 대해 hp[j]가 현재 체력 i보다 낮을 경우 이전 부분문제의 해와 비교하여 최대값을 갱신 누적값이 필요하기 때문에 체력 i보다..

문제 https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이 모든 정점으로부터 다른 모든 정점까지의 거리를 구하는 문제로써 플로이드 워셜 풀이가 가능 하지만 나는 데이크스트라로 풀이함 최초 접근 주어지는 K개의 노드를 출발점으로 하여금 데이크스트라를 수행하면서 전역 dp배열에 최대 비용을 기록 후 갈 수 있는 노드들에 대해 탐색하여 왕복시간을 구하려함. 하지만 이렇게 풀이하게 될 경우 왕복시간을 구할수가 없기 때문에 잘못된 풀이. 접근법 주어지는 K로부터 모든 노드에 대해 왕복시간을 구하고 모두..

문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 역 인접리스트를 활용한 데이크스트라 문제 첫번째 접근법 소프티어 8차를 보고난 후 1번문제와 비슷하다 판단하여 그리디하게 접근함… 각 면접장마다 i번째 면접장소를 end로 잡고 각 정점으로부터 i번째 면접장까지의 최단거리를 구함 두번째 접근법 제일 처음 떠올렸던 접근인데 각 면접장으로부터 다른 정점들까지의 최단경로를 구함으로써 한번..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 DP를 활용한 완전탐색 첫번째 접근법 (BFS) 각 격자별로 BFS를 수행하면서 DP 메모이제이션을 수행. 다음 탐색좌표에 대한 최장길이 DP값이 있다면 해당 부분문제 해를 이용하여 현재 최장길이를 구하는 식으로 풀이. 두번째 접근법 (DFS) 첫번째 접근에서 메모리초과가 발생하여 DFS로 변경 로직자체는 동일 각 좌표마다 DFS를 수행하면서 다음 나아가는 좌표에 대해 메모이..

본 포스팅은 네트워크 스터디를 기반으로 개인 정리를 위한 포스팅입니다. 잘못된 부분이 있다면 언제든 지적해주시면 감사하겠습니다! APR 프로토콜 ARP 프로토콜은 같은 네트워크 대역에서 통신을 하기위해 필요한 MAC주소를 IP주소를 이용해서 알아오는 프로토콜 IP 주소는 단순히 L3에서 단대단 연결을 위한 주소이고 실질적인 데이터 이동은 MAC 주소를 사용하는 L2단을 거쳐야 한다. 여기서 IP 주소와 MAC 주소를 이어 주는 역할을 하는 프로토콜이 바로 ARP 같은 네트워크 대역에서 통신을 한다고 하더라도 데이터를 보내기 위해서는 7계층부터 캡슐화를 통해 데이터를 보내기 때문에 IP주소와 MAC주소가 모두 필요함 이 때 IP주소는 알고 MAC주소는 모르더라도 ARP를 통해 통신이 가능 ARP가 중요하게..

본 포스팅은 네트워크 스터디를 기반으로 개인 정리를 위한 포스팅입니다. 잘못된 부분이 있다면 언제든 지적해주시면 감사하겠습니다! 이번 시간에는 가까이 있는 컴퓨터끼리 데이터를 주고받는 방법에 대해서 알아볼 수 있었음. 2계층에서 하는 일 2계층은 하나의 네트워크 대역 즉, 같은 네트워크 상에서 존재하는 여러 장비들 중에서 어떤 장비가 어떤 장비에게 보내는 데이터를 전달하는 역할을 수행함 추가적으로 오류제어(보내는 데이터에 오류가 있는지), 흐름제어(누가 누구에게 데이터를 보내는지) 수행함 하나의 네트워크 대역 LAN에서만 통신할 때 사용하는 계층으로 다른 네트워크와 통신할 때는 항상 3계층이 도와주어야 함 3계층의 주소, 프로토콜을 이용해야만 다른 네트워크와 통신가능. MAC ? 인터넷을 할 수 있는 기..