백준/알고리즘 이론정리 4

[알고리즘 이론] 연결 리스트(Linked List)

연결 리스트(Linked List) 배열과같이 연속적인 메모리 위치에 저장되지 않고 포인터를 사용하여 연결하는 선형 데이터 구조이다. 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성이 된다. Linked List(연결 리스트)를 사용하는 이유? 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 (1) 배열의 크기가 고정되어 있어서 미리 요소의 수에 대해 할당을 받아야 하는 문제와 (2) 새로운 요소를 삽입하는 것이 비효율적(비용이 많이 듬)이다. 공간을 만들고, 기존 요소를 전부 이동하는.. Linked List는 언제든지 붙이고 뗄수있는 동적 크기를 갖고, 삽입/삭제가 용이하다는 장점을 갖는다. Linked List는 임의로 액세스를 허용할 수 없다는 단점이 있다...

[알고리즘 이론] 큐(Queue)

큐(Queue) 큐(Queue)는 스택(Stack)과 반대의 개념을 갖고 있다. 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 특성을 띄고있는데 큐는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In First-Out) 특성을 띈다. Ex> 매표소에서 표를 사는경우, 가장 먼저온 손님이 먼저 구매하게 된다. Ex> 보통 컴퓨터와 주변기기 사이에는 항상 큐가 존재한다. 그 이유는 컴퓨터의 CPU와 주변기기 사이에는 속도 차이가 있기 때문에 CPU를 효율적으로 사용하기 위하여 큐를 사용해야한다. 선입선출(FIFO: First-In First-Out) : 먼저 들어온 데이터가 먼저 나가는 구조이다. 큐는 뒤(Back,Rear)에서 새로운 데이터가 추가되고 앞(Front)에서 데..

[알고리즘 이론] 스택(Stack)

스택이란? 스택(stack)은 컴퓨터에서 믿을 수 없을 정도로 많이 사용되는 자료구조이다. 창고에 쌓여있는 상자나 책 등을 생각하면 스택을 이해하기가 더 쉽다. 아래서 부터 A,B,C,D 순으로 쌓여있는 상자에서 B의 상자를 꺼내고 싶다면 D -> C -> B 순으로 상자를 건드리면서 꺼내야한다. Ex> 스마트폰에서 '뒤로가기' 키를 누르면 현재 수행되는 앱이 종료되고, 이전에 수행되던 앱이 다시 나타난다. Ex> 컴퓨터 안에서는 수 많은 함수 호출이 이루어지고, 이러한 함수는 실행이 끝나면 자신을 호출한 장소로 되돌아가야한다. 이때 스택이 사용된다. 즉, 스택은 복귀할 주소를 기억하는데 사용된다. Ex> 컴파일러안에 괄호 사용의 오류를 검사하는데에도 쓰인다. 괄호는 대괄호[], 중괄호{}, 소괄호() ..

[필수알고리즘, python] 연결 리스트(Linked list)

필수알고리즘 연결 리스트(Linked list) 알고리즘 설명 연결리스트는 알고리즘과 자료구조 중에서 가장 기본이 되며, 가장 많이 사용되는 알고리즘에 속한다. 연결리스트에는 기본적으로 노드(Node)와 링크(Link)라는 용어를 사용하게 되는데, 각각의 노드(Node)들은 내부에 1. data 2. 연결된 노드의 정보인 링크(Link)를 가지고 있다. 왜 배열을 사용하지 않고, 연결리스트를 사용할까? 연결리스트의 장점은 곧 배열의 단점이다. 배열은 동일한 자료형을 갖는 데이터의 집합이며 배열을 생성할 때 한번에 총 메모리를 확보하여 사용할 수 있도록 하기 때문에 프로그램이 실행되는 중간에 배열의 크기를 바꾸거나 할 수가 없다. 따라서 배열의 단점은 배열안에 저장되어 있는 값들을 정렬할 때도 일일이 메모..