스택으로 쌓아놓은 수열에서 조건을 만족하는 값들이 언제부터 다 나오는가?

17162번: 가희의 수열놀이 (Small) 여러개의 쿼리가 주어지는데,  1. 스택의 맨 뒤에 숫자를 추가 2. 스택이 비어있지 않으면 맨 뒤의 원소를 제거 3. 맨 뒤에서부터 최소 몇개의 수를 선택해야, 이들을 mod로 나누었을때 0,1,2,..,mod-1이 최소 1개 이상 나타나는가? 예를 들어 [2,3]인 경우 4로 나누면 나머지는 [2,3]인데, 여기서 0,1이 없으므로 -1 [2,3,1,4]인 경우 4로 나누면 나머지는 [2,3,1,0]인데 여기서 0,1,2,3이 모두 나왔으므로 4 -----------------------------------------------------------------------------------------------------------------------..

  • format_list_bulleted 자료구조(스택,큐,해시맵)
  • · 2025. 2. 27.
  • textsms

인접한 원소의 곱의 합이 최대가 되도록 수열을 만드는 방법

16209번: 수열 섞기 수열 a1,a2,...,an이 주어질때 인접한 원소들의 곱 a1a2 + a2a3+... + an-1an이 최대가 되도록 수열을 섞고 싶다 그렇게 섞은 수열 하나만 구한다 ----------------------------------------------------------------------------------------------------------------------------------------------------------- 적어도 양수는 양수끼리, 음수는 음수끼리 곱해야 한다는 것을 생각할 수 있다 또한 절댓값이 큰 것끼리 곱해야 커진다는 것도 생각할 수 있다 양수 그룹에서 큰 값들을 먼저 찾아서 a1 > a2 > .... > an이라고 한다면... a1 a..

  • format_list_bulleted 그리디 알고리즘
  • · 2025. 2. 20.
  • textsms
경기장 일렬 좌석에 앉을 때 사람을 지나치지 않고 전부 앉는 방법의 수

경기장 일렬 좌석에 앉을 때 사람을 지나치지 않고 전부 앉는 방법의 수

29313번: Стадион (acmicpc.net)  일렬로 된 N개의 좌석이 있는데 사람이 양쪽으로 들어가서 좌석에 앉을 수 있다고 할때,  어떤 사람이 이미 앉은 사람을 지나치지 않고 N명이 모두 앉는 방법의 수를 구하는 문제 예를 들어 3명이 앉는다고 해보면 이렇게 4가지가 있다    N개의 자리가 있을 때 _ _ _ _ _ _ ... 첫번째 자리에 먼저 앉으면 1 _ _ _ _ _ ... 나머지 N-1개의 자리는 고정적으로 2,3,4,5,6,... 으로 1가지 = N-1C0가지 결정된다 두번째 자리에 먼저 앉으면 _ 1 _ _ _ _ .... 1의 왼쪽 자리 _ 를 N-1명중 1명을 결정시키면 1의 오른쪽은 무조건 자동으로 결정되므로... N-1C1가지 왜냐하면 1의 왼쪽에 3을 앉히면 3 1 ..

  • format_list_bulleted 조합론
  • · 2024. 7. 26.
  • textsms
키타마사 법(kitamasa method, きたまさ法)에 대한 공부

키타마사 법(kitamasa method, きたまさ法)에 대한 공부

1. 키타마사 법(kitamasa method) 수열 an의 점화식을 이전의 몇개 항으로 정의한다면, 귀납적 정의, 재귀적 수열 등으로 부른다. an=∑i=1kwian−i 이런 형태로 정의되는 대표적인 수열은 피보나치 수열이다. an=an−1+an−2,w1=w2=1,k=2 이 피보나치 수열의 가장 빠른? 해법중 하나는 행렬을 이용하는 방법이다. https://deepdata.tistory.com/760 행렬을 이용한 피보나치 수열 문제의 해법 1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. an+1=an+an−1 $a_{n} = a_{n} + ..

  • format_list_bulleted 대수학
  • · 2023. 8. 27.
  • textsms

[Java]running median 복습하면서 자바로 구현해보기

1. running median 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median (tistory.com) 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median 1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결 deepdata.tistory.com 1) 최대힙과 최소힙 2개를 초기화 2) 최대힙의 원소의 수와 최소힙의 원소의 수가 동일하다면, 최대힙에 수를 넣어주고 3) 최대힙의 원소의 수가 최소힙의 원소의 수 + 1이라면, 최소힙에 수를 넣어준다. 즉 최대힙 > 최소힙 > 최대힙 > 최소힙 >....으로 번갈아가면서 수..

  • format_list_bulleted 자료구조(스택,큐,해시맵)
  • · 2023. 3. 21.
  • textsms