🐯 알고리즘/알고리즘 정리

집합이란?개념: 순서와 중복이 없는 원소들을 갖는 자료구조종류: 유한 집합, 무한 집합 등, 중요한 것은 상호배타적 집합상호배타적 집합: 교집합이 없는 집합 관계이를 활용하여 이미지 분할, 최소 신장트리 알고리즘 구현, 클러스터링 작업 등이 가능하다. 집합의 연산 배열을 활용한 트리로 표현대표 원소: 집합을 대표하는 원소 -> 루트 노드를 생각하자하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다. 집합을 트리로 변경 시 "배열의 값=인덱스의 부모노드"ex) set[9] = 3 -> 9의 부모는 3 유니온-파인드 알고리즘집합 알고리즘에 주로 쓰이는 연산: 합치기&탐색 = Union&Find -> 찾고나서 합치자 Find 연산특정 노드의 루트 노드 탐색A,B 두 노드의 루트 노드가 같다? ->..

트리 분야: 인공지능, 데이터베이스, 자동 완성 시스템 등 다양한 분야에서 사용트리는 에지로 연결된 노드로 구성된 계층 구조노드: 각 노드에는 데이터가 들어 있다.루트: 최상위 노드로, 부모가 없는 노드자식/부모: 계층적 방식으로 연결된 노드Leaf: 자식이 없는 노드.에지: 부모 노드와 자식 노드 사이의 연결 고리 코테에서는 이진 트리만 알면 된다.이진트리란 모든 노드의 최대 차수가 2를 넘지  않는 트리이진 트리는 배열이나 포인터로 구현한다. 이진 트리  배열로 표현루트 노드가 인덱스 1에 있을 경우왼쪽 자식 = 부모인덱스 * 2오른쪽 자식 = 부모인덱스 * 2 + 1루트 노드가 인덱스 0에 있을 경우왼쪽 자식 = 부모인덱스 * 2 + 1오른쪽 자식 = 부모인덱스 * 2 + 2단점: 이 표현은 배열에..

해시란?개념: 해시 함수를 사용하여 키를 값에 매핑하는 데이터 구조해시 함수는 빠른 조회를 위해 키를 변환된 값(주로 인덱스)으로 변환하여 데이터를 훨씬 빠르게 검색할 수 있게 해준다.연속 인덱스를 사용하는 기존 배열과 달리 해시는 키를 사용하여 데이터를 탐색특징단방향 액세스: 키를 사용하여 값을 찾을 수는 있지만 값에서 키를 찾을 수는 없다.상수 시간 조회(O(1)): 해시 함수는 키에서 직접 인덱스를 계산하므로 전체 데이터 집합을 검색할 필요 없이 빠르게 검색 가능변환 필요: 해시함수를 통해 키를 인덱스로 변환해야 값에 효율적으로 액세스할 수 있다.해시를 사용하지 않으면 항목을 찾기 위해 데이터 전체 검색을 수행해야 하므로 효율성이 훨씬 떨어진다. 해시 테이블 또는 버킷해싱에서 '해시 테이블' 또는 ..

큐란?큐의 ADT isfull: 큐가 꽉 차서 더 이상 데이터를 넣을 수 있는지 여부를 확인하는 함수True: 큐가 꽉 찼음False: 큐에 여유 공간이 있음isempty: 큐가 비어 있는지 확인하는 함수True: 큐가 비었음False: 큐에 데이터가 존재함push (enqueue): 큐의 rear(뒤쪽) 끝에 데이터를 추가하는 함수pop (dequeue): 큐의 front(앞쪽) 끝에서 데이터를 제거하는 함수front: 큐의 앞쪽 끝에 있는 데이터를 반환하는 함수(제거하지 않음)rear: 큐의 뒤쪽 끝에 있는 데이터를 반환하는 함수(제거하지 않음)data[maxsize]: 큐가 내부적으로 데이터를 저장하는 배열 또는 리스트와 최대 크기 maxsize 리스트를 큐처럼 -> 왼쪽에서 삽입, 삭제 가능que..

파이썬은 기본적으로 스택 자료구조를 제공하지 않지만, 리스트를 이용해 스택을 구현할 수 있다.스택은 LIFO(Last In, First Out) 방식으로 동작하며, 마지막에 추가된 항목이 가장 먼저 제거되는 구조파이썬 리스트의 몇 가지 메서드를 사용하면 스택의 기본 연산을 구현할 수 있다. 1.스택 연산push: 스택에 데이터를 추가하는 연산stack = []stack.append(10) # 스택에 10 추가stack.append(20) # 스택에 20 추가print(stack) # 출력: [10, 20] pop: 스택에서 가장 마지막에 추가된 데이터를 제거하고 반환하는 연산popped_element = stack.pop() # 스택에서 가장 위에 있는 20을 제거하고 반환print(popped_..

1차원배열#3가지 방법arr = [0] * 6arr = list(range(6))arr= [0 for _ in range(6)]2차원 배열 arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]print(arr[2][3]) #12arr = [[i]*4 for i in range(3)] # [[0,0,0,0],[1,1,1,1],[2,2,2,2]]실제로는 오른쪽 처럼 저장된다. 배열 선택시 고려할 점할당할 수 있는 메모리 크기를 확인중간에 데이터 삽입이 많은지 확인 파이썬에서는 리스트로 배열 표현 리스트 기법리스트 생성리스트에 데이터 추가append() 메서드: 리스트 끝에 새로운 데이터 추가+ 연산자: 두 리스트를 합쳐서 새로운 리스트 만든다.insert() 메서드: 특정 위치에 데이터 ..

https://product.kyobobook.co.kr/detail/S000210881884 코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고코딩 테스트 합격자 되기: 파이썬 편 | ★ 코딩 테스트 합격자가 되는 가장 확실한 방법! ★ 프로그래머스 제공, 전문가가 모여 엄선한 빈출 100문제로 철저하게 대비하세요신입 사원 코딩 테스트product.kyobobook.co.kr이 책을 가지고, 코테를 준비해보고자 한다. 배열부터 그리디까지 12단원이니, 하루에 한단원 끝낸다는 마인드로 차근차근 정리해보고자 한다.모든 문제를 12일안에 다 풀긴 어려우니1회독은 알고 있는 개념들을 정리하고 기본적인 문제들을 풀어보자2회독은 모든 문제를 내손으로 푸는 것을 중점으로 풀어보자3회독은 시간복잡도와 풀이 ..