본문 바로가기

Develop Study/Algorithm31

(25.04.12) DP vs LIS (Longest Increasing Subsequence) 최적의 경우의수를 나타내는 형태의 DP 알고리즘을 활용하는 문제인데, 값들의 순서를 기억할 필요는 아니기 때문에,DP로 백준문제에서 통과는 했지만,  LIS 알고리즘 이란 것을 검색하면서 우연히 알게 되어이 문제에 적용을 해보았다.KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.. 2025. 4. 12.
(25.04.05) 이분탐색의 활용 알고리즘을 보다보면, 정말 간단한 이분탐색의 활용도, 문제의 기준점을 어떻게 잡냐에 따라서 생각하는데 한참 걸리기도 한다.특히 이번 문제일 경우에도,  공유기를 멀리 떨어뜨려야 한다 -> 이분탐색을 사용한다 -> 집 순서를 left right mid로 잡아서 를 멀리 떨어 뜨려야한다. -> 그런데 집 거리가 주어진다 -> left right 을 사용하는데 조건이 있다 이런 고민이 있어 한참을 생각했던 문제이다.하지만, 템플릿을 활용하는데에 있지, 집간 거리 자체를 기준점으로 잡는다면 오히려 접근하는데 굉장히 쉬워진다. 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 .. 2025. 4. 5.
(25.03.29) 최대 사각형 구하기 알고리즘 : 히스토그램, DP, 비트마스크 Maximal Rectangle 이란 알고리즘을 비트마스크와 DP를 사용하는 예제로 풀게 되었는데,상당히 이해하는데 많은 시간이 걸렸기에.. 일단 완벽하게 이해를 하는것 보다 이렇게 작동되는지 알고 코드 흐름을 기억하는 수 밖에 없는 것 같다. 추후에 언젠가 보여질 수 있기 때문에 반복해서 코드를 기억해서 작성하기도 했다.Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0".. 2025. 3. 29.
(25.03.27) 비트 마스크의 활용 : DP 심화 비트마스크가 생각보다 빠르게 적용할 수 있는 점을 알게 되어서 DP 부분에 많은 적용을 해보려고 노력하고 있다.  You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers.For example, if nums = [1, 2, 3, 4]:[2, 3], [1, 2, 3], and [1, 3] are good subsets with products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively.[1, 4] and [4] are not good subsets with pro.. 2025. 3. 27.
(25.03.25) 비트 마스크의 활용 : DP DP 알고리즘은 메모이제이션과 이를 누적해서 DP 테이블에 저장하는 재귀 또는 반복을 채택하고 있다.하지만, 어떤 경우에는 저장해야하는 경우의수가 너무 많아 메모리를 너무 많이 사용하거나, 또는 알고리즘 코드를 작성하는데 복잡도가 높아질 수 있다. 이때 이전의 모든 조합 구하는 방식인 "비트마스크"를 활용해서 비교하면서 진행할 수 있다.You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted.Return the number of ways to color the grid.. 2025. 3. 25.
(25.03.24) n개에서 k 고르기 : 재귀 백트래킹 VS 비트마스크 OO 사 코딩 테스트를 진행하면서, 기억에 남는 문제를 복기를 해서 알고리즘을 확인했다.최대한 많은 조합을 만드는 문제는 많은 알고리즘에서 발생을 했지만,만약 그 조합 중에 K개 만큼 특정 갯수가 변수로 주어진 경우에는, 불필요하게 모든 조합을 구하고, 그리고 거기서 k개의 요소를 가진 경우의 수를 모두 고르는 방식은 굉장히 비효율 적이다. 따라서 재귀 트백트래킹을 사용할 수 있지만, 이 보다 효율적인 메모리를 사용해서 재귀를 사용하지도 않고도, 순서 -> 비트로 사용하는 비트마스크 방식을 찾아 이를 적용하고 학습했다. [음료수 맛 조합 문제]여러 종류의 음료수가 주어집니다. 각 음료수는 여러 가지 맛을 가지고 있습니다. 4가지 맛이 있을 경우 음료수의 맛은 이진수(1101, 1000, etc) 로 주어.. 2025. 3. 24.
(25.01.28) DFS 알고리즘의 시간 부족 Time Limit Exceeded 해결 : 자료구조의 활용 DFS의 다중 탐색을 여러번 사용하는 경우, 반복문 단위에서 DFS 횟수를 줄여서 Time Limit을 벗어날 수 있었다.(이분탐색) 하지만 어떤 조건에 맞춱가면서 하나의 DFS를 찾아가는 알고리즘에서 발생하는 것은 탐색해야하는 데이터에 비해, 리소스가 (메모리 등)이 한정적일 때 발생할 수도 있다.즉, 하나의 깊이 탐색 자체가 너무 많은 리로스를 사용하기 때문인데,이 때, List 나 Set 처럼 백트래킹이 있는 알고리즘에서 불필요한 사용이 있을 수 있다. 이 때,  백트래킹을 진행하지 않고 조건에 만족하는 방향만 찾아게 하면서 탐색 속도를 줄이려면 어떻게 해야할까.Questionare given a list of airline tickets where tickets[i] = [fromi, toi] r.. 2025. 1. 28.

티스토리툴바