Algorithms과 자료구조19 파이썬 알고리즘(소수찾기 에라토스 테네스 체) https://www.acmicpc.net/problem/11653 import sys import math input = sys.stdin.readline N = int(input()) # 에라토스 테네스의 채 로 소수들을 찾는다. def prime_num(n): arr = [True]*(n+1) prime_arr = [] for i in range(2, int(math.sqrt(n)+1)): if arr[i]==True: j=2 while(i*j) 2022. 2. 6. 해시테이블 해시테이블이란? 해시테이블 , 해시맵, 해시 표는 키를 값에 매칭할 수 있는 구조인 연관 배열 주가에 사용되는 자료구조이다. 해시테이블은 해시함수를 사용하여 index 를 bucket이나 slot의 배열로 계산한다. 버킷/ slot은 실제 값이 저장되는 장소이다. 왜 사용할까? 빠르게 데이터를 검색할 수 있다고 한다. 빠른 검색속도를 제공하는 이유는 내부적으로 배열을 사용하여 데이터를 저장하기 때문이다. 특정 값을 search하는데 데데이터 고유의 인덱스로 접근게 되어 평균적인 case에 대해 time complexity가 O(1)이 된다. 하지만 데이터의 충돌이 발생하는 경우 Chaining에 연결된 리스트 까지 검색해야 할 경우 O(N)까지 시간복잡도가 증가 할 수 있다. (Chaining은 아래에서.. 2022. 1. 16. 프로그래머스_42587 프린터_파이썬풀이(스택,큐) 문제 : 프린터의 중요도가 적힌 리스트가 주어지고 원하는 프린트 하고자 하는 파일의 인덱스가 주어졌을 때 몇 번째로 프린터 되는지 출력하는 문제. 나의 풀이 : from collections import deque def solution(priorities, location): answer = 0 priorities = deque(priorities) #popleft를 쓰기위해 deque로 형변환 while True: maxpr = max(priorities) a=priorities.popleft() if a==maxpr: #왼쪽부터 순서대로 뽑은 값이 max라면? if location == 0: answer+=1 break else : answer+=1 location-=1 else : location.. 2021. 12. 15. RB_TREE(삭제) 레드 블랙 트리의 삭제의 경우 삽입보다 다소 복잡하다고 책에서 말한다. (다소?...) 머리가 나빠 동기들이 많이 도와줬음에도 혼자 이해하는데 2일이 꼬박 걸린 듯하다. 아무튼 내가 이해한 바를 정리해 보려 한다. 삭제의 시간 복잡도 삭제도 삽입과 마찬가지로 O(logN)의 시간 복잡도를 가진다. RB트리의 삭제 우선 노드의 삭제는 두 가지 방법으로 진행할 수 있다. 1. 삭제하려는 노드가 (Z)라면 Z의 오른쪽의 최솟값을 이동시켜 값을 보완한다. 2. Z의 왼쪽의 최댓값을 Z의 위치로 이동시켜 값을 보완한다. 그 이유는 RB트리 또한 이진트리의 원칙을 기본으로 하기 때문에 삭제되는 노드의 오른쪽(삭제되는 노드보다 큰 값들의 집합)의 가장 왼쪽(최솟값)을 노드로 이동시킨다면 이진트리의 원칙이 깨지지 않고.. 2021. 12. 8. RB_Tree(레드블랙트리)_삽입 이진트리의 경우 계속하여 큰값이나 작은값이 들어올 경우 노드가 한쪽으로 치우칠 수 가 있다. 이경우 특정 key값을 탐색하는데 시간이 늘어나는 단점이 있으며 이를 보완한 것이 자가균형이진탐색트리 Red-Black Tree이다. RBtree의 특성 모든 노드의 색은 빨간색 혹은 검은색이다. 루트 노드는 검은색 이어야 한다. 모든 리프노드는 루트노드와 같은 검은색이다. 빨간색 노드의 자식은 모두 검은색이다. 루트노드에서 리프노드까지 가는 경로상 만나는 검은색 노드의 수는 모두 동일하다 RBtree 시간 복잡도 O(logn): RBtree 삽입 기본적 삽입은 이진트리의 삽입과 같다 그러나 삽입과정에서 루트 노드는 검은색이어야 하며 빨간색 노드의 자식은 검은색이어야 한다는등 조건이 있어 RB트리의 특성을 만족하.. 2021. 12. 5. LCS(Longest Common Subsequence) 최장 공통 부분 수열 최장 공통 부분 수열 (Longest Common Subsequence) 문제란? 주어진 여러개의 수열 모두 부분수열이 되는 수열중 가장 긴 것을 찾는 문제이다. 이 문제와 아래 최장공통 부분 문자열 문제와 혼동하면 안된다. 최장 공통 부분 문자열(Longest Common Substring) 문제란? 주어진 여러개의 문자열 모두 부분수열이 되는 문자열 중 가장 긴 문자열을 찾는 문제 예시 가나다라마바사 가하나카마바사 LCSubsequence 가나다라마바사 가하나카마바사 LCSubstring 가나다라마바사 가하나카마바사 LCS 문제는 더 작은 '부분문제'로 나뉠 수 있고 이것을 반복해 더 간단한 부분문제로 쪼갤 수 있다. 즉 동적 프로그래밍 문제풀이기법으로 접근될 수 있다. 부분문제는 수열이 짧아질 수록.. 2021. 11. 26. 이전 1 2 3 4 다음
