그래프란? 그래프는 정점과 간선으로 이루어진 자료구조이다. 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수도 있다. 그런 면에서 트리는 그래프의 일종인 셈이다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활에서 다양한 예를 그래프로 표현할 수 있다. 대표적으로 지하철 노선도, 도심의 도로 등이 있다. 이런 식으로 활용할 수 있는 방법이 많기에 문제도 다양하게 출제를 할 수 있다. 그래프는 알고리즘에서 굉장히 많이 사용된다. 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다. ..

Bubble Sort란? Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. Process (Ascending) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 ..

Vector란? Vector는 ArrayList와 동일한 내부구조를 가지고 있다. ArrayList와 마찬가지로 Vector내부에 값이 추가되면 자동으로 크기가 조절되며 그다음 객체들은 한 자리씩 뒤로 이동된다. 하지만 Vector와 ArrayList의 한 가지 다른 점이 있는데 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드들이 실행할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있다. Vector의 단점 (ArrayList와 비교) Vector는 항상 동기화된다는 장점이자 단점을 가지고 있다. 스레드가 1개일때도 동기화를 하기 때문에 ArrayList보다 성능이 떨어..

Stack이란? Stack이란 쌓아 올린다는 것을 의미. 따라서 Stack 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. Stack의 특징 Stack은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고,Top으로 정한 곳을 통해서만 접근할 수 있다.가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.Stack에서 자료를 삭제할 때에도 top을 통해서만 가능하다. 데이터 넣기(Stack에서 top을 통해 삽입): push() 데이터 최상위 값 빼기(top을 통한 삭제): pop() 비어있는지 확인: isEmpty() 꽉 차 있는지 확인: isFull() 따라서 Stack..

Array는 index로 빠르게 읽기는 좋은데 유연하지 못하고 ... List는 유연하기는 한데 index로 빠르게 읽기는 못하고... 유연하면서도 빠르게 읽어내는 방법이 없을까? Map Key와 Value로 이루어진 자료구조. 순차적으로 메모리에 데이터를 저장하는 Array와 List와는 달리 Key와 Value로 구성되어 있다. hashing: Key를 범위(배열 크기)에 맞게 적절히 겹치지 않는 index로 변경한다. hash function: hashing의 기능을 수행함, key값을 넣으면 hash값으로 변환하여 bucket의 index로 사용된다. bucket: Map의 Array hash collision: 해쉬 충돌, 이미 존재하는 key값에 다른 key값으로 같은 hash의 index를 ..

List 개념 이해하기 자료구조 중 하나인 List는 배열의 한계를 극복할 수 있는 강력한 자료구조 중 하나이며 데이터를 단순하지만 효율적으로 다룰 수 있는 자료구조이다. List는 Array처럼 어떠한 데이터들을 묶기 위한 개념이다. Array와 대표적으로 다른 특징들은 아래와 같다. 데이터를 담을 공간의 추가가 가능하다. (Array는 초기 공간을 지정하기 때문에 한정적) 데이터를 담을 공간의 삭제가 가능하다. (Array는 데이터가 담기는 공간의 값을 변경할 수 있지만 그 공간을 삭제할 수 는 없다.) 즉, 크기가 가변적이다. List 인터페이스의 구현체에는 Stack, Vector, ArrayList, LinkedList가 있다. 이 중에서도 대표적인 클래스인 ArrayList와 LinkedLis..