Algorithms13 가장 긴 증가 부분 수열(LIS) 알고리즘 가장 긴 증가 부분 수열(LIS) 알고리즘가장 긴 증가 부분 수열(Longest Increasing Subsequence, LIS)은 컴퓨터 과학에서 중요한 문제 중 하나로, 주어진 배열에서 증가하는 순서로 이루어진 가장 긴 부분 수열을 찾는 문제입니다. 이 문제는 다양한 분야에서 응용될 수 있으며, 특히 최적화 및 데이터 분석에 유용합니다.문제 정의주어진 배열 A=[a1,a2,…,an]에서 LIS는 다음 조건을 만족하는 가장 긴 부분 수열 S=[s1,s2,…,sk]입니다:s1S는 A의 부분 수열입니다.접근 방법LIS 문제를 해결하는 여러 가지 방법이 있습니다. DP를 활용한 알고리즘: O(n^2) 이분 탐색을 활용한 알고리즘: O(n log n) DP를 활용한 LIS 알고리즘임시 배열 생성.. 2024. 11. 14. [Programmers] 가장 큰 정사각형 찾기 가장 큰 정사각형 찾기난이도: level 2정답률: 38% (2024.07.31 기준)완료한 사람: 6359명 (2024.07.31 기준)문제 설명1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 이 글에서는 주어진 2D 배열 board에서 1로 구성된 가장 큰 정사각형의 넓이를 찾는 방법을 설명합니다. 이 문제는 동적 계획법(Dynamic Programming)을 이용하여 효율적으로 해결할 수 있습니다. 아래는 Python으로 작성된 해결 코드와 그에 대한 상세한 설명입니다. 코드구현d.. 2024. 8. 1. [Programmers]N-Queen N-Queen난이도: level 2정답률: 38% (2024.07.31 기준)완료한 사람: 6359명 (2024.07.31 기준)제한사항퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.n은 12 이하의 자연수입니다.입출력 예시)nresult11203042 해당 문제는 백트래킹을 이용하여 문제를 풀어봤습니다. 고려할 점2차원의 보드이지만 배열의 index를 행이라고 생각하면 1차원 배열로 표현이 가능하다.2가지 기능을 구현해야 한다. 1st. 퀸을 배치하는 모든 경우의 수 구하기 -> 백트래킹2nd. 경우의 수 중에 조건을 만족하는 경우 찾는 부분 -> 2가지 1. board를 이용한 풀이해당 풀이는 n이 짝수일 경우에 가운데를 기준으로 대칭이 되는 경우가 있으므로 고려해서 짜면 시간 .. 2024. 7. 31. d-ary Heaps 힙(Heap)은 컴퓨터 과학에서 중요한 데이터 구조 중 하나이며, 우선순위 큐 등 다양한 응용 분야에서 활용됩니다. 여기서는 이진 힙(Binary Heap)의 확장인 d-ary 힙에 대해 살펴보겠습니다. d-ary 힙은 각 노드가 최대 d개의 자식을 가질 수 있는 구조로, 일반적으로 우선순위 큐와 관련이 있습니다. 1. d-ary 힙의 기본 개념: d-ary 힙은 이진 힙을 확장한 것으로, 각 노드가 최대 d개의 자식을 가질 수 있습니다. 이는 힙의 트리 구조를 보다 다양하게 만들어주며, 일부 연산에서 효율성을 향상시킬 수 있습니다. 2. d-ary 힙의 특징: 자식의 순서: 각 노드의 자식들은 왼쪽부터 오른쪽으로 순서대로 나열됩니다. 힙 속성 유지: d-ary 힙도 최대 힙이나 최소 힙으로 구현 가능하.. 2024. 1. 11. 이전 1 2 3 4 다음
