![]()
✨트리(tree) 트리 구조란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 최상위노드: 루트노드 자식없는 노드: 잎 노드 잎노드가 아닌 노드: 내부 노드 ✨트리순회 전위 순회(preorder traversal),중위 순회(inorder traversal),후위 순회(postorder traversal)로 나뉘어진다. ex) 백준 1991번 트리순회 https://www.acmicpc.net/problem/1991 import sys class Node(): def __init__(self,v,l,r): self.value=v if(l=='.'):self.left=None else:self.left=l if(r=='.'):self.r..
✨ 투 포인트(Two-Point Algorithm) 2개의 포인터를 이용하여 배열속 원하는 값을 찾을수있다. O(N)의 시간 복잡도를 가진다. ex) 백준 두 수의 합 https://www.acmicpc.net/problem/3273 import sys n=int(sys.stdin.readline().rstrip()) li=list(map(int,sys.stdin.readline().rstrip().split(" "))) correct=int(sys.stdin.readline().rstrip()) li.sort() left_p=0 right_p=n-1 count=0 while True: if(li[left_p]+li[right_p]==correct): #같을때 left_p+=1 count+=1 elif(..
![]()
✨깊이 우선 탐색(DFS, Depth First Search) 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘 ex)백준 알고리즘 수업 - 깊이 우선 탐색 2 https://www.acmicpc.net/problem/24480 import sys from collections import deque visited=[] need_visit=deque() N,M,R=map(int,sys.stdin.readline().rstrip().split(" ")) visited_dic={i:0 for i in range(1,N+1,1)} graph={i:[] for i in range(1,N+1,1)} #무방향이므로 a,b 서로의 인접노드 추가 for i in range(M): a,..
![]()
✨그래프(Graph) 그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex: 정점 edge: 정점과 정점을 연결하는 간선 ✨그래프(Graph)종류 무방향그래프 그래프를 연결하는 간선에 방향이없다. 방향그래프 그래프를 연결하는 간선에 방향이있다. 가중치 그래프 그래프를 연결하는 간선에 코스트가있다. 완전그래프 그래프의 모든 정점이 간선으로 연결되있다. ✨그래프(Graph)구현 인접행렬 그래프의 정점을 2차원 배열로 표현 연결됨:1 (가중치 그래프일 경우 가중치로 표현) 연결안됨:0 O(n^2) 시간 복잡도 인접리스트 그래프의 노드를 리스트로 표현 각정점에 대한 인접정점을 순차적으로 표시 O(n) 시간 복잡도 🎈참고자료 https://80000coding.oopy.i..
모델링 특징 추상화: 일정한 형식에 맞춰 표현 단순화: 제한된 표기법이나 언어로 표현 명확성: 이해하기 쉽게 표현하기 위해 애매모호함 제거 유의점 중복 : 중복되는 정보 최소화 비유연성: 데이터 정의와 데이터 사용 프로세스 분리 비일관성: 데이터들간 상호연관 관계에 대한 명확한 정의 스키마 외부스키마:각 사용자 단계의 DB 스키마. (사용자 관점)(개개인 사용자) 개념스키마:조직 전체의 DB 스키마. (설계자 관점)(모든 사용자) 내부스키마:물리적으로 데이터가 저장되는 스키마. (개발자 관점) (물리적 저장 구조) 모델링 3단계 개념적 데이터 모델링: 추상화 논리적 데이터 모델링: 속성,관계표현,속성 물리적 데이터 모델링:성능, 저장 등 물리적인 성격 데이터 독립성 논리적 독립성:개념 스키마가 변경되도 ..
✨우선순위 큐(Priority Queue) 평범한 큐나 스택과 비슷한 축약 자료형이다. 각 원소들은 우선순위를 갖고 있다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 자료구조 힙을 통하여 구현된다 ✨힙(Heap) 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙' 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙' ✨Python PriorityQueue from queue import PriorityQueue q=PriorityQueue() q.put(5) q.put(3) q.put(4) print(q.get()) #출력: 3 (우선순위,값)튜플 형태 추가 from q..
![]()
✨ 그리디 알고리즘(Greedy algorithm)최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 ex)백준 1715번https://www.acmicpc.net/problem/1715 import sysimport heapqsum=0hq=[]for i in range(int(sys.stdin.readline().rstrip())): heapq.heappush(hq,int(sys.stdin.readline().rstrip())) sum=0if(len(hq)==1):print(0)else: while hq: a=heapq.heappop(hq) b=heapq.heap..
✨누적 합(Prefix sum) 주어진 배열에서 각 위치까지의 합을 미리 계산하여 배열에 저장해 놓는 알고리즘 빠른응답속도 추가 메모리 사용 ex) 백준 11659번 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 import sys N,M=map(int,sys.stdin.readline().rstrip().split(" ")) li=list(map(int,sys.stdin.readline().rstrip().split(" "))) li2=[0] sm=0 for i in li: sm+=i li2.append(sm) for i in range(M): a,b=map(int,sys.stdin.readline().rstrip().split(" ")) sys.stdout.w..
