위상 정렬(Topology Sort)  위의 위키피디아 문서를 참조하면, 위상 정렬이란 정점의 선형 순서 지정을 통해 모든 방향 간선 uv에 대해 정점 u가 v보다 앞에 올 수 있게 정렬하기 위해 사용되는 알고리즘으로, 방향성 비순환 그래프 - DAG(Directed Acyclic Graph)에만 적용할 수 있다고 한다.     쉽게 말하자면 순서가 정해져 있는 작업을 차례로 수행해야할 때 순서를 결정해주는 알고리즘이고,더 쉽게 말하자면, 순서를 찾아주는 알고리즘이다.  특징나열한 정렬 순서만 두 가지 경우가 존재하고 추가로 여러 개의 답이 더 존재할 수 있다. 이처럼 위상 정렬은 여러 개의 답이 존재할 수 있다는 특징이 있다. 순회하는 방법이 한 가지보다 많을 수 있기 때문이다. 또한, 위에서 DAG에..

크루스칼 알고리즘 (Kruskal Algorithm)크루스칼 알고리즘(Kruskal Algorithm)이란 최소 신장 트리(Minimum Spanning Tree)를 찾기 위해 사용되는 알고리즘이다. 신장 트리(Spanning Tree)그래프 내의 모든 정점을 포함하는 트리 최소 신장 트리(Minimum Spanning Tree)신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리   최소 신장 트리를 찾기 위해 모든 간선을 가중치에 따라 오름차순으로 정렬하는 아이디어를 사용하여 효과적으로 MST를 구할 수 있게 된다.세부적인 구현 방법은 다음과 같다. 1. 모든 간선을 가중치에 따라 오름차순 정렬한다.2. 간선을 하나씩 선택하여 사이클이 생기지 않을 때 연결하여 모든 노드가 연결될 때 까지 반복한..

LIS(최장 증가 부분 수열)N크기의 배열이 주어졌을때, 배열에서 일부 원소를 조합하여 만든 부분 수열 중, 오름차순의 조건을 만족하면서 길이가 최대인 부분 수열을 말한다. 아래처럼, {3, 6, 2, 1, 7, 8, 5, 4, 9}의 배열이 있다면, LIS는 {3, 6, 7, 8, 9} 이다  DPLIS 문제는 각 요소를 포함하는 증가하는 부분 수열의 최대 길이를 찾는 문제로 이를 효율적으로 해결하기 위해 동적 계획법을 사용한다.단일 배열 내에서, 이전 인덱스의 숫자와 비교하여 증가시켜주면 되기 때문에 DP로 문제를 해결할 수 있다.단일 배열이라는 점만 제외하면 LCS와 유사한 매커니즘이기에, 점화식도 비슷한 방법으로 구현할 수 있다.   [알고리즘] LCS (Longest Common Subseque..

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

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

네트워크를 부분적으로 공부한 후 간결하게 정리하였습니다.개선점들을 알려주신다면 적극 반영하겠습니다.   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..