본문 바로가기

Develop Study160

(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.04.03) Singleton Pattern & Spring Bean 면접 준비와 그리고 채용공고에서 보듯이 싱글톤 패턴을 통한 개발을 할 수 있는지 또는 이에 대한 이해가 있는지를 보기도 해,한번 더 공부하기 위해서 찾아서 정리를 했다.기본적으로 Spring 의 Bean이 싱글톤 패턴이라는 것으로만 알고 있었지만, 실제로 Singleton Pattern과는 조금 다른 점이 있고,그리고 특히, Spring Bean을 싱글톤 패턴으로 개발하는 것이 목적이 아닌 DI를 목적으로 두기 때문에,Singleton Pattern에 대해서 한번 찾아보고 공부했다.싱글톤 패턴 Singleton PatternApplication 내에서 객체를 단 하나만 생성하고, 이를 공유하는 패턴Application 상태를 유지 또는 자원을 전역에서 공유 (또는 logging 등)일종의 전역 변수처럼 .. 2025. 4. 3.
(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.

티스토리툴바