본문 바로가기

Python81

LeetCode 20. Valid Parentheses - Python LeetCode 20. Valid Parentheses - Python Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Example 1: Input: s = "()" Output: true Example 2: Input: s = "()[]{}" Output: true Example 3: Inp.. 2020. 9. 21.
LeetCode 234. Palindrome Linked List - Python LeetCode 234. Palindrome Linked List - Python Given a singly linked list, determine if it is a palindrome. Example 1: Input: 1->2 Output: false Example 2: Input: 1->2->2->1 Output: true 문제 정의: 회문(=거꾸로 읽어도 똑같은 결과가 나오는) 연결 리스트인지 확인하라. 풀이 - fast 포인터와 slow 포인터를 설정한다. fast포인터는 slow 포인터보다 2배 빠르다. - 2배 빠르게 움직이는 fast가 연결리스트 끝(null)에 가면 slow 포인터는 중간 노드에 위치한다. - slow 포인터가 위치한 중앙에서 나머지 오른 쪽 노드들의 순서를 거꾸로 뒤집.. 2020. 9. 18.
LeetCode160. Intersection of Two Linked Lists - Python LeetCode160. Intersection of Two Linked Lists - Python Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume the.. 2020. 9. 16.
LeetCode 141. Linked List Cycle 141. Linked List Cycle Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Return t.. 2020. 9. 14.
[LeetCode] Easy 문제 풀이 모음 - Python 1. Two Sum Given an array of integers nums and and integer target, return the indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. 더보기 Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we re.. 2020. 9. 12.
[Python] 자료구조와 알고리즘 기초 - 재귀 알고리즘, 동적 계획법, 연결리스트, 스택, 큐, 이진트리 Contents 선형 배열(Linear Array) 정렬(Sort) 탐색(Search) 재귀 알고리즘 동적계획법 연결리스트 양방향 연결리스트 스택 큐 환형큐 우선순위 큐 이진 트리 이진 탐색 트리 힙 선형 배열(Linear Array) #Python 리스트에 활용할 수 있는 연산들 (1) 리스트 길이과 관계 없이 빠르게 실행 결과를 보게되는 연산들 원소 덧붙이기 .append() 원소 하나를 꺼내기 .pop() (2) 리스트의 길이에 비례해서 실행 시간이 걸리는 연산들 원소 삽입하기 .insert() 원소 삭제하기 .del() #리스트에서 원소 찾아내기 Example 1: Input: L = [64, 72, 83, 72, 54] x = 72 Output: [1, 3] Example 2: Input: L .. 2020. 9. 12.
[Python 자료 구조] 힙 (Heaps) #힙과 이진 탐색 트리 비교 구분 힙 이진 탐색 트리 원소들은 완전히 크기 순으로 정렬되어 있는가? X O 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? X O 부가의 제약 조건은 어떤 것인가? 완전 이진 트리이어야 한다. #연산의 정의 init() : 비어 있는 최대 힙을 생성 insert(item) : 새로운 원소를 삽입 remove() : 최대 원소(root node)를 반환하고 삭제 #배열을 이용한 이진 트리의 표현 class MaxHeap: def __init__(self): self.data = [None] #최대 힙에 원소 삽입 (1) 방법 - 트리의 마지막 자리에 새로운 원소를 임시로 저장 - 부모 노드의 키 값을 비교하여 위로, 비교하고 위로 이동 (2) 복잡도 - 원소의 개수가.. 2020. 9. 11.
[Python 자료 구조] 이진 탐색 트리 (Binary Search Trees) #이진 탐색 트리이진 탐색 트리 (Binary Search Trees) - 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리 (중복되는 데이터 원소는 없는 것으로 가정) #연산의 정의 insert(key, data) : 트리에 주어진 데이터 원소를 추가 remove(key) : 특정 원소를 트리로 부터 삭제 lookup(key) : 특정 원소를 검색 inorder() : 키의 순서대로 데이터 원소를 나열 min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색 #insert(key, data) class Node: def insert(self, key, data): if key < self... 2020. 9. 11.
LeetCode 198. House Robber - Python LeetCode 198. House Robber - Python You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given a list of non-negat.. 2020. 9. 11.
[Python 자료구조] 이진 트리 (Binary Trees) #연산의 정의 size() : 현재 트리에 포함되어 있는 노드의 수를 구함 depth() : 현재 트리의 깊이(또는 높이;height)를 구함 순회(traversal) #이진 트리의 구현 - size() # 이진트리의 구현 - 노드(node) class Node: def __init__(self, item): self.data = item self.left = None self.right = None # 이진 트리의 구현 - 트리(tree) class BinaryTree: def __init__(self, r): self.root = r class Node: # 이진 트리의 크기 - 재귀함수 이용 def size(self): l = self.left.size() if self.left else 0 # 왼.. 2020. 9. 10.

티스토리툴바