![]()
최장 공통 문자열(Longest Common Subsequence)두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제다이나믹 프로그래밍을 통해 해결한다. ex) 백준 9252 LCS 2 https://www.acmicpc.net/problem/9252ACAYKPCAPCAK를 입력받았을때 dp 배열[0, 0, 0, 0, 0, 0, 0][0, 0, 1, 1, 1, 1, 1][0, 1, 1, 1, 2, 2, 2][0, 1, 2, 2, 2, 3, 3][0, 1, 2, 2, 2, 3, 3][0, 1, 2, 2, 2, 3, 4][0, 1, 2, 3, 3, 3, 4]import sysfrom collections import dequest1=[" "]st2=[" "]st1.ex..
![]()
✨서로소 집합(Disjoin-set)공통 원소가 없는 두개 이상의 집합 ✨유니온 파인드(Union-Find)서로소 집합에 대해 union,find 연산을 수행하는 알고리즘Union:두 개의 집합을 하나의 집합으로 병합Find:원소가 어떤 집합에 속해있는지를 판단 EX) 백준 1717 집합의 표현https://www.acmicpc.net/problem/1717 import syssys.setrecursionlimit(1000000)def getparent(n): if(dic[n]==n):return n else: dic[n]=getparent(dic[n]) return dic[n]def unionparent(a,b): n1=getparent(a)..
✨이진탐색(Binary Search)정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식 ✨Python 코드 def binarySearch(array, value, low, high): if low > high: return False mid = (low+high) / 2 if array[mid] > value: return binarySearch(array, value, low, mid-1) elif array[mid] ✨Python bisect 라이브러리import bisectbisect_left(literable, value) # 왼쪽 인덱스를 구하기bisect_right(literabl..
![]()
✨트리(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..
✨우선순위 큐(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..
