문제 난이도GOLD III (문제 링크)  풀이 [알고리즘] 벨만-포드(Bellman-Ford) 알고리즘벨만-포드 알고리즘은 그래프의 최단 경로를 구하는 알고리즘의 하나로, 다익스트라로 해결하지 못하는 음의 간선이 포함된 문제를 효과적으로 해결할 수 있는 알고리즘이다.  [알고리즘] 다mag1c.tistory.com 포스팅에서 학습했기 때문에 자세한 설명은 생략하고, 풀었던 방법만 나열해보고자 한다. 벨만-포드 알고리즘은 특정 출발점에서 모든 노드로의 최단 경로를 탐색하는 알고리즘이다. 또한 음수 사이클을 검출할 수 있다. 도달할 수 없는 노드를 표시하기 위해 INF에 가까운 값들로 초기화해서 사용할 수 있다.  첫번째 방법문제에서, 특정 노드를 언급하지 않았다. 한 노드에서 출발하여~~~이기 때문에, ..

벨만-포드 알고리즘은 그래프의 최단 경로를 구하는 알고리즘의 하나로, 다익스트라로 해결하지 못하는 음의 간선이 포함된 문제를 효과적으로 해결할 수 있는 알고리즘이다.  [알고리즘] 다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로,mag1c.tistory.com   다익스트라 vs 벨만-포드백준 웜홀 문제의 2번 예시로 그래프를 그려보았다. 우리가 눈으로 보았을 때, 실제 1에서 1까지의 최단경로는 0이 아니라 한 바퀴를 돌았을 때, 무한히 -2의 가중치를 계속해서 더하는 경로이다. 1에서 3의 최단경로 또한 1에서 3까지의 ..

문제 난이도GOLD II (문제 링크)   풀이두 노드 간의 최장 경로인 트리의 지름을 구하는 문제이다. 모든 경우의 수를 구해서, 가장 큰 값을 찾아야하기 때문에 DFS에 적합하다. DFS 구현은 단순하니 이를 통해 문제를 쉽게 해결할 수 있다.//dfs 호출부int max = 0;for (int i = 1; i     메모리 초과는 단순 이차원 배열을 통해 각 노드의 경우의 수를 계산했기 때문에 발생했다.이는 리스트로 구현하여 해결하였다.  하지만, 모든 경우의 수를 구하면 시간 초과가 발생하는데, 모든 경우의 수를 구하게 되면 O(V^2)이 되며, 문제 조건에서 V가 100,000까지이기 때문에 최적화할 수 있는 방법이 필요하다. 임의의 노드 x에서 최장 경로 노드를 DFS를 통해 구했고, 이를 y..

네트워크를 부분적으로 공부한 후 간결하게 정리하였습니다.개선점들을 알려주신다면 적극 반영하겠습니다.(개발 입문 시 간단히 공부했던 TCP / UDP에 대해 재정리했습니다.)   TCP (Transmission Control Protocol)TCP(전송 제어 프로토콜)은 IP의 핵심 프로토콜 중 하나로, OSI 4계층인 전송 계층에 위치하는 프로토콜이다.  IP 네트워크에서의 데이터 통신은 데이터 전송의 불확실성, 데이터 손실, 라우팅 과정에서의 패킷 손실 등이 있는데, 이는 우편을 받기까지의 과정을 생각해본다면 쉽게 이해할 수 있다.  편지가 우체국에서 분류될 때, 실수로 잘못된 주소로 보내지거나 운송 중 분실될 수 있다. 이는 IP 네트워크에서 패킷이 전송 중에 손실되거나, 네트워크 경로를 이탈하여 수..

문제 난이도GOLD III  문제 링크https://www.acmicpc.net/problem/1238   풀이 [알고리즘] 다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 알고리즘그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로,mag1c.tistory.com 위의 다익스트라 알고리즘을 사용해서 구현한 문제이다.    문제 예시를 그림으로 표현해보았다.목적지로의 최단거리만 구하면 됐던 기본적인 다익스트라 알고리즘 구현 문제에서, 반대로 2에서 각 노드의 최단 경로를 한번 더 구해주기만 하면 된다. (A -> X, X -> A) private static int[] dijkstra..

네트워크를 부분적으로 공부한 후 간결하게 정리하였습니다.개선점들을 알려주신다면 적극 반영하겠습니다.   IP(Internet Protocol)인터넷을 통해 데이터를 주고받을 때 사용되는 통신규약으로 네트워크 계층에 위치하는 프로토콜이다.인터넷에 연결된 모든 장치들을 식별할 수 있도록 각각의 장비에 부여되는 고유 주소이다.    IPv6는 128비트로 구성된 IP주소로, 8개의 4자리 16진수로 이루어져있으며, 콜론으로 구분된다.1234:0ae3:85a3:0000:0000:2f3a:0370:7334   구조 아이피는 네트워크 ID와 호스트 ID로 구성되어 있으며 위의 IP주소 예시에서의 네트워크 ID와 호스트 ID는 다음과 같다     IP 클래스 네트워크 ID는, 어떤 네트워크인지 식별하며, 호스트 ID..

네트워크를 부분적으로 공부한 후 간결하게 정리하였습니다.틀린 정보 혹은 보기에 불편한 점을 알려주신다면 적극 반영하겠습니다.   LAN Local Area Network의 이름에서 알 수 있듯이, 소규모 통신망을 말한다.     HUB근거리 통신에서, 컴퓨터 간의 소통을 위한 연결장치  허브의 단점데이터 전송 시 연결된 모든 컴퓨터에 데이터를 전송하며(그림 1)이미 누군가가 통신망을 사용중이라면 충돌 문제(Collision)가 발생한다.(그림 2)     허브의 단점 개선Collision문제를 CSMA/CD 프로토콜을 사용해 해결하고자 했다.CSMA/CD (Carrier Sense Multiple Access/Collision Detection:: 반송파 감지 다중 접속/충돌 감지)쉽게 말해, 데이터 전..

LCSLongest Common Subsequence는 최장 공통 부분 문자열로, Substring의 값을 구하는 것이 아니라연속되지 않은 부분 문자열 중 가장 긴 공통 문자열을 찾는 알고리즘이다. 반대로, Longest Common Substring은 비슷하지만 부분 문자열이 아닌, substring이 되는 문자열이다. 예를들어 ABCDEF, BCDFQQ라는 문자열이 주어지면Longest Common Subsequence는 BCDF가 되고Longest Common Substring은 BCD가 된다.  LCS의 길이를 구할 때는 DP(Dynamic Programming)를 통해 메모제이션으로 효율적인 문제 해결이 가능하다.   점화식char[] w1 = word1.toCharArray();char[] w..