난쟁이 개발자

그래프는 노드(vertex)와 간선(edge)을 이용한 비선형 데이터 구조 . 보통 그래프는 데이터 간의 관계를 표현하는 데 사용됨. 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현함. 간선은 방향이 있을 수도, 없을 수도 있음. 만약 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치라는 개념을 추가하여 표현하기도 함. 그래프 용어 정리 예를 들어 도시 간의 인구 이동을 그래프로 표현하면 다음과 같다. 그림에서 사각형으로 표현한 것은 노드(또는 정점), 화살표로 표현한 것은 간선, 간선 위에 숫자로 표현한 것은 가중치다. 노드에는 어떤 데이터가 들어있다. 인구 이동의 경우 어디서 얼마나 이동했는지 표시할 필요가 있으므로 간선에 가중치를 표현함. 흐름을 표현하는 방향성 간선은 방향을 가질 수도 ..

집합과 상호배타적 집합의 개념 개념 : 집합은 순서와 중복이 없는 원소들을 갖는 자료구조. A라는 그룹의 원소 구성이 {1, 6, 6, 6, 4, 3} 이라면, 이는 집합으로 생각할 때 중복을 제외해 {1, 6, 4, 3}으로 생각해야 한다. 순서를 따지지 않는다. 집합의 종류 유한 집합 : 원소의 개수가 유한함. 무한 집합 : 원소의 개수가 무한함. 공집합 : 집합이 비어 있음. 상호배타적 집합 : 교집합이 없는 집합관계 상호배타적 집합이란 ? 교집합이 없는 집합 관계. A = {1, 2, 3} B = {4, 5, 6, 7} 이 두 집합의 원소 중 겹치는 원소가 없으면 교집합이 없다고 할 수 있고 이를 상호배타적 집합이라고 함. 상호배타적 집합의 특성을 활용하는 분야 코딩 테스트에서 항호배타적 집합을 ..

프로그래밍 분야에서 트리는 계층 구조를 표현하는 용도로 많이 사용됨. 인공지능 : 인공지능의 판단 기준을 만들 때 의사 결정 트리를 사용. 이를 통해 외부에서 입력된 데이터를 분류하거나 상황을 예측하는 모델을 만들 수 있음. 자동 완성 기능 : 트리는 문자열 처리에도 많이 활용됨. 검색 엔진에서 자동 검색어 추천 기능도 트리 구조를 활용한 것. 데이터베이스 : 데이터를 쉽게 검색, 삽입, 삭제할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱함. 트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양. 따라서 밑둥(root)는 맨 위에 있음. 노드(Node) 트리를 구성하는 기본 요소 노드에는 데이터와 하위 노드에 대한 참조를 가지고 있다.(연결리스트와 유사하다.) 그래프에서 정점과..

해시 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 해시의 특징 단방향으로 동작한다. - 키를 통해 값을 찾을 수 있지만 값을 통해서 키를 찾을 수 는 없다. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있습니다. - 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다. 해시를 사용하지 않는다면 우리는 값의 위치에 대한 어떤 정보를 알 수 없다. 따라서 내가 찾고자 하는 데이터를 전체 데이터를 확인하는 방법이 유일한 방법이다. 반면 해시를 사용하면, 순차 탐색할 필요 없이 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐..

큐(Queue)는 데이터를 저장하는 자료구조 중 하나로, 데이터를 일렬로 나열한 선형구조입니다. 큐는 데이터를 넣는 Enqueue(인큐)와 데이터를 빼내는 Dequeue(디큐) 연산을 지원하며, 데이터는 First in First Out (FIFO)의 원칙을 따릅니다. 즉, 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다. 큐의 주요 특징과 용어 : Push : 큐에 새로운 데이터를 추가하는 작업입니다. 새로운 데이터는 큐의 뒤쪽(Rear)에 추가됩니다. Pop : 큐의 가장 앞쪽(Front)에 있는 데이터를 제거하고 반환하는 작업입니다. 가장 먼저 추가된 데이터가 먼저 제거됩니다. Front : 큐의 가장 앞쪽에 있는 데이터를 조회하는 작업입니다. Rear : 큐의 가장 뒤쪽에 있는 데이터를 조회하는 ..

스택 개념 선입후출 또는 FILO(First In Last Out) : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조. 스택 정의 스택은 ADT(abstract data type) - 추상 자료형이며, 인터페이스만 있고 실제로 구현은 되지 않은 자료형 파이썬의 경우, 스택을 제공하지 않지만 대안으로 리스트 메서드인 append() 메서드, push() 메서드로 스택을 대체 가능 deque는 한 쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양 쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조 이런 특징을 조금만 응용하면 스택처럼 사용할 수 있음. 스택 구현하기 더보기 stack = [] # 스택 리스트 초기화 max_size = 10 # 스택의 최대 크기 def isFull(stack..

자료구조 시간 복잡도 평균 최악 접근 탐색 삽입 삭제 접근 탐색 삽입 삭제 배열 array O(1) O(N) O(N) O(N) O(1) O(N) O(N) O(N) 주로 여러개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다. [인덱스, 값] 쌍의 집합이다. 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조 순차적 메모리 공간에 할당되는 순차적 표현 같은 자료형의 변수를 여러 개 만드는 경우에 유용함 동일한 이름을 사용하는 인덱스 번호로 각 항목을 접근할 수 있다. 배열은 어느 위치에나 O(1)에 조회가 가능하다 인덱스(Index) : 각 요소는 배열 내에서 고유한 인덱스를 가지며, 이 인덱스는 배열의 시작부터 얼마나 떨어져 있는지를 나타냅니다. 대부분의 프로그래밍 언어에서 인덱스는 0부터 시작하며..

03 - 알고리즘의 효율 분석 시간 복잡도 : 알고리즘 성능을 나타내는 지표 시간 복잡도는 대체로 낮으면 낮을수록 좋음. 빅오 표기법 : 해당 알고리즘에 대한 최악의 시간 복잡도를 표현하는 방법. 수식 빅오 표기 설명 3x^2 + 5x + 6 O(x^2) 다항 함수로 구성되어 있으므로 최고 차항 x^2 만 남습니다 x + logx O(x) 다항함수 + 로그함수의 경우, 증가폭이 더 낮은 로그함수를 제거하고 다항함수만 남깁니다. 2^x + 10x^5 + 5x^2 O(2^x) 지수함수는 다항함수보다 빠르게 증가하므로 지수함수만 남습니다. 시간 복잡도 최대 연산 횟수 O(N!) 10 O(2^N) 20 ~ 25 O(N^3) 200 ~ 300 O(N^2) 3,000 ~ 5,000 O(NlogN) 100만 O(N)..