서로소 집합

서로소 집합(Disjoint Sets) 서로소 집합(Disjoint Sets)은 공통 원소가 없는 두 집합을 의미한다. 예를 들면 {1, 2}와 {3, 4} 가 서로소 집합에 해당된다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union 과 find 이 2개의 연산으로 조작할 수 있다. union(합집합) 연산 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find(찾기) 연산 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합집합과 찾기 연산으로 이루어져 있다. 따라서 union-find 자료구조라고도 한다. 서로소 집합 자료구조 서로소 집합 자료구조를 구현할 때는 트..

플로이드 워셜 알고리즘

플로이드 워셜(Floyd Warshall) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용할 수 있는 경우이다. 다익스트라 알고리즘에서는 한 지점에서 다른 모든 지점까지의 최단거리인 반면, 플로이드 워셜은 모든 지점 to 모드 지점인 것이다. 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다. 노드의 개수가 N 개일 때 알고리즘상으로 N 번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 총 시간 복잡도는 O(N^3)이다. 플로이드 워셜 알고리즘을 사용해야 하는지에 대한 판단 기준 가중치 방향 그래프가 주어진다. A -> K ->..

템플릿 메서드 패턴

템플릿 메서드 패턴(Template Method Pattern) 템플릿(Template) 이라는 단어에서 알 수 있듯이, 템플릿 메서드 패턴은 어떤 작업 알고리즘의 골격을 정의한다. 공통 기능과 세부기능을 갖도록 구현할 수 있으며, 세부 기능은 서브 클래스마다 달라질 수있다. 즉, 템플릿 메서드를 이용하면 알고리즘의 구조를 그대로 유지하면서 특정 단계만 서브 클래스에서 새로 정의하도록 할 수 있다. 생성 단계 상위 클래스(알고리즘 골격)를 캡슐화 한다. 서로 공통점이 있는 메서드를 일반화 하여 새로 만든다. 어떤 알고리즘에 대한 템플릿 역할을 메서드가 한다. 서브클래스에서 특정 알고리즘에 선택적으로 적용되야 하는 경우에는 후크(hook) 를 사용한다. AI Seller 지금으로부터 5년뒤, 높은 임금 문..

웹의 동작 방식(How Does The Web Work?)

How Does The Web Work? 본 게시글은 원작자(Chuck choi) 께 원문 How Does The Web Work ? 게시글 번역 허락을 구하고 작성한 글입니다. 번역 과정에서 원문 내용에 대한 첨삭이 일어났으므로 원문 내용과 다른 부분이 있을 수 있습니다. 또한, 본 게시글에 사용된 이미지의 사용 권한은 원작자에게 있습니다. 제 이전 Medium Blog 에서 작성된 내용을 옮겼습니다. 웹은 어떻게 동작할까? 자동차, 텔레비전, 난로, 냉장고는 우리가 매일 사용하는 기계로 사용이 상당히 간편합니다. 이것들은 우리 삶의 필수적인 도구입니다. 하지만, 우리는 그것들이 어떻게 작동하는지 완전히 이해하지 못하더라도 문제되지 않으며 그것들을 사용하기 위해 메커니즘을 이해할 필요가 없습니다. 컴퓨..

최단 경로와 다익스트라 알고리즘

최단 경로(Shortest Path) 최단 경로(Shortest Path)는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 길 찾기 문제라고도 불린다. 아래 세 개의 알고리즘이 주로 사용된다. 다익스트라 알고리즘(Dijkstra Algorithm) 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 벨만 포드 알고리즘(Bellman-Ford's algorithm) 최단 경로 문제의 특징은 다음과 같다. 도로, 길찾기 문제 도로(길)와 가중치(값, 시간 등)가 주어지는 경우 Ex. A 위치에서 K 를 거쳐 X 로 도착하려고하는 경우에는 플로이드 워셜 알고리즘 사용. (즉, 어디를 거쳐간다고하면 플로이드 워셜 알고리즘일 가능성이 높음) 최단 경로의 문제는 대부분 가중치 방향 그래프..

다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming) 동적 계획법을 듣기전에 재귀와 메모이제이션에 대한 이해가 먼저 필요하다. 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이 있는데 대표적인 방법에 동적 계획법(Dynamic Programming)이 있다. 다이나믹 프로그래밍 방식은 TopDown and BottomUp 두 가지가 있으며 메모이제이션 기법을 자주 사용한다. Memoization : 메모리를 더 많이 사용하여 시간 복잡도를 줄이는 방법 다이나믹 프로그래밍으로 해결할 수있는 대표적인 예시가 피보나치 수열이다. 재귀에서 배웠듯이 재귀를 사용하려면 점화식을 작성해보는 것이 좋다. 피보나치 수열에 대한 점화식은 다음과 같다. $$ n > 2 ? f(n) = f(n-2)..

프로세스 동기화

프로세스 동기화 프로세스 동기화(Process synchronization)란 프로세스 사이에 동기화를 하는 것을 말한다. 현재는 대부분 쓰레드 기준으로 문맥 교환(Context Switching) 이 일어나기 때문에 쓰레드 동기화(Thread synchronization)라고도 불린다. 프로세스 동기화는 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것이다. 그럼 동기화(Synchronization)는 공유 자원의 일관성을 유지하는 것으로 볼 수 있다. 프로세스 동기화에 대한 시작은 경쟁 상태(Race Condition)와 임계 구역(Critical Section)에 대한 이해부터 시작된다. 경쟁 상태(Race Condition) 경쟁 상태(Race Condition)란 동시에 여러 개의 프로세스 ..

Interrupt 와 Context Switching

Interrupt 와 Context Switching System call 운영체제는 커널 모드와 사용자 모드로 나뉘어 구동된다. 운영체제에서 프로그램이 구동되는데 있어 파일을 읽어 오거나, 파일을 쓰거나, 혹은 화면에 메시지를 출력하는 등 많은 부분이 커널 모드를 사용한다. 시스템 콜은 이러한 커널 영역의 기능을 사용자 모드가 사용 가능하게, 즉 프로세스가 하드웨어에 직접 접근해서 필요한 기능을 사용할 수 있게 해준다. 시스템 콜은 프로세스 제어, 파일 조작, 장치 조작, 정보 유지보수, 통신과 보호 이렇게 다섯 가지 유형으로 나눌 수 있다. Interrupt 인터럽트는 CPU 가 프로그램을 실행하고 있을 때, I/O 장치 등에 의해 예외 상황이 발생하여 처리가 필요한 경우에 CPU 에게 처리하도록 알..