CS/자료구조 및 알고리즘 (7) 썸네일형 리스트형 [알고리즘] BFS, DFS 그래프(Graph) 그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조로, 객체 간의 관계를 표현하는 데 사용된다. 그래프는 다양한 형태로 표현될 수 있으며, 일반적으로 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 구현된다. 인접 행렬(Adjacency Matrix) 인접 행렬은 2차원 배열로 그래프를 표현하는 방식이다. 그래프의 노드 수를 N이라고 할 때, N x N 크기의 행렬을 생성하고, 각 행렬 요소에 노드 간의 연결 여부를 저장한다. 인접 행렬은 노드 간의 연결 여부를 상수 시간(O(1))에 확인할 수 있어서 빠른 검색이 필요한 경우 유용하다. 하지만 그래프의 크기가 크면 공간 효율성이 떨어질 수 있다. 인접 리스트(Adjacency Lis.. [자료구조] 트리 트리란? 트리는 계층적인 구조를 가지며, 여러 개의 노드(node)로 이루어진 비선형 자료 구조이다. 노드(Node) 트리의 기본 요소로서 데이터와 다른 노드와의 관계 정보를 가지고 있다. 각 노드는 하나의 데이터를 포함하고 있으며, 노드 간에는 부모(parent)와 자식(children) 관계가 있다. 루트(Root) 트리의 가장 상위에 위치한 노드로, 모든 다른 노드는 루트로부터의 경로를 통해 접근할 수 있다. 부모와 자식(Parent and Children) 트리에서 부모 노드는 자식 노드를 가리키는 관계를 가지고 있다. 부모 노드는 자식 노드보다 상위에 있으며, 자식 노드는 부모 노드에 의해 직접적으로 연결된다. 가지(Branch) 부모 노드와 자식 노드 사이의 연결을 나타내는 선이다. 각 노드는.. [자료구조] 리스트 리스트(List) 데이터 요소들을 순서대로 저장하는 자료구조이다. 배열 또는 동적 배열로 구현될 수 있다. 인덱스를 사용하여 각 요소에 접근할 수 있다. # 리스트 from typing import Any class List: def __init__(self,size:int)->None: self.size = size print(f"{self.size} 크기의 리스트 생성!") self.__container = [None] * self.size def getter(self,index:int)->Any: return self.__container[index] def setter(self,item:Any,index:int)->None : self.__container[index] = item def add(.. [알고리즘] 문자열 검색 브루트 포스(Brute Force) 선형검색을 단순하게 확장한 것으로 가능한 모든 위치에서 패턴을 일치시키는 과정을 반복하여 검색하는 방법이다. 예시 # 브루트 포스 # 문자열에서 C 찾기(대소문자 구분 X) string = input("영어 문자열을 입력해주세요 : ") matchContainer = [] for idx,c in enumerate(string): if c.upper() == 'C': print(f'"{c}" match? -> Yes') matchContainer.append(idx) else: print(f'"{c}" match? -> No') if matchContainer == []: print("문자열 내에 C가 없습니다.") else: print(f"문자열 {string}에서 C.. [알고리즘] 정렬 정렬 정렬이란 값을 대소 관계에 따라 일정한 순서로 늘어놓는 작업을 의미한다. 정렬을 사용하면 검색을 더 쉽게 할 수 있다. 오름차순 정렬(Ascending order) : 값이 작은 데이터를 앞쪽에 배치 내림차순 정렬(descending order) : 값이 큰 데이터를 앞쪽에 배치 버블 정렬(Bubble Sort) 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 정렬 알고리즘이다. 시간복잡도(Time Complexity) 최선의 경우(정렬된 배열이 주어진 경우): O(n) 이 경우에는 인접한 원소를 비교하고 교환할 필요가 없기 때문에 한 번의 순회만으로 정렬이 완료된다. 평균 및 최악의 경우: O(n^2) 버블 정렬은 인접한 원소를 비교하고 교환하는 과정을 n-1번 수행한다. 각 .. 이전 1 2 다음
