알고리즘/자료구조3 [자료구조] 스택 - Stack 스택에 대해 알아보도록 하겠습니다.스택은 자료구조에서 아주 기초이자 중요한 개념입니다. 개념부터 설명하겠습니다. 스택 개념 stack은 사전적 의미는 "쌓다" 입니다. 상자 BOX를 생각하면 쉽게 이해할 수 있습니다.박스에 책을 쌓는다고 가정하겠습니다. 책은 바닥부터 차례대로 쌓아지겠죠?? 책을 꺼내려면 어떻게 해야할까요!아마 제일 최근에 쌓은 책을 처음 꺼낼 수 있고, 맨 처음에 넣은 책은 마지막에 꺼낼 수 있을것 같습니다.그림으로 보면 아래와 같아요! 제일 먼저 넣은 데이터는 1번이고, 제일 마지막에 넣은 데이터는 4번입니다.데이터를 꺼낼때는 반대로 4번이 제일 처음 나오고 1번이 마지막으로 나올 것입니다그래서 스택을 "선입후출" , "후입선출" 의 특징을 가지고 있다고 말합니다! 어디에 쓰일까? 그.. 2017. 11. 12. 자료구조 : 연결리스트 (Linked list) 자료를 저장하는 방법 중 크게 배열과 연결리스트가 있습니다. 그럼 언제 배열을 사용하고 언제 연결리스트를 쓸까요? 먼저 두 자료구조의 장, 단점에 대해 알아보겠습니다. 표1 배열, 연결리스트 장점 및 단점 배열은 접근이 빠르고 간단합니다. n번째 인덱스에 접근할 경우 arr[n]을 사용하면 빠른 시간에 접근할 수 있습니다. 그러나 배열을 사용하기 위해서는 처음에 배열의 크기를 선언해야 하고 크기의 수정이 불가능하기 때문에 메모리 사용이 비효율적입니다. 또한 중간 데이터를 삭제 했을때 빈 배열을 처리하는 것이 번거롭습니다..( 자료구조를 공부해보신 분이라면 이해하실 겁니다ㅠ) 그러나 연결리스트는 위의 단점을 해결할 수 있습니다. 필요할때마다 데이터를 생성하여 연결하면 되기 때문에 메모리를 효율적으로 사용가.. 2017. 11. 8. 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘(Dijkstra Algorithm) 그래프 내에서 최단경로를 정하는 알고리즘은 여러가지가 있습니다. 그 중 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할 때 사용됩니다.또한 모든 간선의 가중치가 양의 가중치를 가지고 있을 때 사용할 수 있습니다. 다익스트라의 기본적인 원리는 한 정점에서 갈 수 있는 다른 정점 중, 작은 가중치 간선을 우선적으로 탐색하는 방법입니다. 현재 정점을 A라 하고, A와 연결된 가선이 B라고 가정해 봅시다. A까지 이동하는 비용을 a , B까지 이동하는 비용을 b , A에서 B로 이동할 때 발생하는 비용 x 라 할 때a+x < b 라면B까지 가는 비용을 a+x로 갱신할 수 있습니다. 아래 예제를 통해 더 자세히 알아보겠습니다. 위와 같은 .. 2017. 10. 6. 이전 1 다음 반응형
