개발새발 로그

다이나믹 프로그래밍이란 주어진 문제를 한 번의 수행으로 풀도록하는 알고리즘이다. 보편적으로 분할정복기법을 사용하는데 이 기법은 동일한 수행을 다시해야한다는 단점이있다. 이러한 대표적인 예시가 피보나치수열 피보나치 수열에서 F(15)를 구하려면 F(14)와 F(13)을 구해야한다. F(14)를 구하려면 F(13)과 F(12)를... 이런식으로 나아간다. -> 비효율적 이럴 때 예를 들어 F(12)가 중복적으로 나오는 경우가 생길 것이다. 이렇게 되면 동일한 데이터를 반복적으로 불필요하게 실행하게 된다. ->단순하게 분할정복기법을 사용하면 안된다. ->이럴 때 다이나믹 프로그래밍 기법을 사용해야한다. 다이나믹 프로그래밍은 다음의 예시에 사용가능하다. -큰 문제를 작은문제로 나눌 수 있다. -작은 문제에서 구..

이진트리는 데이터의 탐색속도 증진을 위해 사용하는 구종비니다. 이때 루트에서 자식노드로 접근하는 방법은 포인터를 이용하는 방식과 DFS를 이용하는 방식이 있습니다. 만약 완전이진트리가 아닌 자식노드가 하나씩 없는 이진트리라면 배열로 표현하기 어렵고, 탐색할 때도 불필요한 메모리가 사용됩니다. 이진 트리를 순회하는 방법은 크게 세가지 방법이 있다. -전위순회 : 루트 → left → right -중위순회 : left → 루트 → right -후위순회 : left → right → 루트 포인터를 이용해서 완전이진트리가 아닌 구조에서도 안정적으로 작동할 수 있다. JS에서는 클래스를 이용해야한다. const preOrder=[]; const inOrder=[]; const postOrde=[]; //부모 자식..

크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다. 즉 최소 비용 신장트리를 만들기 위한 대표적인 알고리즘이다. 예를 들어 각 도시를 도로를 이용해 연결해 모든 도시가 연결되도록 할 때 최소한의 비용을 구하는 것이다. 먼저 신장트리에 대해 알아보자 신장 트리 (Spanning Tree) 이러한 그래프가 있다고 가정하자 이 그래프를 연결하는 최소 연결부분만 사용한다면 아래와 같이 나온다. 더 많은 경우가 있지만 생략했다. 최소 연결이란 간선의 수가 가장 적다는 것을 의미한다. 그래프에서 일부 간선을 선택해서 만든 트리. 모든 정점들이 연결 되어 있어야하고 사이클을 포함하면 안된다. 하나의 그래프에는 여러개..

서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 합집합(union)과 찾기(find) 연산으로 구성 쉽게보면 현재 연결되지않은 노드들이 있는 것이다. 그래서 공통된원소가 없어 서로 합쳐야하는 것이다. 그림을 보면 현재 부모값과 노드값이 똑같다. 이제 이걸 {1 , 2} 두 원소를 합칠 것이다. 합치게되면 1 의 parent값 1과 2의 parent값 2를 같게해서 연결되게 할것이다. -> 부모 값이 같음으로써 서로 연결되어 합쳐 졌다는 의미가 된다. 즉 위와같은 경우가 되는것이다. 2의 부모값을 1로 바꿔준다. -> 바꿔줄 때 부모 값이 작은 쪽이 부모가 되도록 해야한다. 이제 합..

누적합은 구간의 누적합을 구하는 문제 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우O(n^2)의 시간복잡도를 갖기 때문에 입력의범위가 클 때 사용할 수 없습니다. 하지만 Prefix sum방식을 사용하면 O(N)으로 해결 할 수 있습니다 수열이 주어지고 어떤 구간의 값의 합을 구해야 할 때 사용한다.