본문 바로가기

분류 전체보기

(38)

[DP] 도시의 집 DP 연습 문제 : 도시의 집 문제 한 나라에 $n $개의 도시가 있다. 각 도시들은 $1, 2, 3, \dotsc n$ 의 번호가 주어진다. 또한 각 도시들은 $a[i]$개의 집이 있다. $q$ 개의 쿼리가 주어진다면, 도시 $l$ 과 도시 $r$ 사이에 얼마나 많은 집이 있는지 알려주어야 한다. 입력값 : 테스트 케이스 ,$t$ 도시의 개수 , $n$ 각 도시의 집의 개수 $a[i]$ 쿼리의 개수, $q$ 도시 $l$ 과 $r$ 제약: $1

segment tree (세그먼트 트리) 세그먼트 트리 (Segment Tree) 세그먼트 트리란 무엇일까요? 다음의 문제를 통해 알아봅시다. 문제 arr[0 ... n-1] 인 배열이 주어졌을때, $ 0 \leq l \leq r \leq n-1$ 인 $l$ 부터 $r$ 까지 배열의 원소들 합을 구하기. 특정 배열의 원소를 새로운 값 $x$ 로 바꾸기. 다시 말하면 $ 0 \leq i \leq n-1$ 인 상황에서 arr[i] = x 을 해야 합니다. 정답 가장 간단한 솔루션은 $l$ 부터 $r$ 까지 loop 를 만들어서 주어진 범위 내의 배열 원소들의 합을 계산하는 것입니다. 배열의 값을 업데이트 하기 위해서는, arr[i] = x 를 하면 됩니다. 주어진 범위의 합을 계산하는 과정은 $O(n)$ 의 시간복잡도가 걸리고, 값을 업데이트 하기..

행렬 멱법을 이용한 피보나치 값 구하기 행렬 멱법이 무엇인지 모르신다면 여기로 이번 포스팅에서는 행렬 멱법을 이용해 $n$ 번째 피보나치 값을 구하는 방법에 대해 말해보고자 합니다. 피보나치 숫자 피보나치 숫자들은 다들 아시다시피 다음과 같은 정수 나열이죠. $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \dotsc $$ 수식으로 적자면 $F_n$ 는 $n$ 번째 피보나치 숫자라고 정의하겠습니다. 그렇다면, $$F_n = F_{n-1} + F_{n-2}$$ 이 되고, 초기값은 $$F_0 = 0, F_1 = 1$$ 으로 정합니다. 숫자 $n$ 이 정해지면 $n$번째 피보나치 숫자를 출력합니다. 입력값 : n = 2 출력값 : 1 입력값 : n = 9 출력값 : 34 어떤 방법들이 있을까요? 총 4개의 방..

