프로그래밍/개념원리

개요 연결 리스트란 요소를 차례차례 연결시켜서 만든 리스트형 자료구조다. 배열 리스트(ArrayList)와 다른 점은, 연결 리스트는 구현에 배열을 사용하지 않았다는 것이다. 연결 리스트에서 요소를 삽입하면, 배열의 특정 위치에 요소를 저장하는 대신 노드(Node)라는 곳에 저장한다. 이 노드라는 것은 마치 열차 칸과 같은데, 자신의 이전, 다음 순번을 가리키는 연결고리(Link)를 같이 가지고 있어서 마지 쇠사슬을 엮는 듯이 서로 얽히는 구조를 띄도록 만든다. 이런 특수한 구조로 인해 다음과 같은 특징을 가진다. 특징 배열 리스트에 비해 삽입과 삭제가 빠르다 배열 리스트는 배열의 크기가 수시로 변하는 것처럼 보이지만, 사실 내부에서는 고정된 배열에 요소를 삽입/삭제하고 있다. 그러다가 요소가 배열의 크..

개요 해시맵이란 자료를 키-값(key-value)의 형태로 저장하는 자료구조이다. 여기서 키-값의 쌍을 보유한 객체를 엔트리(Entry)라고 부른다. 백과사전을 떠올리면 쉽다. 단어 부분이 키이고, 설명 부분이 값이라고 보면 된다. 실제로 C#에는 딕셔너리라는, 꽤 비슷한 클래스를 제공한다! (해시맵이랑은 구현이 전혀 다르지만) 특징 키는 중복을 허용하지 않지만, 값은 중복을 허용한다. 해시맵에서 키를 저장하는 공간은 해시 테이블(HashTable)을 기반으로 구성된다. 해시 테이블이란 객체가 가진 값을 기반으로 고유한 해시코드(int)을 도출해내는 해시 함수를 사용하는 자료구조인데, 이 함수를 사용하면 모든 키를 고유한 장소에 저장할 수 있게 된다. Set 자료구조처럼 중복을 허용하지 않는 이유이기도 ..

개요 배열(Array)이란 프로그래밍 하는 사람이면 모르는 사람이 없을 자료구조이다. 동일한 타입의 요소들을 연속된 메모리 공간에 순서대로 저장한 것을 배열이라고 한다. 칸이 여러 개 달린 서랍장을 생각하면 좋다. 특징 크기가 고정되어 있다. 항상 처음에 선언했던 크기를 가진다. 중간에 늘리거나 줄일 수 없는데, 그 이유는 배열이 만들어질 때 [입력한 타입의 크기*배열 길이] 만큼의 용량을 통짜로 확보하기 때문이다. 4byte짜리 int가 10개 들어가는 배열을 생성하면 그 배열은 총 40byte의 길이를 가지게 된다. 여기서 크기를 늘려버리면 다른 변수가 차지하고 있는 공간을 침범하게 될 수 있다는 문제가 생긴다. 그렇기에 배열의 크기를 조정하려면 새로 만드는 수밖에 없다. 원하는 위치의 요소로 쉽게 ..

개요 큐란 대표적인 선입선출(First In First Out, FIFO)형 자료구조이다. 선입선출이란 먼저 들어온 것이 먼저 나간다는 것을 뜻한다. 데이터를 반드시 입력한 순서대로 처리해야 할 때 큐를 사용한다. 보통은 데이터를... 순서대로 처리하므로... 큐는 정말 다양한 상황에서 쓸 수 있다. 주요 메소드 기본적으로 다음과 같은 기능을 가진다. Enqueue() 큐에 데이터를 추가하는 것을 의미한다. 데이터는 항상 큐의 마지막 위치에 추가된다. 항상 마지막 위치에 추가되므로, 복잡한 연산이 필요없다. 따라서 항상 O(1)의 시간복잡도를 가진다. Dequeue() 큐에서 데이터를 꺼내는 것을 의미한다. 데이터는 항상 큐의 첫번째 위치에서 꺼낸다. (스택처럼 마지막 위치에서 꺼내지 않는다!) Enqu..

개요 스택이란 대표적인 후입선출(Last In First Out, LIFO)형 자료구조이다. 후입선출이란 나중에 들어온 것이 먼저 나간다는 것을 뜻한다. 스택은 데이터를 입력한 순서대로가 아닌, 반대의 순서로 처리해야 할 때 사용된다. 마치 반복문 안의 반복문 안의 반복문에서 가장 나중에 쓴 반복문이 먼저 돌아가듯 스택이 그렇다. 프링글스를 먹을 때처럼, 가장 나중에 있는 것부터 역순으로 데이터를 취하게 되는 것이다. 주요 메소드 기본적으로 다음과 같은 기능을 가진다. Push() 스택에 데이터를 추가하는 것을 의미한다. 데이터는 항상 스택의 마지막 위치에 추가된다. 항상 마지막 위치에 추가되므로, 복잡한 연산이 필요없다. 따라서 항상 O(1)의 시간복잡도를 가진다. Pop() 스택에서 데이터를 꺼내는 ..

개요 특정 조건에 맞는 원소들의 모임을 집합(Set)이라고 한다. 자바에서 사용되는 컬렉션 클래스인 Set이 이 뜻이다. 표현법 원소나열법 A = {1, 2, 3, 4, 5}, B = {2, 4, 6, 8, 10} 처럼 줄줄이 나열하는 것. 조건제시법 A = {A | A는 정수, 1