알고리즘 (5) 썸네일형 리스트형 [Python] 연산 속도 올리기 - 개요 및 알고리즘과 자료구조 🐍 본 게시글은 Python 3.11.0 환경에서 작성되었습니다! 파이썬은 인터프리터 언어로 알려져 있지만 사실은 하이브리드 언어로 볼 수 있다.그 이유는 동작 방식을 보면 알 수 있다. 파이썬 코드가 동작하는 방식을 보면 프로그래머가 Python Source Code를 Python Interpreter에 전달하면 내부에서 다음과 같은 과정이 진행된다.Python Complier가 파이썬 소스 코드를 읽고 문법 검사 후 오류가 없으면 바이트 코드로 변환 한다.PVM(Python Virtual Machine)이 바이트 코드를 기계어로 한줄씩 번역한다. 이런 과정이 끝난 후 컴퓨터는 번역된 기계어를 실행한다. Python Compiler가 변환한 바이트 코드를 프로젝트에서 볼 수 있는데 바로 __pyca.. [알고리즘] BFS, DFS 그래프(Graph) 그래프는 노드(Node)와 간선(Edge)으로 이루어진 자료구조로, 객체 간의 관계를 표현하는 데 사용된다. 그래프는 다양한 형태로 표현될 수 있으며, 일반적으로 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)로 구현된다. 인접 행렬(Adjacency Matrix) 인접 행렬은 2차원 배열로 그래프를 표현하는 방식이다. 그래프의 노드 수를 N이라고 할 때, N x N 크기의 행렬을 생성하고, 각 행렬 요소에 노드 간의 연결 여부를 저장한다. 인접 행렬은 노드 간의 연결 여부를 상수 시간(O(1))에 확인할 수 있어서 빠른 검색이 필요한 경우 유용하다. 하지만 그래프의 크기가 크면 공간 효율성이 떨어질 수 있다. 인접 리스트(Adjacency Lis.. [알고리즘] 문자열 검색 브루트 포스(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번 수행한다. 각 .. [알고리즘] 재귀 재귀(Recursion) 재귀란 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 말한다. 재귀를 사용하면 특정 프로그램을 간결하고 효율성 좋게 작성할 수 있다. 가장 대표적인 예시로 팩토리얼(Factorial)이 있다. 팩토리얼은 양의 정수를 순서대로 곱한다는 의미로 "순차 곱셈"이라고도 한다. ex. 0! = 1, 2! = 1 x 2 = 2 팩토리얼은 일정한 공식 있는데, 10!은 10 x 9!과 같이 나타낼 수 있다. 이를 일반화하면 n! = n x (n-1) x .... x 1와 같이 나타 낼 수 있다. 이 공식를 사용하여 팩토리얼을 구하는 재귀 함수와 일반 함수를 작성해서 비교해보자. # 일반함수로 팩토리얼 구현 def factorial(n:int)->int: s.. 이전 1 다음