Matrix Exponentiation (행렬 멱법) Matrix Exponentiation (행렬 멱법) Matrix Exponentiation 은 프로그래밍 문제 풀기에서 가장 많이 사용되는 기법입니다. 간단한 질문으로 Matrix Exponentiation 가 무엇인지 알아보겠습니다. $n$ 번째의 피보나치 숫자를 찾기위한 최소의 시간 복잡도는 몇일까요? DP 를 사용하면 $O(n)$ 에 찾을 수 있을것이라 생각합니다. 하지만 Matrix Exponentiation (이하 행렬 멱법) 을 이용하면 $O(log(n))$ 에 찾을 수 있습니다. 혹시라도 행렬 멱법에 관련된 문제를 먼저 풀어보고 싶으신 분은 여기를 들어가보세요. 행렬 멱법을 이용해 $n$ 번째 피보나치 숫자인 $F(n)$을 찾기 위해선 아래와 같은 선형 재귀 수식을 알아야 합니다. $$F(..

[DP] 게임 이기기 DP 연습문제 : 게임 이기기 문제 두 친구 부커와 드윗이 재밌는 게임을 하고있습니다. 턴을 돌아가면서 가방에 있는 빨간공 또는 초록색 공을 꺼냅니다. 각 참가자는 돌아가면서 공을 꺼내고, 절대 다시 넣지 않습니다. 처음 빨간공을 꺼낸 사람이 이깁니다. 부커가 무조건 처음 시작합니다. 만약, 가방안에 아무 공이 없거나 꺼낼 빨간공이 없으면 부커가 이깁니다. 부커가 이길 확률은 어떻게 될까요? 예제 다음과 같은 입력을 받는다고 하겠습니다. 가장 처음 입력은 test case 입니다. 각 라인의 첫번째 숫자는 빨간 공의 갯수, 두번째 숫자는 초록색 공의 갯수 입니다. 3 2 1 1 1 10 0 출력값은 아래와 같습니다. 0.666667 0.500000 1.000000 첫번째 test case 는 빨간 공이 ..

python List 조작법 : Extended Slices 확장된 슬라이스 (Extended Slices) Python 1.4 이후로 부터, list 를 슬라이스할때 syntax 부분에 "step" 또는 "stride" (큰걸음) 이라는 3 번째 옵션을 지원하게 되었습니다. 예를 들어 L[1:10:2],L[:-1:1],L[::-1] 와 같은 syntax를 작성하는것이 가능합니다. 이 "step" 이란것은 무슨 의미일까요? 다음 예제를 통해 바로 이해하실 수 있을겁니다. >>> L = range(10) >>> L[::2] [0, 2, 4, 6, 8] L[:] 은 [0,1,2,3,4,5,6,7,8,9] 를 가지고 있지만 2칸씩 띄어서 List를 만들고자 했으므로 L[::2] 가 되고 [0, 2, 4, 6, 8]가 되네요. 이 "step" 은 음수로도 쓸 수 있습니다..

[DP] Palindrome, 팰린드롬(회문) 만들기 - 2부 DP 연습문제 : Palindrome, 팰린드롬(회문) 만들기 문제 문자열이 하나 주어집니다. 회문을 만들기 위해서 문자열에 삽입해야 하는 최소의 문자 갯수를 찾으세요. 예제 ab : 회문을 만들려면 1개의 문자가 필요합니다.bab aa : 이미 회문이기 때문에 문자가 필요없습니다. 0개 abcd : 회문을 만들려면 3개의 문자가 필요합니다. dcbabcd abcda : 회문을 만들려면 2개의 문자가 필요합니다. adcbcda 여기서 재밌는점은 abcda 를 회문으로 만드는데 필요한 문자 갯수와 bcd 를 회문으로 만드는데 필요한 문자갯수는 같다는 점입니다. (왜그럴까요?) abcde : 회문을 만들려면 4개의 문자가 필요합니다. edcbabcde 문제는 여기서 연습하실 수 있습니다. 정답을 보시기전에 ..

[DP] LCS(Longest Common Subsequence) 찾기 DP 연습문제 : LCS(Longest Common Subsequence) 찾기 동적 계획법에서 굉장히 유명한 문제입니다. 알아두시면 프로그래밍 문제를 푸는데 큰 도움이 되실것이라 생각합니다. 문제 2개의 문자열이 주어집니다. 이 둘의 공통된 가장 긴 문자열을 찾으세요. 공통된 문자열은 서로 왼쪽에서 오른쪽 순으로 이어져야 하며, 한 문자열 내에서 꼭 근접한 문자들을 고르지 않아도 됩니다. 예를 들어 "abc", "abg", "bdf", "aeg", "acefg", .. 등등 은 "abcdefg" 의 부분 문자열입니다. ("gfe" 는 거꾸로 적혔으니까 안됩니다.) 그러니까 $n$ 개의 문자열이 있다면 $2^n$ 개의 부분문자열의 경우의 수가 있습니다. 이 문제는 컴퓨터과학 문제중 가장 기본적인 문제면서..

이전 1 2 3 4 5 다음

티스토리툴바