본문 바로가기

전체 글

 (76)
[ALGORITHM] 그래프 탐색(DFS, BFS) 그래프 그래프 자료구조는 각 노드들 간의 관계를 표현하는 그래프로 지금까지 배웠던 리스트, 스택, 큐 등 선형구조가 아닌 비선형 구조이다. 그래프의 구조 그래프는 여러 특성을 가지는 vertex(정점)과 정점들간의 관계를 의미하는 edge(간선)으로 이루어져 있다. 그래프의 종류 무방향 그래프(undirected graph) : 간선에 방향이 없다. 즉 양방향 방향 그래프(directed graph) : 간선에 방향이 있다. 즉 단방향 가중치 그래프: 거리나 비용등으로 표현될수 있는 가중치가 간선에 포함되어 있다. 그래프 탐색 방법 DFS(깊이 우선 탐색) : Depth-First Search의 약자로 인접한 노드를 따라 탐색하고 더이상 자식 노드가 존재하지 않으면 다음 자식 노드가 존재하는 곳부터 탐색..
[ALGORITHM] 연결리스트, 스택, 큐, 해시 테이블 연결리스트(Linked List) 연결리스트는 인덱스를 통해 빠른 접근은 가능하지만 크기가 불변인 배열의 단점을 보완하기 위해 생긴 자료구조이다. 기본적으로 파이썬은 리스트가 이 연결리스트의 기능들을 지원한다. Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있다. Pointer : 각 노드에서 다음 데이터를 가리키는 주소값을 가지고 있다. Head : 연결리스트에서 가장 시작점인 데이터를 의미한다. Tail : 연결리스트에서 가장 마지막 데이터를 의미한다. Next = None(Null) : 다음 데이터가 없을 경우 포인터의 주소값은 None(Null)이다. 연결리스트는 필요한 데이터를 찾을때 시작점(head)부터 pointer를 따라 해당 데이터를 찾기 때문에 O(n)의 시간 복..
[CS] 1의 보수법과 2의 보수법 사람과 사람의 의사소통 하기 위해서는 그들이 사용하는 언어가 같아야하듯 프로그래머가 컴퓨터와 의사소통하기 위해서는 컴퓨터가 사용하는 언어를 알아야합니다. 한글은 24자의 자음과 모음이 영어는 26개의 알파벳이 있어 이들의 조합으로 무수히 많은 조합을 만들어 낼수 있지만 컴퓨터는 0과 1만을 사용해 정수의 부호와 크기를 표현해야 하기 때문에 비효율적인 방법으로 조합을 짜면 비용이 낭비 됩니다. 컴퓨터의 언어로 정수를 효율적으로 표현하기 위해서는 보수라는 개념을 먼저 알고가야 합니다. 보수란, '두 수의 합이 진법의 밑수(N)가 되게 하는 수'를 말합니다. 예를 들어 10진수 4의 10의 보수는 6이고, 10진수 2의 10의 보수는 8입니다. 보수는 컴퓨터에서 음의 정수를 표현하기 위해서 고안되었습니다. 1..
[ALGORITHM] 최단경로(다익스트라, 플로이드와샬) 최단경로 노드간 이동할 때 가중치가 1인 경우에는 BFS(너비 우선 탐색)를 이용해 쉽게 최단거리를 구할 수 있었습니다. 그렇다면 가중치가 1이 아닌 경우에는 어떻게 풀어야 할까요? 이때는 BFS가 아닌 Dijkstra(다익스트라)와 Floyd-warshall(플로이드-와샬) 탐색 기법을 이용해 문제를 풀 수 있습니다. 가중치가 음수일 경우 이용할 수 있는 Bellman Ford(벨만 포드) 기법도 있지만 이 글에서는 우선 다익스트라와 플로이드-와샬에 대해서만 배워 보겠습니다. 다익스트라(Dijkstra) 다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단거리를 구해주는 알고리즘입니다. 다익스트라의 기본 개념은 출발 지점에서 부터 방문하지 ..

티스토리툴바