본문 바로가기
반응형

언어별 개념 정리/Python16

[Python] 알고리즘 풀이 시 유용한 함수 사용 팁 (map, join 등) 1. 2차원 배열에서 최대값 & 최소값 & 합 구하기 (Map 함수 활용) - map 함수의 기본 구성은 map(function,iterable) - function 부분에 다른 기능을 추가해서 2차원 리스트에 적용 할 수 있음. # 2차원 배열에서 반복문을 사용하지 않고 특정 값 구하기 x = [[1,0,-30,6,5],[3,4,7,8,1],[3,2,6,7,1],[-1,2,3,6,8],[99,1,2,3,6,8]] print(max(map(max, x))) # 최대값 99 print(min(map(min, x))) # 최소값 -30 print(min(map(max, x))) # 내부 배열의 최대 값들 중에서 가장 작은 값 6 print(max(map(min, x))) # 내부 배열의 최소 값들 중에서 가.. 2023. 4. 29.
[파이썬] 탐색 알고리즘 정리 - 백트래킹 백트래킹 (*Notion AI의 설명) 백트래킹(Backtracking)은 해결책을 구하기 위해 모든 가능성을 시도해보는 것이 아니라, 해결책에 대한 후보군을 구성하고 그 후보군이 문제의 조건을 만족하는지 여부를 검사해가며 해답을 찾아가는 알고리즘입니다. 백트래킹은 대표적으로 스도쿠, N-Queen, 암호해독 등의 문제에서 활용됩니다. 이 알고리즘은 보통 재귀적으로 구현되며, 각 단계에서는 해결책 후보군 중 하나를 선택하고, 이 선택이 문제의 조건을 만족하는지 검사합니다. 조건을 만족하지 않는다면 이전 단계로 돌아가 다른 후보군을 선택합니다. 이러한 과정을 반복하면서 최종적으로 해결책을 찾아가는 것이 백트래킹의 기본적인 원리입니다. 백트래킹은 완전탐색(Exhaustive Search)과 유사하지만, 백트.. 2023. 3. 12.
[파이썬] 알고리즘 - 트리 순회 (전위, 중위, 후위) (python) 트리(Tree) 트리는 노드(node)와 노드들을 연결하는 에지(edge)로 이루어진 자료 구조 특징 각 노드는 하나의 부모 노드와 여러 개의 자식 노드를 가질 수 있음. 트리는 그래프의 한 종류로, 루트(root) 노드에서 시작하여 모든 노드를 방문할 수 있는 구조. 이진 트리(Binary Tree) 이진 트리는 각 노드가 최대 두 개의 자식 노드를 갖는 트리, 자료 구조에서 가장 널리 쓰이는 구조 참고사항 트리는 계층적인 구조를 나타내기 때문에, 운영 체제에서 디렉터리 구조, 인터넷에서의 사이트 맵, 컴파일러에서의 구문 분석 트리 등에 적용 트리 순회(Tree Traversal) 트리 순회는 트리의 모든 노드를 방문하는 방법 전위 순회(preorder traversal) 부모노드 → 왼쪽 자식 노드 .. 2023. 2. 27.
[파이썬] 탐색 알고리즘 정리 - 깊이 우선 탐색(DFS) (python) 깊이 우선 탐색 (Depth First Search, DFS) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 갈 수 있는 곳이 없으면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하여 모든 정점을 방문하는 방법 특징 가장 마지막에 만났던 정점으로 돌아가 다시 탐색을 반복하므로 LIFO 구조의 스택 사용 넓게 탐색하기 전에 깊게 탐색하므로 깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)이 넓이 우선 탐색(BFS)보다 간단 탐색 속도는 DFS가 BFS보다 느림 스택과 재귀 알고리즘의 형태로 구현 가능 트리에서 사용되는 모든 순회는 DFS 의 종류 DFS의 탐색 과정 출처 : https://commons.wikimedia.org/.. 2023. 2. 26.
[파이썬] 탐색 알고리즘 정리 - 너비 우선 탐색(BFS) (python) 너비 우선 탐색(Breadth First Search, BFS) 루트노드(혹은 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 방문해나가 가장 멀리 떨어진 정점을 나중에 방문하는 순회 방법 말그대로 넓게 탐색하는 방법 (방문한 노드를 기준으로 주변을 탐색해나가므로) 깊이 우선 탐색보다 조금 더 복잡함 특징 거리에 따라 단계별로 탐색하므로 직관적이지 않은 면이 있음 그래프 탐색의 경우 어떤 노드를 방문했는지 반드시 검사해야 함 → 그렇지 않을 경우 무한 루프에 빠질 위험 있음 재귀적으로 동작하지 않음 방문한 노드를 차례로 저장한 후 꺼내는 큐(Queue)를 사용(선입선출의 원칙) 시간 복잡도는 O(N)의 시간 소요 (단, 실제 수행 시간은 DFS > BFS) 방문.. 2023. 2. 22.
소수 판별 알고리즘 - 에라토스테네스의 체 📃에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 만들어낸 소수를 찾는 방법 🌓 특징 2~n까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식 실제 계산은 무식하지만 프로그래밍에선 상당히 효율적인 방법론 구하자고하는 수의 √(n)에 해당하는 소수의 배수만 확인하여 지우면 되기 때문에 빠름 👏 과정(예시 : 2~120까지 모든 소수 찾기) 2~120까지의 숫자 나열 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수를 모두 지움 남아있는 숫자에서 3은 소수이므로 오른쪽에 3을 쓰고 3의 배수를 모두 지움 남아있는 숫자에서 5는 소수이므로 오른쪽에 5을 쓰고 5의 배수를 모두 지움 남아있는 숫자에서 7은 소수이므로 오른쪽에 7을 쓰고 7의 배수를 모두 지움 위 과정을.. 2023. 2. 21.
반응형

티스토리툴바