천천히 빛나는

그래프의 표현 그래프를 컴퓨터가 처리하게 만들기 위해서는 그래프를 적절한 자료구조로 변환해 주어야 한다. 표현 방식에는 인접행렬(adjaceny matrix)와 인접리스트(adjaceny list)가 있다. 인접 행렬 그래프 (adjaceny matrix) 모든 정보를 저장하는 방식이다. 직관적이며 쉽게 구현이 가능하지만 불필요한 정보 저장이 많다. 그래프의 크기가 커지면 메모리 초과가 발생할 수도 있다. 보통 2차원 배열을 사용하여 구현한다. 정점의 개수가 총 n개이면 인접행렬은 nxn의 크기를 갖는다. 무방향 그래픠 경우 대각선을 중심으로 대칭이며 가중치가 있을 경우 1이 아닌 가중치를 저장하게 된다. 인접 리스트 그래프 (adjaceny list) 갈 수 있는 곳만 저장하는 방식이다. 필요한 정보만..

본 포스팅에서는 그래프의 기본 용어만 다룹니다. 인접행렬 및 인접리스트 관련 내용을 원한다면 (2)를 읽어주세요. 그래프(Graph) 정점(Node/Vertex, 노드)과 간선(Edge, 엣지)으로 이루어진 자료구조이다. 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G=(V, E)라고 할 수 있다. 정점 A에서 B로 이동할 수 있는 방법을 경로(Path)라고 한다. 그래프 내에서 정점끼리의 path는 여러 개여도 된다. 또 두 정점 간 경로가 존재하지 않을 수도 있다. 정점 A에서 B로 가는 Path가 존재하면 정점 B는 정점 A로부터 reachable하다고 한다. 노드가 겹치지 않는 경로를 elementary하다고 하며 길이(length)는 엣지의 수를 나타낸다. 간선으로 연결되어 ..

17298. (오큰수) 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 두 개의 풀이 방식이 있습니다. 더 이해하기 편한 걸로 코드를 구현해보시는 걸 추천합니다 :D 개인적으로 저는 2번이 이해하기가 더 쉬웠습니다. 1) 오큰수를 찾지 못한 값들을 stack에 저장하는 경우 vector input(n); // 입력받은 값들 stack index; // 오큰수를 찾지 못한 값들 - Stack에는 오큰수를 찾지 못한 값들이 쌓일 예정이다. (정확히는 몇번째로 입력한 값인지가 쌓인다.) - 입력..

Stack에 대한 문제들을 다루는 챕터이다. Queue(큐)와 Deque(덱)은 그래프와 BFS에서 집중적으로 다룰 예정이다. https://shine-slowly.tistory.com/39 알고리즘 : 자료구조(1) 스택 (Stack) (C++로 구현) 스택 (Stack) 스택(stack)은 쌓아놓은 더미라는 의미 그대로, 책상에 쌓여있는 책을 생각하면 된다. 가장 큰 특징은 LIFO(Last In First Out-후입선출)이다. 제일 최근에 들어온 데이터가 가장 먼저 나가는 shine-slowly.tistory.com 스택을 아예 모른다면 이 글을 가볍게 읽는 것을 추천한다. c++로 스택을 구현하는 과정과 c++ stl stack을 사용하는 방법이 나와 있다. 10828. (스택) 정수를 저장하는..

리스트 (List) List는 배열과 비교하여 이와 같은 모습을 띄고 있다. 실제 값이 저장되는 데이터 필드과 주소가 저장된 링크 필드로 구현되어 있다. 리스트는 삽입, 삭제, 탐색에서 뚜렷한 차이를 보인다. 배열을 생각해보면 값을 삭제하려면 뒤에 있던 값들을 이동시켜야 한다. 하지만 리스트는 주소만 바꿔주면 된다. https://velog.io/@kon6443/Data-Structure-C-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-list [Data Structure] C++ / 자료구조 / Linked list 링크드 리스트란 배열과 비슷하게 선형적으로 연결된 자료구조이다.하지만 인접한 메모리 공간에 저장되는 배열과 다르게 링크드 리스트는 인접한 메모리 공간에 저..

스택 : 한쪽에서만 자료를 빼고 넣을 수 있다. 큐 : Front 에는 삭제가, Back 에서는 삽입이 일어난다. 덱 (Deque) 덱(deque)은 양쪽에서 삽입과 삭제가 가능하며 스택(stack)과 큐(queue)의 연산을 모두 지원한다. Double-Ended Queue라는 뜻으로 front, rear에서 모두 삽입 삭제가 가능한 큐를 생각하면 된다. enqueue : 덱에서 요소를 추가 dequeue : 덱에서 요소를 삭제 front : 덱의 맨 앞 rear : 덱의 맨 뒤 큐와 같은 용어를 쓴다. 하지만 enqueue와 dequeue가 앞과 뒤 모두에서 일어난다는 것을 잊지밀자! class Deque { private: int front; // front에 가까운 원소의 바로 앞 int rear..

큐 (Queue) 큐(queue)는 스택(stack)과 다르게 FIFO(First In First Out-선입선출)의 구조를 가지고 있다. 편의점 아르바이트를 해보신 분들은 특히 잘 아시겠지만 가장 먼저 들어온 것을 가장 앞에 배치하여 가장 먼저 나갈 수 있도록 하는 것이다. 은행의 번호표를 생각해보자. 100번째 번호표를 뽑은 상태이고 현재 손님이 많이 몰린 탓이 96번째 손님까지 서비스를 받고 있다. 그렇다면 다음 손님의 번호와 새로온 손님의 번호를 기억하기 위해서는 어떻게 해야할까? 바로 큐를 이용하면 된다. Enqueue : 큐 맨 뒤에 요소 추가 Dequeue : 큐 맨 앞에 요소 삭제 Peek : front에 위치한 데이터 (가장 일찍 들어온 요소) Front : 맨 앞의 위치 Rear : 맨..

스택 (Stack) 스택(stack)은 쌓아놓은 더미라는 의미 그대로, 책상에 쌓여있는 책을 생각하면 된다. 가장 큰 특징은 LIFO(Last In First Out-후입선출)이다. 제일 최근에 들어온 데이터가 가장 먼저 나가는 것이다. 편의점 아르바이트를 해보신 분들이 아는 선입선출과 반대되는 용어이다. 여기서 선입선출에 해당되는 자료구조는, 뒤에서 다룰 큐 (Queue)이다. 문서 편집기에서 되돌리기를 했을 때 바로 직전에 실행한 작업이 취소되는 것을 생각하면 된다. push : 스택의 top에서 데이터 삽입 pop : 스택의 top에서 데이터 삭제 stack top : 스택에서 입출력이 이루어지는 부분 element : 스택에 저장되는 것 full stack : 포화 상태의 스택 스택의 기본 용어는..