본문 바로가기

분류 전체보기

 (133)
백준 19228번 Key storage 문제 요약 NERC 2019 K번이다. 문제에서 정수의 새로운 해시함수를 제시하는데, 해시 방법은 다음과 같다. 숫자 N이 주어지면, N을 2로 나누고, 나눈 몫을 3으로 나누고, 3으로 나눈 몫을 또 4로 나누고, 몫이 0이 될 때까지 나누는 수를 1씩 늘려가며 나눈다. 그리고 그 과정에서 나온 나머지들의 multiset이 해시값이다. 이를 의사코드로 나타내면 아래와 같다. function F(N): x 0;++i) x.insert(N%i) N /= i return x 이런 해시 함수가 있을 때, 어떤 숫자 $k$가 들어오면 그것과 같은 해시값을 가지는 자신 이외의 키의 개수를 출력하는 문제이다. 테스트 케이스는 최대 50000개이며, $ 1 \le k \le 10^{18} $이다. 풀이 수의 범위가 ..
백준 17415번 Huge Integer! 문제 N개의 $(a_i, b_i)$쌍이 주어졌을 때, 다음과 같은 수 $\lambda$를 $K$로 나눈 나머지를 구하는 것이다. $$ \lambda = \underbrace{a_1 \cdots a_1}_{b_1} \underbrace{a_2 \cdots a_2}_{b_2} \cdots \cdots \underbrace{a_{n-1} \cdots a_{n-1}}_{b_{n-1}} \underbrace{a_n \cdots a_n}_{b_n} $$ 각 $a_i$를 $b_i$개씩 이어붙인 숫자를 K로 나눈 나머지를 구한다고 생각하면 된다. 서브태스크 1의 경우 $b_i$의 총 합이 백만으로 나이브한 방식으로 그냥 숫자를 붙여나가면 맞을 수 있다. 서브태스크 2는 당연히 이런 방식으로 접근하면 시간초과가 난다. ..
백준 2844번 자료구조 백준 2844번 자료구조 스플레이트리를 사용해서 문제를 해결할 수 있다. 3번과 4번쿼리는 별 거 없이 스플레이 트리의 기본 연산들로 처리할 수 있다. (split, merge) 1번쿼리 또한 레이지 프롭으로 쉽게 해결이 가능한 쿼리다. 2번 쿼리가 문제다. 스플레이트리로 선형 배열을 다룰 때 서브트리는 각각 어떤 구간을 담당하고 있는 것으로 볼 수 있다. [L, R]을 담당하게 서브트리를 잘 모았다고 치면 이 구간에 들어오는 2번 쿼리는 초항이 X이고 공차가 X이며 길이가 R-L+1인 수열을 [L, R]에 더해주는 것이다. 그러면 이 쿼리를 어떻게 전파할 지 생각할 수 있다. 해당 서브트리의 루트가 위 구간에서 m번째 노드라고 하자. 그러면 왼쪽 서브트리는 [L, m-1]을 담당하고 오른쪽 서브트리는 ..
아이패드랑 컴퓨터 연결하기 화면공유 미러링 맥 계열은 아마 그냥 꼽으면 화면 공유가 되지 않을까 싶다 윈도우에선 lonely인가 유료인지 무료인지 모를 프로그램이 있는데 반응이 느리고 좀 끊긴다. 아이패드랑 컴퓨터랑 같은 와이파이를 공유하고 있는 상황에서 화면 공유를 쉽게 하는 방법이 있다. zoom을 이용한다. 개인 회의 만들고 거기서 화면 공유 누르면 아이패드를 선택할 수 있다. 아이폰도 가능한 것 같다. 하라는대로 잘 하면 컴퓨터에 아이패드 화면이 뜬다. 화질도 좋다. 반응도 빠릿빠릿하다. OBS로 잡는거도 잘 된다.
BOJ 백준 16296번 Daily division BAPC 2018 Preliminary D번 문제이다. 풀이에 앞서 문제를 먼저 정리하자면, 1번 부터 N번까지의 마을이 일렬로 있으며 각 마을에 몇 명이 있는지가 주어진다. 날마다 푸드트럭이 이 마을로 찾아오는데 i번 마을에 찾아왔을 때 1번부터 i-1번 마을까지의 사람들이 왼쪽에 줄을 서고, i+1번부터 N번 마을까지의 사람들이 오른쪽에 줄을 서게 된다. i번 마을에 있는 사람들은 반으로 나눠져 각각 왼쪽 오른쪽에 서며, 사람 수가 홀수일 경우에는 남는 1명은 양쪽 줄의 차이가 적어지는 쪽으로 이동하되, 양쪽 사람 수가 같으면 아무 곳이나 간다. 이 때, 쿼리는 i번 마을의 사람 수가 임의로 바뀌었을 때 양쪽 줄의 차이가 가장 적어지는 푸드 트럭의 위치는 어디인가이다. 트럭이 i번 마을에 왔을 때, ..

티스토리툴바