본문 바로가기

전체 글38

[Leetcode 85번 문제] Maximal Rectangle 문제 요약0과 1로 이루어진 2차원 매트릭스가 주어진다. 이 안에서 직사각형의 성질을 만족하는 가장 큰 넓이를 구하여라입력2차원 배열이 주어지고, 행과 열의 최대 크기는 200씩이 문제를 푸는 정공법은 스택이라고 할 수 있을 것 같다. 그런데 난 이 문제를 처음 봤을때 때 DP를 떠올렸다. 정확히 왜 그랬냐 하면DP문제는 겹치는 부분이 존재한다. 피보나치 수열 같이 a(n) = a(n - 1) + a(n - 2) 가 대표적 이 문제에서도 역시 그런 겹치는게 보였기 때문이다.동적프로그래밍은 굉장히 많은경우에 문제의 답이 되는 경우가 많다. 많은 경우에 백트래킹보다 빠르고 경우의 수를 탐색할때 최적일 때가 많아서 그렇다.하지만 그만큼 DP도 한가지 방법만 있는게 아니라 여러가지 접근이 가능하기에 어떻게.. 2024. 4. 19.
백준 9527번 1의 개수 세기 문제풀이 입력 두 자연수 A, B (1 ≤ 10^16) 입력범위가 굉장히 넓다. 전체적인 범위에서 어떤 수를 이진수로 바꾸고 그 차이에 대해서 바깥의 1을 컨테이너라고 지정하고 그게 그 모든 경우의수가 쉽게말해서 16부터 31 사이의 수라면 바깥 1은 15번 등장하고 나머지는 모든 경우의 수의 절반 말그대로 888 등장할것임 출력 어떤 두 수 사이의 수들에 대해서 1이 등장하는 횟수를 출력해라. 과정 입력값이 10 ^ 16까지기 때문에 모든 수를 늘려가면서 세는것은 엄두도 못 낼 일 다만 직관적으로 이해하기 쉬운건 1이 등장하는데 패턴이 있을 것이라는 점이다. 예를들어 0000(2)부터 1111(2)까지 1이 등장하는 횟수는 당연히 32회다.중복 순열의 총 경우의수에 각각의 자리수가 등장할 확률은 1/2를 곱하면.. 2024. 3. 22.
영화 롤리타(1962) 리뷰 욕망과 사랑의 불가분성 ★★★★☆ 이 리뷰는 스포일러를 포함하고 있습니다. 영화 는 블라디미르 나보코프의 동명의 소설을 원작으로 한 스탠리 큐브릭의 촉 장편영화이다. 스스로 문제가 되는 걸 피하지 않는 작품이 흔히 그렇듯 많은 비판을 받았지만 한편으론 아직 2001 스페이스 오디세이, 풀 메탈 재킷과 같은 신인감독 스탠리 큐브릭에 대한 찬사와 기대 또한 쏟아졌다. 이런 극단적인 소재를 가진 작품은 사람들로 하여금 풍자극이나 교훈극을 떠올리게 한다. 이 두 가지의 형식은 모두 해당 소재 자체를 비판하고 사람들로 하여금 멀리하게 하기 위한 특징을 가지고 있다. 그리고 롤리타 역시 이런 풍자극, 교훈극의 구성을 가지고 있다. 특히 이후에도 시계태엽 오렌지, 닥터 스트레인지러브 같은 완성도 높은 풍자극을 만들어.. 2022. 8. 21.
하나의 이상이란 허구, 도덕의 기원과 실체. 이 글은 프리드리히 니체(Friedrich Wilhelm Nietzsche) 도덕의 계보학(1887)과 안티크라이스트를 바탕으로 제작하였습니다. 현대사회는 그 자체로 인간 욕망의 풍경화라고 할 수 있다. 그래서 이 사회는 우리를 끔찍하게 엮어 놓고있다. 현대 사회의 이명이 초연결의 사회라는건 명백하고 그 연결 역시 개개인의 욕망이 내린 방향성이다. 하지만 사실 우리 개인 모두에게 남은 각각이 모두 거대하고도 어두운 심해속과 같아야 한다. 우린 절대 남이 될 수 없기 때문이다. 본디 인간의 삶은 자신 이외의 혼돈, 카오스에 대한 자신의 로고스와 파토스의 발현들에 지나지 않는다. 하지만 우리 용기없는 인간들은 이 카오스를 견디지 못했다. 우리는 연결될 뿐만 아니라 서로 같아지기도 원한다. 이 카오스를 눈앞에.. 2022. 5. 3.

티스토리툴바