본문 바로가기

전체 글

 (159)
백준 5829번 Luxury River Cruise USACO 2013 Open Contest Silver 2번 문제이다. 문제 요약 정점이 N개 주어지고, N개의 정점은 각각 두 개의 간선을 갖는다. 정점의 각 간선은 Left와 Right로 나타내어진다. 길이 M의 Left 혹은 Right로 이루어진 순열이 주어지는데, 1번 정점에서 출발하여 M개의 순열을 K번 반복했을 때 도착하는 정점의 번호를 출력하는 것이 문제이다. 문제의 제한은 $ 1 \le N \le 1000, 1 \le M \le 500, 1 \le K \le 10^9$이다. 풀이 당연히 그래프를 만들고 $ MK $번 간선을 타고 지나가면 시간 초과다. 일단 이걸 줄여보자. 길이 $M$짜리 순열을 $K$번 타고 지나간 뒤의 결과를 찾는 것인데, 하나의 정점에서 간선을 $M$번 타고 가다가 그..
백준 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로 잡는거도 잘 된다.
티스토리 블로그를 따로 만들었습니다. 지금까지 쓴 글들은 다 이곳에도 올리긴 할거다 따로 만든 이유는 대략 두가지인데 깃헙 블로그에는 헛소리같은걸 쓰기가 어려운 느낌.... 그리고 현재 쓰고 있는 테마가 수식쪽이나 태그가 좀 마음에 안들어서 어차피 문서 다 리뉴얼해야 하는데 그럴바에 좀 편한 곳으로 오자. 어차피 글 쓰는 거는 로컬에서 마크다운 렌더링 돌리고 올릴텐데 html에 스크립트 좀 편하게 박을 수 있는게 좋을 거 같았다 일단 여기를 메인으로 하고 테마 바꾸는걸 귀찮아하지 않고 바꾸는 데에 성공하면 깃 페이지쪽이랑 여기랑 같이 올라갈거 같다. 아직 2월 시작도 안했지만 2월엔 SUAPC가 있다. 지금 백준 868솔인데 스플레이 문제들만 이번 주 내로 밀고 대회전까지 가벼운 문제들로 1000솔은 찍어서 구현속도를 올려놔야겠다. 팀연습시..
BOJ 백준 16296번 Daily division BAPC 2018 Preliminary D번 문제이다. 풀이에 앞서 문제를 먼저 정리하자면, 1번 부터 N번까지의 마을이 일렬로 있으며 각 마을에 몇 명이 있는지가 주어진다. 날마다 푸드트럭이 이 마을로 찾아오는데 i번 마을에 찾아왔을 때 1번부터 i-1번 마을까지의 사람들이 왼쪽에 줄을 서고, i+1번부터 N번 마을까지의 사람들이 오른쪽에 줄을 서게 된다. i번 마을에 있는 사람들은 반으로 나눠져 각각 왼쪽 오른쪽에 서며, 사람 수가 홀수일 경우에는 남는 1명은 양쪽 줄의 차이가 적어지는 쪽으로 이동하되, 양쪽 사람 수가 같으면 아무 곳이나 간다. 이 때, 쿼리는 i번 마을의 사람 수가 임의로 바뀌었을 때 양쪽 줄의 차이가 가장 적어지는 푸드 트럭의 위치는 어디인가이다. 트럭이 i번 마을에 왔을 때, ..

티스토리툴바