sen_log

✅ 팰린드롬(palindrome) 이란?팰린드롬은 순방향으로 읽었을 때와 역방향으로 읽었을 때 같은 문자열을 의미한다.문자열뒤집은 문자열결과AApalindromeBBBBpalindromeABDDSSDDBAnot palindromeABDDBAABDDBApalindrome  🤔 문제: 가장 긴 팰린드롬 부분 문자열(palindrome substring) 찾기BANANANA 문자열에서 가장 긴 팰린드롬 부분 문자열은 BANANANA 이다.이렇게 특정 문자열에서 가장 긴 팰린드롬 부분 문자열을 구하려면 어떻게 해야할까? 💡 기존 풀이아마 이 문제가 나오면 문자열의 길이가 O(N^2)의 시간복잡도로 해결할 수 있을 정도로 짧게 주어질 것이다. 그러니 냅다 풀어보자. (1) 팰린드롬의 중심 문자부터 탐색홀수 길..

힙(heap) 힙은 아래 속성을 만족하는 완전 이진 트리(complete binary tree) 기반 자료구조다. 최대 힙(max heap)에서 주어진 노드 C에 대해 P가 C의 부모 노드라면 P의 키(값)는 C의 키보다 크거나 같다. 최소 힙(min heap)에서는 P의 키가 C의 키보다 작거나 같다. Sift Up 연산 힙에 노드를 추가할 때는 sift up 연산이 동작한다. 해당 연산은 리프 노드의 값으로 시작해 값을 위 노드의 값과 연속적으로 교환하여 값을 루트를 향해 경로 위로 이동한다. 위(부모) 노드와 비교해 트리의 속성을 만족할 때까지, 또는 루트 노드에 도달할 때까지 연산을 계속한다. 최소 힙에 노드(값 18)를 추가하는 과정 위 영상에서 새 노드(값 18)은 완전 이진 트리를 만족하기 ..

Union-Find 알고리즘 공통 원소가 없는 두 집합을 서로소 집합이라고 한다. Union-Find 알고리즘은 많은 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하는 자료구조를 나타낸다. 그래프 혹은 트리 자료구조에서 두 노드가 같은 그래프에 속해 있는지 알 수 있다. 서로소 집합은 기본적으로 세 가지 연산으로 구성되어 있다. 1. Make Set 연산 각 원소에 대해 집합을 만드는 연산으로, 자기 자신을 하나의 집합으로 만든다. 따라서 각 집합의 대표자는 원소 자신이 된다. int[] parents = new int[N]; private static int makeSet() { for(int idx = 0; idx < parents.length; idx++) { parents[idx] = i..