본문 바로가기

전체 글

 (228)
선형 자료 구조 - (스택, 벡터, 리스트 구현) 배열배열 : 배열은 인접한 메모리에 저장되는 요소의 집합입니다. 인덱스를 통한 빠른 접근이 가능하며 예상 할 수 있는 순서로 데이터를 저장하고 탐색하는데 사용하기 좋은 자료구조입니다. 또한, 연속된 메모리 주소에 요소들이 존재하기 때문에 관리하기 쉽습니다.다만, 삽입과 삭제에 시간 복잡도 O(N) 성능을 보여 다른 자료구조보다 시간적 성능이 좋지 못합니다. 또한, 메모리의 재사용이 어렵습니다. 처음 할당 받은 메로리 중 일부 데이터를 삭제하더라도 배열 자체가 삭제되지 않으면 해당 공간을 재사용 할 수 없습니다.배열의 시간복잡도 :탐색 - 임의 접근 방식으로 인덱스를 가지고 있기에 빠른 탐색이 가능합니다. 탐색 시 배열은 O(1) 의 시간복잡도를 가집니다.추가 - 추가하려는 데이터가 맨 뒤가 아니면 특정 ..
그 외 개발 경험
이진 탐색 트리와 균형 이진 트리 이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 현재 노드보다 작은 값이고 오른쪽 자식은 현재 노드보다 큰 값을 가지는 이진 트리이다. 이진 탐색을 이용하면 시간복잡도 O(logn) 으로 빠른 탐색이 가능하다. 그런데 이러한 이진 탐색을 위한 저장공간이 배열이기 때문에 (인덱스가 있어야한다) 결국 이 배열에 삽입/삭제 시에는 O(n) 의 시간복잡도를 가지게 된다. 탐색, 삽입, 삭제 에 전부 O(logn) 가지는 자료구조를 표현한 것이 이진 탐색 트리이다. 이진 탐색 트리의 순회 탐색에는 3가지 방법이 있다.전위 순회입력으로 들어온 현재 노드를 출력왼쪽 노드 방문오른쪽 노드 방문중위 순회왼쪽 노드를 방문현재 노드를 출력오른쪽 노드를 방문..
BFS DFS 차이 DFS와 BFS 는 그래프 탐색 알고리즘입니다. DFS 는 깊이 우선 탐색으로 시작 노드부터 각각의 분기들을 순차적으로 완벽 탐색하는 알고리즘입니다. 시작 노드에서부터 최대한 깊이 들어가면서 그래프를 탐색합니다.한 경로를 끝까지 탐색한 후, 되돌아와서 다른 경로를 탐색합니다.스택 또는 재귀 함수를 사용하여 구현할 수 있습니다. 노드의 수 V, E는 간선의 수를 나타냅니다.시간복잡도 시간 복잡도는 인접 리스트를 사용하는 경우 각 노드와 그 인접한 간선들을 한 번씩 방문하므로 O(V + E)입니다.인접 행렬을 사용하는 경우 모든 노드를 방문하고 간선을 확인하므로 O(V^2)입니다.  BFS 는 시작 노드로부터 인접한 노드들을 먼저 탐색하는 탐색 알고리즘입니다. 큐를 사용하여 먼저 발견된 노드들에게 우선 탐..
트리와 그래프 트리트리는 루트 노드를 가지는 계층적 구조의 자료구조 입니다.루트 노드로 부터 하위 노드로 연결되어지며 사이클이 없습니다. 비순환적 그래프로 볼 수 있습니다.임의의 2개의 노드 사이에는 하나의 경로가 존재합니다.트리의 노드는 자식 노드를 1개 이상 가질 수 있습니다.  트리를 기반으로 이진 트리, 힙 트리, b 트리 등의 다양한 자료구조를 만들 수 있습니다. 그래프 그래프 비선형 데이터 구조로, 여러 개의 노드와 이를 연결하는 간선으로 구성됩니다.노드 간에는 부모-자식 관계가 없습니다. 각각의 노드들은 간선으로 연결 될 수도 있습니다.간선을 가지기 때문에 무방향, 단방향, 양방향 그래프등의 다양한 그래프가 존재합니다.그래프는 사이클을 가질 수 있습니다. 노드 간에 복잡한 형태를 그래프로 표현 가능합니다...
배열(Array)과 연결 리스트(Linked List) 배열은 고정 길이이며 연속적으로 데이터를 저장합니다. 순차탐색에 용이하고 인덱스를 가지기 때문에 임의 접근이 가능하다는 장점이 있습니다.중간 삽입/삭제가 비효율적이고 고정 길이를 가지기 때문에 사용에 따라 메모리를 낭비할 수 있다는 단점이 있습니다. 연결 리스트는 노드기반이며 동적 크기를 가질 수 있습니다. 데이터가 연결 리스트에 추가/삭제된다면 이 전 노드와 연결만 해주면 되어 삽입/삭제가 편합니다. 필요한 만큼만 데이터를 사용하기 때문에 메모리를 효율적으로 사용가능합니다.데이터가 연속적으로 저장되는 것은 아니기 때문에 순회 시 배열보다 느릴 수 있습니다. 특정 요소를 접근할 때 인덱스가 없기 때문에 임의 접근이 어렵습니다.   배열은 데이터의 크기가 고정되어 있거나 빠른 접근이 필요한 경우에 적합합니..
해시 테이블 해시 테이블은 Key와 Value 로 데이터를 저장하는 자료구조 입니다. 해시 테이블은 해시 함수를 사용합니다. 해시 함수를 이용하여 key 값을 해시 value 를 생성합니다. 생성된 해시 value 를 배열의 인덱스로 하여 그 공간에 value 를 저장합니다. 값을 찾을 때에도 key 값을 해시함수에 넣어 해시 value 를 찾고 배열의 인덱스로 하여 value 를 찾습니다.만약 해시 함수에 의해 나오는 해시 value 값이 같다면 충돌이 생기며,1. 체이닝2. 오픈 어드레스를 이용하여 해결합니다. 1. 체이닝 : 해시 테이블의 각 인덱스의 저장공간을 리스트로 만들어 충돌이 발생할 때 리스트를 이용하여 연결합니다.2. 오픈 어드레스 : 충돌이 일어나면 다른 비어있는 공간을 찾고 저장합니다. 해시 테이..
객체지향의 4대 특성 객체지향의 4대 특징으로는 추상화, 캡슐화,상속, 다형성이 있습니다. 추상화 : 객체들의 공통된 속성과 행동들을 묶어 표현하는 개념입니다. 공통된 기능과 속성만 표현하기 때문에 클래스를 단순화하고 세부적인 내용은 오버라이딩하여 표현합니다. 캡슐화 : 캡슐화는 낮은 결합도를 유지 할 수 있도록 설계하는 객체지향 프로그래밍의 한 특징입니다. 변수와 메소드를 클래스라는 캡슐에 넣어서 분류하여 재활용이 원할하게 하며 접근제한자를 통해 정보은닉을 할 수 있습니다.외부에서 객체의 데이터를 직접 접근하지 못하게 하고, 메서드를 통해서만 접근하도록 제한합니다 상속 : 한 클래스가 가진 속성과 기능을 하위 클래스에게 물려주는 것을 의미합니다. 파생 클래스는 기반 클래스의 특정 속성과 기능을 사용할 수 있습니다. 계층적 ..

티스토리툴바