이번에 알아볼 것은 굉장히 유명한 자료구조 삼대장들인 스택(Stack), 큐(Queue), 데크(Deque) 입니다. 스택 (Stack) 스택은 자료구조의 맨 위에서만 삽입과 삭제가 일어나는 자료구조 입니다. 포인터가 맨 위를 가르키고 있어, 데이터의 가장 위에서만 삽입과 삭제가 일어나지요. 가장 나중에 들어간 원소가 가장 빨리 나오는 LIFO(Last in - First out) 구조 입니다. PUSH를 통해 원소를 삽입, POP을 통해 원소를 꺼냅니다. 이는 쌓아놓은 접시와 비슷합니다. 접시를 쌓을 때는 보통 가장 윗 접시부터 꺼내 쓰곤하죠? 컨트롤 + z를 눌러 뒤로가기를 하는 것도, 브라우저의 뒤로가기도 스택의 예시 중 하나입니다. 자바의 Stack 클래스 출력 : 10, 10, 5, 3 자바에서..

이번에 알아볼 것은 그래프 탐색의 대표적인 방법인 그래프의 표현 방법인 인접 리스트와 인접 행렬입니다. 그래프와 트리에 관한 내용은 이전 포스팅을 참고해주세요. https://uknowblog.tistory.com/357 [자료구조] 그래프(Graph)와 트리(Tree) - 점과 선의 예술 그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어 uknowblog.tistory.com 그래프의 연결 표현 : 인접 배열과 인접 리스트 그래프의 연결을 표현하는 방법에는 인접 배열과 인접 리스트가 있습니다. 이름처럼 배열을 썼느냐, 리스트를 썼느냐의 차..

그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어진 형태입니다. 그래프의 시초 위 두 개의 그림은 다들 수학시간때 한 번씩 본 그림일텐데요. '쾨니히스베르크 다리 건너기' 문제입니다. 쾨니히스베르크(현 러시아 칼리닌그라드) 중앙에는 섬이 있는데, 7개의 다리를 단 한 번씩만 모두 건널 수 있느냐? 라는 문제입니다. 이걸 단순화 시킨게 아래의 그림인데, 각 육지를 점, 다리를 선으로 나타낸 것이 그래프의 시초 중 하나라고 추측되고 있습니다. 참고로 위 문제는 '한 번씩 모두 건널 수 없다'라는 것이 수학적으로 증명되었으며, 자세한 내용은 오일..

분리집합? 분리집합이란 서로소 집합이라고도 불립니다. 이름에서도 알 수 있듯, 각각의 집합이 공통 원소를 가지지 않는 집합입니다. 즉 전체 집합 U에 두 개의 집합 A, B가 있을 때 A ∩ B = Ø 가 성립됩니다,. 이는 집합이 두 개가 아닌 세 개 이상이여도 마찬가지로, 각각의 집합이 공통원소를 가지지 않습니다. Union - Find 이러한 분리집합의 구현과 연산은 Union - Find로 이루어집니다. 말 그대로, Union(병합), Find(찾기) 인데요. 두 개의 트리셋 A와 B가 있다고 합시다. A와 B의 자식노드들은 모두 루트(최상위 노드)를 가리키고 있습니다. 그렇다면, 이 트리 두개를 병합하려면 어떻게 해야 할까요? 바로 B의 루트가 A의 루트를 가리키게 하면 됩니다. 각 트리셋의 자..