우서오십쇼

subsequence : 최장 공통 부분 수열 == 즉 연속이 아니어도 순서만 맞으면됨substring : 최장 공통 부분 무자열 == 무조건 연속이어야 한다!! 기본적으로 DP를 이용해서,, 해결한다.  ABCDCCDA 라는 두개의 문자열이 있을 때.... 어떻게 비교해야할까? 1. str1[i] != str2[j]    str1[0]과 str2[0]을 비교해보자! A와 C이므로 다르다,,! 즉 둘 중 하나는 무시해줘야한다    => i랑 j 둘 중 하나만 증가2. str1[i] == srt2[j]    str1[2]과 str2[0]을 비교해보자! C와 C이므로 똑같다..! 즉 같이 취해준다.    => i랑 j를 같이 1 증가해서 비교 ... 이걸 어떻게 dp로 구현해야할까? 2차원 배열을 이용해준다..

공부/자료구조, 알고리즘 2024. 9. 18. 15:07

stack인데, 정렬된 스택을 말한다!=> 위로 쌓는데, 정렬규칙을 만족 못하면 냅다 pop해버리기!  예를 들어,,,,, (bottom) [1, 2, 4, 5] (top) 이라는 스택이 있고, 이 스택의 규칙은 botom 이 때 3을 stack에 push하려고 한다!!! 그러면    top쪽에 5 위에 쌓아버리면 규칙을 만족하지 못한다 pop    top쪽에 4 위에 쌓아버리면 규칙을 만족하지 못한다 pop    top쪽에 2 위에 쌓으면 규칙을 만족한다! push=> (bottom) [1, 2, 3] (top) 이라는 스택으로 바뀌게 된다.  이런 스택의 장점은 뭐가있을까?? 특정 원소 기준으로 왼쪽이나 오른쪽에서 가장 가까운 큰값, 가장 가까운 작은값.. 같은 문제해결에 도움이 된다! [1, 3, ..

공부/자료구조, 알고리즘 2024. 9. 17. 10:50

DAG (Directed acyclic graph == 사이클이 없는 그래프) 가 주어졌을 때, 노드를 정렬하는 방법노드를 일렬로 (linear) 정렬하는 방법이다.    규칙은?? edge의 방향이 무조건 왼쪽 -> 오른쪽 이도록 해준다. 총 3가지 방법이 있다! topoplogical sort는 사이클이 없는 그래프에서만 가능하다 (사이클이 생기면 정렬못함)== 즉 topoplogical sort가 정상적으로 동작하지 않으면, 해당 그래프에 사이클이 있다는 뜻도 된다 Indegree Array모든 노드들의 incoming edge 개수를 저장하고, 여기서 0값을 가지는 노드부터 정렬해주는 방법=> incoming edge를 배열에 저장하므로, 0값을 찾는것 * 모든 vertex마다 이루어짐== 시간복..

공부/자료구조, 알고리즘 2024. 9. 14. 14:10

최소신장트리란?spanning tree(신장트리)란 모든 정점(vertex)를 포함하고, 이 정점들을 연결하는 간선(edge)로 이루어진 tree이다.=> tree라는 조건을 만족시켜야 하기 때문에 모든 정점들이 연결되어있고, 사이클이 없다 (acycle, connected)* 주어진 그래프에서 어떤 edge를 선택하냐에 따라 다양한 spanning tree를 만들 수 있다.* spanning tree의 cost : 선택한 edge들의 모든 weight 합=> spanning tree cost가 가장 작은 spanning tree를 minimun spanning tree (최소신장트리)라고 한다. 신장트리 만들기GENERIC-MST(G, w) A = Ø while A does not form ..

공부/자료구조, 알고리즘 2024. 8. 21. 17:39

큐 : 먼저 들어온게 먼저 나감 (FIFO)우선순위큐 : priority가 높은게 먼저나감 (순서보다 priority가 먼저 고려됨) -> 우선순위큐를 구현하는 방법이 heap인것! (동작만 잘 작동하면 뭐로 구현하든 상관없겠지만) 그냥 heap만들고 우선순위큐라고 하면 되는,,?? 느낌인것같다!! 딱히 차이점을 못느끼겠음 heap을 이용하는 이유는 insert, delete연산에서 heap이 시간복잡도가 가장 낮아서 그렇다.

공부/자료구조, 알고리즘 2024. 5. 25. 20:20

이진트리 -> level간 숫자의 크기순서가 유지되는 자료구조 1. min heap : 상위 레벨(위쪽)에 더 작은 숫자 (더 작은 우선순위를 가진 데이터)가 있음2. max heap : 상위 레벨(위쪽)에 더 큰 숫자 (더 큰 우선순위를 가진 데이터)가 있음-> heap에서 pop을 하면, 무조건 오름차순(또는 내림차순)으로 데이터가 나온다!![데이터 추가]1. heap의 제일 아래에 넣는다2. 재정렬한다 (부모와 비교해서, 위치 바꾸기) [데이터 삭제 (pop)]1. heap의 루트노드를 pop한다2. 루트자리에 heap의 제일 마지막에 있는 데이터를 넣는다3. 재정렬한다 (자식과 비교해서, 위치바꾸기)

공부/자료구조, 알고리즘 2024. 5. 24. 16:37