목록자료구조&알고리즘 (2)

Enthusiasm! Enthusiasm!

재귀 vs 비트마스킹

알고리즘 문제를 풀다 보면 브루트포스 문제들이 자주 나온다. 그중에서도 몇 개를 탐색하는지 정해지지 않고 1개일 때, 2개일 때... N개일 때 전부 탐색해봐야 하는 경우가 있다. 이 때 사용할 수 있는 두 개의 알고리즘을 백준 1182번 문제에 적용하며 비교해 보겠다. https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 재귀 1182번 문제는 주어진 집합(수열)의 모든 부분집합을 구한 뒤 그 합을 계산하여 주어..
자료구조&알고리즘/자료구조 및 알고리즘 2023. 11. 2. 15:09
이진 트리의 순회

대표적인 자료구조인 트리에서 이진트리를 순회하는 방법 및 간단한 코드를 소개하겠다. 이진 트리(Binart Tree) 트리란 각 노드가 부모-자녀 관계를 갖는 계층 구조를 나타낸 데이터 구조이며, 루트 노드에서 시작하여 하위 노드로 분기되는 비선형 데이터 구조이다. 리프 노드를 제외한 각 노드에는 하나 이상의 하위 노드가 있다. 이진트리는 이러한 트리 구조중 각 노드들이 자식을 2개 이하로 가지는 트리를 칭한다. 이진 트리의 순회 이진 트리를 순회하는 방법은 대표적으로 3가지가 있다.(백준 1991) preorder(전위 순회) -(루트)(왼쪽 자식)(오른쪽 자식) 순서로 순회 def preorder(curr): if curr != '.':#현재 노드가 null이 아니면 (여기서는 .을 null이라 가정..
자료구조&알고리즘/자료구조 및 알고리즘 2023. 2. 3. 12:59
이전 Prev 1 Next 다음