[자료구조] 배열 (Array)

1. 소개 배열은 많은 유사한 항목을 저장하기 위한 간단한 데이터 구조이다.모든 프로그래밍 언어에 존재하고 많이 데이터 구조의 기반으로 사용된다.배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 한다.면접 문제에서 자주 등장하므로 배열을 잘 다루면 좋을 것 같다. 장점인덱스를 이용한 접근이 가능하므로 모든 요소에 O(1)의 시간복잡도로 접근이 가능하다.List, Graph와 달리 포인터정보를 저장하지 않으므로 메모리효율이 좋다. 단점할당될때 크기가 정해지므로 변경이 힘들다.중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제된 요소로부터 위에 있는 모든 요소들을 이동시켜주어야 한다...

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 31.
• textsms

[자료구조] Set

1. 소개Set이란?Set은 Java 컬렉션 프레임워크의 일부로, 중복을 허용하지 않는 데이터 집합을 표현한다.수학의 집합 개념과 유사순서를 보장하지 않지만, 일부 구현체(LinkedHashSet, TreeSet)는 순서를 유지하거나 정렬한다. 특징중복 요소를 허용하지 않는다.null 요소를 허용한다. (TreeSet은 허용 X)순서를 보장하지 않는다. (LinkedHashSet, TreeSet은 예외) 주요 메서드boolean add(E e); // 요소 추가boolean remove(Object o); // 요소 삭제boolean contains(Object o); // 요소 포함 여부 확인int size(); // Set의 크기 반환boolean isEm..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 27.
• textsms

[자료구조] Map

🗺️ Map   key, value 쌍으로 저장하고 관리하는 자료구조  인덱스로 값에 접근하는 리스트, 배열과는 다르게 Map을 사용하면 개발자가 지정하는 key로 값에 접근이 가능하다.Map은 그 내부 구현 방식에 따라 'HashMap', 'TreeMap', 'LinkedHashMap' 등으로 나뉜다.    장점 빠른 데이터 검색데이터 검색과 조회가 빠르다. 키를 통해 바로 값으로 접근할 수 있기때문키 기반 데이터 관리키로 고유 식별자를 부여하여 데이터를 관리할 때 적합함. ex) Key == 학생 ID, Value == 학생정보 단점 메모리 사용량 증가키 관리의 복잡성키의 고유성을 유지해야한다. 동일한 키를 사용해 삽입하면 기존 값이 덮어씌워짐  주요 메서드put(key, value): 지정된 키와..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 27.
• textsms

[자료구조] Heap (힙)

Heap 이란? Heap 자료구조는 이진트리 중에서도 완전이진트리의 속성을 가지고 있다. 힙은 최대 힙 Max Heap과 최소 힙 Min Heap으로 구분할 수 있다. 최대 힙은 부모노드가 항상 자식노드보다 큰 값을 가지고 있기 때문에 루트 노드는 항상 트리의 최댓값을 가지고 있게 된다. 반대로 최소 힙은 부모노드의 값은 항상 자식 노드보다 작기 때문에 루트 노드는 트리의 최솟값이 들어있게 된다. 항상 그렇기 때문에 이 힙의 새로운 값이 추가되거나 삭제되어도 특성은 유지되어야 한다.! 힙은 이진탐색트리와는 다르게 값의 중복이 허용되고, 좌우 노드 간의 관계가 아닌 상하 관계에서만 값의 제약을 받게 된다. 힙의 시간 복잡도 최대 혹은 최소값을 빠르게 가져오는 게 중요한 상황에서 사용할 수 있다.힙에서 최대..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 21.
• textsms

[자료구조] 그래프, dfs, bfs

그래프란? 정점(vertice)과 정점간의 관계를 표현한 조직도직접적인 관계가 있다면 두 정점 사이에 간선(edge)이 있고 간접적인 관계가 있다면 몇 개의 점과 선에 걸쳐서 이어진다.' 용어 정점(Vertice): 데이터가 저장되는 그래프의 기본 원소, 노드라고도 한다.간선(Edge): 정점 간의 관계를 나타내는 선사이클(Cycle): 한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 할 수 있음.자기 루프(Self loop): 한 정점에서 출발한 간선이 다른 정점을 거치지않고 다시 자기 자신에게 돌아오면 자기루프를 가진다고 표현함.차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 그래프 구현 그래프를 구현하는 방식에는 인접행렬과 인접리스트 방식이 있다. 인..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 21.
• textsms

[자료구조] 트라이 (trie)

트라이(trie)란? 트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조.흔히 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조이다. 장단점트라이는 문자열 검색이 빠르다.문자열을 탐색할때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 효율적이다.각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있음. 삽입 예제apple, app, asia를 입력했을 때의 모습 처음 apple을 넣을 때 head의 자식노드에 아무것도 없으므로 a를 추가한다.a노드의 자식도 없으므로 p를 넣어준다.p의 자식도 없으므로 다음 글자인 p를 넣어준다. 이런식으로 e까지 자식노드로..

• format_list_bulleted 알고리즘공부/자료구조
• · 2025. 1. 20.
• textsms