본문 바로가기

Python

 (36)
[좌충우돌, 파이썬으로 자료구조 구현하기] 이진트리에 키 삽입하기 문제 [https://www.geeksforgeeks.org/insertion-in-a-binary-tree-in-level-order/?ref=lbp] 이진트리와 키가 주어질 때, 이진트리의 레벨 순서에서 가장 먼저 사용할 수 있는 위치에 키를 삽입하는 함수를 만들어라. 풀이 문제에서 "레벨 순서"에서 가장 먼저 사용할 수 있는 위치라고 했으니 레벨 순서로 푼다. 위 그림의 예시를 보면 11번의 오른쪽 자식이 레벨순서에서 가장 먼저 사용할 수 있는 위치이다. def insert_key(tree,key): new_node = Node(key) if not tree.root: tree.root = new_node else: q = [tree.root] while q: node = q.pop(0) if no..
[좌충우돌, 파이썬으로 자료구조 구현하기] 이진트리 표현하기 (연결리스트) class Node: def __init__(self,data): self.data = data self.left = None self.right = None class Tree: def __init__(self,node=None): self.root = node if __name__ == '__main__': tree = Tree(Node("A")) tree.root.left = Node("B") tree.root.right = Node("C") tree.root.left.left = Node("D") tree.root.left.right = Node("E") tree.root.right.left = Node("F") tree.root.left.left.left = Node('G&..
[좌충우돌, 파이썬으로 자료구조 구현하기] 순회 함수 만들기 (스택) 스택을 이용한 전위 순회 기본 원리는 재귀함수를 호출하는 코드 대신 방문할 노드를 스택에 저장하는 코드로 바꾸고, 스택이 빌 때까지 반복문으로 순회하는 것이다. 결과를 담을 빈 리스트와 스택 리스트에 루트 인덱스인 0으로 초기화한다. 빈 스택이 아니면 계속 반복한다. 스택에서 인덱스 꺼내 parent에 대입 현재 인덱스의 노드를 방문(리스트에 추가)한다. 왼쪽과 오른쪽 노드의 인덱스를 구한다. 각 노드의 인덱스가 배열의 크기보다 작고, 노드의 값이 None이 아니면 스택에 추가한다. 스택은 마지막 원소를 먼저 꺼내므로, 오른쪽ㅈ 보다 왼쪽을 먼저 방문하려면 오른쪽 노드의 인덱스를 먼저 넣어야 한다. 결과 리스트 반환 def preOrderByStack(tree): if not tree: return []..
[좌충우돌, 파이썬으로 자료구조 구현하기] 순회 함수 만들기 (재귀) 재귀함수를 사용하여 전위 순회, 중위 순회, 후위 순회를 구현해보자. 전위 순회 함수 만들기 현재 노드 방문 -> 왼쪽 노드 방문 -> 오른쪽 노드 방문 위 순서를 재귀적으로 진행하면 된다. def preOrder(tree,i=0): if i >> tree = ["A", "B", "C", "D", "E..
[좌충우돌, 파이썬으로 자료구조 구현하기] 이진트리 표현하기 (배열) 파이썬으로 이진트리를 표현하는 방법에는 배열로 이용하는 것과 연결 리스트를 이용하는 것이 있다. 트리의 값을 레벨 순서대로 배열에 넣어보면 다음과 같다. 인덱스 0 1 2 3 4 5 6 7 값 A B C D E F None G 루트 A의 인덱스는 0 A의 왼쪽 자식인 B의 인덱스: 2 * 0 + 1 = 1 A의 오른쪽 자식인 C의 인덱스: 2 * 0 + 2 = 2 B의 인덱스는 1 B의 왼쪽 자식인 D의 인덱스: 2 * 1 + 1 = 3 B의 오른쪽 자식인 E의 인덱스: 2 * 1 + 2 = 4 C의 인덱스는 2 C의 왼쪽 자식인 F의 인덱스: 2 * 2 + 1 = 5 D의 인덱스는 3 D의 왼쪽 자식인 G의 인덱스: 2 * 3 + 1 = 7 부모 노드의 인덱스가 n일 때, 왼쪽 자식 노드의 인덱스는 2..
[좌충우돌, 파이썬으로 자료구조 구현하기] 트리 구현하기 트리는 족보의 가계도나 조직도, 마인드맵을 생각하자. 어려운 말로는 그래프(Graph)의 한 형태로서, 순환(cycle)이 없는 연결 그래프라 한다. 구성 노드(Node): 트리를 구성하는 기본 요소, 값(key or data)과 하위 노드를 가리키는 포인터(pointer)를 가진다. 간선(Edge): 노드와 노드를 연결한 선(Link) 위 그림처럼 트리는 루트(Root)에서 시작한다. 루트: 부모 노드가 없는 최상위 노드 부모(parent)노드: 자식(child) 노드를 가진 노드 자식(child)노드: 부모 노드의 하위 노드 형제(siblings)노드: 부모가 같은 노드 리프(leaf)노드: 자식이 없는 노드 서브 트리(sub tree): 특정 노드를 루트로 생각할 때 생기는 트리 기타 용어 크기(s..
[좌충우돌, 파이썬으로 자료구조 구현하기] 영어 끝말 잇기 문제 1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해 주세요. 예시 n = 3, words = ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] result = [3, 3] n = 5, words = ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish",..
[좌충우돌, 파이썬으로 자료구조 구현하기] 합이 0인 부분 배열 중 가장 긴 것 찾기 문제 양의 정수와 음의 정수의 배열이 있다. 합이 0인 부분 배열 중 가장 긴 배열의 길이를 구하라. 예시 입력: A = [15, -2, 2, -8, 1, 7, 10, 23] 출력: 5 (합이 0인 부분 배열은 -2 2 -8 1 7) 풀이 1. 이중 반복문 풀이 def largestSubArrayWithZero(arr): result = [0 for _ in range(len(arr))] if len(arr) == 1: return 1 for i,num in enumerate(arr): subArray = [num] for j in range(i+1,len(arr)): num2 = arr[j] subArray.append(num2) if sum(subArray) == 0: result[i] = len(s..

티스토리툴바