다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다. 음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다. 인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다. 매커니즘 (1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디) (2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP) 예시 https://mag1c.tistory.com/451 [백준 19..
서론 Upper Bound, Lower Bound는 이진탐색을 활용한 알고리즘이다. [알고리즘] 이진탐색(이분탐색) - Binary Search Binary Search 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법 정렬되어 있어야 한다 보통 세 개의 변수를 지정해 두고 (ex : left, mid, right) 찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는 mag1c.tistory.com 백준에서 이진탐색을 활용한 문제를 풀다가, 깔끔하게 풀리지 않아서 풀고 난 뒤 다른 분들의 코드나 설명을 참조했더니, 내가 사용했던 조건들이 Upper Bound라는 것을 알게되었고, 정리하고자 포스팅을 진행한다. [백준 1654번 / JAVA] 랜선 자르기 문제 링크 https://www.acm..
서론 올해 초부터 어느정도 적당한 난이도 이상의 코딩테스트들에 응시하고 있는데, 항상 5번문제는 MST관련 문제가 나왔다. 조금만 변형되어도 풀기가 애매해질 정도로 얕은 정도로만 학습을 한 상태였기 때문에, 복기를 위해 관련된 것들을 학습하려고 한다. Union Find Disjoint Set(서로소 집합)을 관리하는 데 사용되는 알고리즘으로, 각 집합의 대표 요소를 통해 집합을 식별한다. 대표 요소를 해당 집합의 부모라고도 부르며, 루트로 표현된다. 일반적으로 작은 번호를 부모로 정하는데, 이는 트리의 높이를 최소화하여 연산의 효율성을 높일 수 있다. 여러 노드가 존재할 때, union과 find 연산을 수행한다. Union : 노드를 연결 Find : 특정 노드의 루트 노드를 찾음 예제 원소 A B ..
해시테이블 (hashtable) Key, Value 로 데이터를 저장하는 자료구조 중 하나이며 데이터를 빠르게 검색할 수 있는 자료구조이다. 빠른 검색을 할 수 있는 이유는 내부적으로 버킷(배열)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. (Key, Value)가 ("Becca", "+1 424 999 0000")인 데이터를 해시 테이블에 저장한다고 할 때, index = hash_function("Becca") % Index을 통해 Index값을 계산한 뒤, array[Index] = "+1 424 99..
Dynamic Programing 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키백과 Dynamic Programing은 1. 하위 문제로 쪼개지며, 하위 문제의 정답으로 해당 문제의 정답을 구할 수 있을 때(Optimal Substructure) 2. 하위 문제가 겹칠 때 (Overlapping Subproblem) 사용할 수 있다. Top-Bottom방식과 Bottom-Up방식이 있는데 이름에서 알 수 있다시피 위에서아래로, 아래에서 위로 가는 방식인 것 같다. Top-Bottom은 재귀를 통해 메인 문제에서 작은 문제들로 쪼개어가는 과정이고 Bo..
틀린 부분이 있으면 지적해주시면 감사하겠습니다. 공부하는데 큰 도움이 됩니다. OSI 7계층 OSI 7 계층이란? 네트워크 프로토콜이 통신하는 구조를 7개의 계층으로 분리하여 각 계층간 상호 작동하는 방식을 정해놓은 ISO(국제 표준화기구)에서 개발한 모델이다. 쉽게 말해 통신이 일어나는 과정을 7단계로 나눈 것이다. 계층을 나눈 이유 통신이 일어나는 과정을 단계별로 파악하기 쉽고, 흐름을 한눈에 알아보기 쉽고, 사람들이 이해하기 쉬우며 계층 중에 특정한 곳에 문제가 생기면 다른 단계의 장비 및 소프트웨어를 건들지 않고도 해당 문제가 생긴 계층만 고칠 수 있다. 데이터 캡슐화 사용자 데이터가 각 계층을 지나면서 하위 계층은 상위 계층으로부터 온 정보를 데이터로 취급하며, 자신의 계층 특성을 담은 제어정보..
틀린 부분이 있다면 지적해주시면 감사하겠습니다. 공부하는데 큰 도움이 됩니다. TCP / IP (Transmission Control Protocol / Internet Protocol) 흔히 TCP/IP라고 알려진 인터넷 프로토콜 스위트(Internet Protocol Suite)는 인터넷과 이와 유사한 컴퓨터 네트워크 사이에서 정보를 주고받는 데 이용되는 통신 프로토콜의 모음이다. 인터넷 프로토콜 슈트 중 TCP와 IP가 가장 많이 쓰이기 때문에 TCP/IP 프로토콜 슈트라고도 한다. TCP/IP는 네트워크 프로토콜 스위트로, 온라인 상의 안전하고 효율적인 데이터 전송의 필수 요건을 정의한다. 패킷 통신 방식의 인터넷 프로토콜인 IP와 전송 조절 프로토콜인 TCP로 이루어져 있다. IP 주소 체계를 ..
틀린 부분이 있다면 지적해주시면 감사하겠습니다. 공부하는 데 큰 도움이 됩니다. WEB과 HTTP / (특징, 구조, 동작 과정 예시)틀린 부분이 있다면 지적해 주시면 감사하겠습니다. 공부에 많은 도움이 됩니다. WEB (World Wide Web) 웹 = 인터넷? 인터넷이라는 거대한 네트워크 위에서 다양한 서비스들이 동작하는데, 웹도 인터mag1c.tistory.com HTTP는 TCP와 UDP방식이 있다. 그렇다면 TCP와 UDP는 무엇이며 어떤 차이가 있을까. TCP (Transmission Control Protocol)TCP는 연결 지향적인 프로토콜로 장치들 사이에서 논리적인 접속을 성립하기 위해 연결을 설정해 신뢰성을 보장하는 연결형 서비스이다.연결 지향적 프로토콜클라이언트와 서버가 연..