본문 바로가기

전체 글

[코딩 테스트 합격자 되기 - 6주차] 트리(Tree) 프로그래밍 분야에서 트리는 계층 구조를 표현하는 용도로 많이 사용됨. 인공지능 : 인공지능의 판단 기준을 만들 때 의사 결정 트리를 사용. 이를 통해 외부에서 입력된 데이터를 분류하거나 상황을 예측하는 모델을 만들 수 있음. 자동 완성 기능 : 트리는 문자열 처리에도 많이 활용됨. 검색 엔진에서 자동 검색어 추천 기능도 트리 구조를 활용한 것. 데이터베이스 : 데이터를 쉽게 검색, 삽입, 삭제할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱함. 트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양. 따라서 밑둥(root)는 맨 위에 있음. 노드(Node) 트리를 구성하는 기본 요소 노드에는 데이터와 하위 노드에 대한 참조를 가지고 있다.(연결리스트와 유사하다.) 그래프에서 정점과.. 더보기
[코딩 테스트 합격자 되기 - 5주차] 해시(Hash) 해시 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 해시의 특징 단방향으로 동작한다. - 키를 통해 값을 찾을 수 있지만 값을 통해서 키를 찾을 수 는 없다. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있습니다. - 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다. 해시를 사용하지 않는다면 우리는 값의 위치에 대한 어떤 정보를 알 수 없다. 따라서 내가 찾고자 하는 데이터를 전체 데이터를 확인하는 방법이 유일한 방법이다. 반면 해시를 사용하면, 순차 탐색할 필요 없이 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐.. 더보기
[코딩 테스트 합격자 되기 - 4주차] 큐(Queue) 큐(Queue)는 데이터를 저장하는 자료구조 중 하나로, 데이터를 일렬로 나열한 선형구조입니다. 큐는 데이터를 넣는 Enqueue(인큐)와 데이터를 빼내는 Dequeue(디큐) 연산을 지원하며, 데이터는 First in First Out (FIFO)의 원칙을 따릅니다. 즉, 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다. 큐의 주요 특징과 용어 : Push : 큐에 새로운 데이터를 추가하는 작업입니다. 새로운 데이터는 큐의 뒤쪽(Rear)에 추가됩니다. Pop : 큐의 가장 앞쪽(Front)에 있는 데이터를 제거하고 반환하는 작업입니다. 가장 먼저 추가된 데이터가 먼저 제거됩니다. Front : 큐의 가장 앞쪽에 있는 데이터를 조회하는 작업입니다. Rear : 큐의 가장 뒤쪽에 있는 데이터를 조회하는 .. 더보기
[코딩 테스트 합격자 되기 - 3주차] 스택 스택 개념 선입후출 또는 FILO(First In Last Out) : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조. 스택 정의 스택은 ADT(abstract data type) - 추상 자료형이며, 인터페이스만 있고 실제로 구현은 되지 않은 자료형 파이썬의 경우, 스택을 제공하지 않지만 대안으로 리스트 메서드인 append() 메서드, push() 메서드로 스택을 대체 가능 deque는 한 쪽으로만 데이터 삽입, 삭제할 수 있는 스택과 다르게 양 쪽에서 데이터를 삽입하거나 삭제할 수 있는 자료구조 이런 특징을 조금만 응용하면 스택처럼 사용할 수 있음. 스택 구현하기 더보기 stack = [] # 스택 리스트 초기화 max_size = 10 # 스택의 최대 크기 def isFull(stack.. 더보기
[코딩 테스트 합격자 되기 - 2주차] 배열 자료구조 시간 복잡도 평균 최악 접근 탐색 삽입 삭제 접근 탐색 삽입 삭제 배열 array O(1) O(N) O(N) O(N) O(1) O(N) O(N) O(N) 주로 여러개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다. [인덱스, 값] 쌍의 집합이다. 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조 순차적 메모리 공간에 할당되는 순차적 표현 같은 자료형의 변수를 여러 개 만드는 경우에 유용함 동일한 이름을 사용하는 인덱스 번호로 각 항목을 접근할 수 있다. 배열은 어느 위치에나 O(1)에 조회가 가능하다 인덱스(Index) : 각 요소는 배열 내에서 고유한 인덱스를 가지며, 이 인덱스는 배열의 시작부터 얼마나 떨어져 있는지를 나타냅니다. 대부분의 프로그래밍 언어에서 인덱스는 0부터 시작하며.. 더보기
[코딩 테스트 합격자 되기 - 1주차] 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).. 더보기

티스토리툴바