TIL/자료구조 & 알고리즘 (10) 썸네일형 리스트형 에라토스테네스의 체(소수 찾기) 소수인지 확인하는 함수def is_prime(num): if num 위의 코드는 해당 수보다 작은 모든 수로 나누어 보아서 소수인지를 판단하는 방법으로, 소수의 정의에 충실한 방법이면서 무식하지만 가장 강력한 방법이다.한 개의 소수를 구할 때는 그런대로 괜찮은 방법인데 범위의 모든 소수를 구할 때는 효율적인 방법이 아니다.소수를 구하기 위해 에라토스테네스가 제안한 방법은 다음과 같다.에라토스테네스의 체범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.1은 제거지워지지 않은 수 중 제일 작은 수(2)를 소수로 채택하고, 나머지 제일 작은 수(2)의 배수를 모두 지운다.지워지지 않은 수 중 제일 작은 수(3)을 소수로 채택하고, 나머지 제일 작은 수(3)의 배수를 모두 지운다.4는 2의 과정에서 지워.. [자료구조] 최소 신장 트리(Minimum Spanning Tree) 신장트리(Spanning Tree) Spanning Tree 특징 최소 신장 트리(MST, Minimum Spanning Tree) Kruskal MST 알고리즘 Prim MST 알고리즘 신장 트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프의 n 개의 정점을 모두 연결하는 최소 간선의 수는 (n-1) 개이고, 이때 이루어진 그래프를 최소 연결 부분 그래프 Spanning Tree라고 한다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 Spanning Tree 특징 DFS, BFS를 이용하여 그래프의 신장 트리를 찾을 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 신장 트리는 모든 정점들이 연결되어 있어야 한다. 신장 트리는 사이클을 포함해서는 안된다. .. [자료구조] 그래프의 표현(인접행렬, 인접리스트) 인접 행렬은 모든 노드를 표현하고 각 노드의 연결 상태를 나타낸다.2차원 배열을 활용하여 그래프를 표현하는 방식인접 리스트는 실제로 연결된 노드들만 저장하기 때문에 간선의 개수와 비례하는 만큼만 메모리를 차지한다.인접 리스트를 활용하여 표현하는 방식인접 행렬 (Adjacency Matrix)인접 행렬이란, 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식을 의미한다.adj[i][j] : 노드 i에서 j로 가는 간선이 존재할 경우 1, 아니면 0 만약 표현하고자 하는 그래프가 방향이 없는 무향 그래프의 경우 노드 i에서 노드 j로 가는 길이 존재하면 노드 j에서 노드 i로 가는 길 또한 존재한다.이러한 특성으로 인접 행렬을 구현할 경우, 대각 성분을 기준으로 대칭인 성질을 가지게 된다.1... 자료구조와 알고리즘을 배우는 이유 자료구조란? ㆍ논리적으로 정의된 규칙에 의해 데이터를 효율적으로 관리하기 위한 표현, 혹은 구조 ㆍ 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것 즉, 자료구조란 말 그대로 '데이터(Data)'의 '형태(구조)'를 의미한다. 자료구조와 알고리즘을 배우는이유 자료구조는 메모리를 어떻게 효율적으로 사용하며, 실행속도를 빠르고, 정확하게 처리할 수 있을까 를 궁극적인 목표로 두고 있다. 알고리즘은 이러한 자료구조의 목표를 바탕으로 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현하는 것이다. 우리가 프로그램을 사용하는데 정확성이 떨어진다거나, 실행속도가 현저히 느리다면 더 정확하고 빠른 프로그램을 찾게 되는 것처럼 효율성이 높은 프로그램을 개발하기 위해 필요한 과정에서 일련.. 자료구조의 유형 텍스트 자료의 표현 ASCII ㆍ가장 일반적으로 사용되는 문자 인코딩 중 하나는 ASCII 이다. ㆍ ASCII는 7비트로 구성되며, 가각의 비트 조합은 128개의 고유한 문자를 나타낸다. ㆍ ASCII 코드는 영어 알파벳, 숫자, 특수 문자 등을 포함. 예를 들어, 대문자 'A'는 ASCII 코드에서 65에 해당하는 값으로 표현되며, 이진수로는 01000001이다. ㆍASCII는 각 문자를 7비트로 표현하므도 총 128개의 문자를 표현할 수 있다. * ASCII로 표현할 수 있는 문자들 외에 추가적인 문자를 지원해야 할 필요성이 있어 기존 7비트에 1비트를 추가하여 8비트를 사용한 코드가 정의되었는데 이런 코드를 확장(extended) ASCII라 한다. 확장 ASCII는 기존 ASCII 코드의 가장 .. 파이썬으로 Heap 구현하기 힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조이다. 힙은 다음과 같은 속성을 가지고 있다. 완전 이진트리(Complete Binary Tree) 이다. 부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다. 키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않음 Heap 재구조화(Heapify) 힙에서 원소의 삽입이나 삭제가 일어나면 최대 힙의 조건이 깨질 수 있다. 이 경우 다시 최대 힙의 조건을 만족하도록 노드의 위치를 바꾸는 것을 재구조화(heapify)라고 한다. 삽입과 삭제의 경우 연산 자체는 O(1)의 .. 파이썬으로 stack 구현하기 class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.top = None def push(self, data): node = Node(data) node.next = self.top self.top = node def pop(self): if self.top is None: return None node = self.top self.top = self.top.next return node.data def peek(self): if self.top is None: return None return self.top.data def is_empty(self): retu.. 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 1. 깊이 우선 탐색(DFS)_루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 끝까지 탐색하는 방식즉, 넓게 탐색하기 전에 깊게 탐색하는 것이다. 깊이 우선 탐색의 탐색 방법DFS는 stack을 이용해서 탐색한다.0. 방문한 곳 표시하는 곳 필요1. A를 push하고 시작2. pop하면서 갈 수 있는 노드가 있다면 push!3. 2번을 반복4. 더 이상 갈 수 없다면 pop5. 2번을 반복6. 4번을 반복 재귀를 이용한 완전탐색 == DFS 백트래킹과 DFS의 차이DFS = 그래프를 완전탐색하는 순회 기법백트래킹 = 정답을 찾는 도중에 해가 되지 않을 것 같은 경로가 있다면 더 가지 않는 가지치기DFS는 단순히 깊이 우선으로 모든 경로를 탐색하는 알고리즘백트래킹은 DFS의 한 형태로, 유망.. [알고리즘] 이분 탐색(binary search) 이진 탐색, 이분 탐색(binary search)이란? 말 그대로 이등분 해가며 탐색하는 알고리즘이다. 찾아야할 숫자가 100이라면 1부터 100까지 하나씩 찾아가는 선형 탐색에 비해 이분 탐색을 활용해 이등분씩 해나가며 탐색을 하면 시간복잡도를 훨씬 줄일 수 있다. 이분 탐색 기본 코드 예제 def binary_search(array: list, target: int): left = 0 right = len(array) - 1 while left target: right = mid - 1 elif array[mid] < target: left = mid + 1 else: return 1 return 0 array의 길이를 기준으로 왼쪽과 오른쪽을 나누고 array의 중간 값과 target 값을 비교해 .. 배열(array)과 연결리스트(linked list) 차이점 배열(array) 배열은 같은 타입의 변수들로 이루어진 집합으로 메모리의 연속공간에 값이 채워져 있는 형태 장점 - 검색 성능 : 인덱스를 사용하여 원소에 바로 접근이 가능(O(1)) - 읽기.쓰기, 즉 참조에 좋은 성능 - 데이터양과 상관없이 항상 일정한 연산량을 갖는 알고리즘 단점 - 초기 선언된 사이즈만큼 메모리의 연속 공간이 필요하므로 작은 빈 공간은 버려지는 경우가 생겨 메모리 활용에 비효율적 - 값의 삽임과 삭제에서 비효율적, 데이터 중간 지점에서 자료의 삽입, 삭제가 일어날 경우 다음 항목의 모든 값을 이동시켜야 함 연결 리스트(Linked list) 배열의 단점을 보완하기 위하여 만들어짐. - 데이터를 분산해서 저장하고, 연결해주자! 장점 - 선언할 때 크기를 지정하지 않으며 주소로 계속 .. 이전 1 다음
