1. 구조 binary indexed tree는 이름에서부터 2진법 인덱스 구조를 이용해서 구간 합 문제를 효과적으로 처리하기 위한 자료구조 point update, range sum을 효과적으로 처리하기 위한 자료구조 다음 그림이 binary indexed tree의 구조를 잘 보여주고 있다. 1) zero index가 아니라 binary indexed tree에서는 편의상 one index로 바꿔서 생각함 2) 데이터가 N개면 tree의 크기도 N이다. 3) tree의 각 index에는 어떤 값들이 저장되어 있는가? 1번 index에는 0번째 원소 1이 있고, 2번 index에는 0번 + 1번째 원소의 합 1+3 = 4가 저장 마찬가지로 3번 index에는 2번째 원소 11이 저장 4번 index에는..
1. 문제 29726번: 숏코딩의 왕 브실이 (acmicpc.net) 29726번: 숏코딩의 왕 브실이 숏코딩의 왕 브실이는 오늘도 숏코딩을 한다. 브실이가 제출한 코드 길이가 수열 $A_1, A_2, \cdots, A_N$로 주어진다. 브실이의 행복도는 자신의 코드 길이에 대한 수열에 따라 달라지는데, 현재 수열 www.acmicpc.net 2. 풀이 $$\sum_{i = 1}^{L-1} A_{i+1} - A_{i} = A_{L} - A_{1}$$을 관찰하는 것은 어렵지 않다. 주어진 합은 배열을 알면 양쪽 끝의 두 원소만을 이용해서 구할 수 있다. 이 의미는, $A_{1}, A_{2}, A_{3}, ... , A_{N}$이 주어질때, 중간의 원소 $A_{2}, A_{3}, ... ,A_{N-1}$는 ..
1. 페리 수열의 대칭성(symmetry) n번째 페리 수열의 분수 $\frac{a}{b}$에 대해 생각해보자. 먼저 기약분수이므로 a,b가 서로소이고 0과 1 사이에 있으므로 a < b이다. https://deepdata.tistory.com/1104 페리 수열(farey sequence) 조금 더 깊게1 - 페리 수열의 길이 - 1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. deepdata.tistory.com 이전에 관찰했던 것처럼 n번째 페리 수열에는 분모가 n 이하인 정수 b에 대하여 b보다 작은 서로소인 모든 정수 a에 대해 $\..
1. 페리 수열의 길이 n번째 페리 수열은 분모가 n 이하인 0과 1 사이의 모든 기약분수를 오름차순으로 나열한 것이다. 기약분수가 무엇인가? $\frac{a}{b}$가 기약분수라면 a와 b가 서로소라는 뜻이다. 이때, 0과 1 사이에 존재하는 기약분수이므로 a < b이다. 그러므로 n번째 페리수열에 존재하는 기약분수들은 다음과 같이 만들수도 있다. "양 끝에는 $\frac{0}{1}, \frac{1}{1}$이 있고, 분모가 b = 2,3,4,5,..,n에 대하여 분자는 k보다 작으면서 서로소인 모든 정수 a에 대해 $\frac{a}{b}$를 나열한 것이다." 예를 들어, 5번째 페리 수열을 보자. 분모가 2이면 2와 서로소인 1에 대해 $\frac{1}{2}$ 분모가 3이면 3과 서로소인 1,2에 대해..
1. 문제 31091번: 거짓말 (acmicpc.net) 31091번: 거짓말 당신 앞에는 $N$명의 사람들이 있다. 각 사람은 자신을 포함하여 몇 명 이상이 거짓말을 하고 있다고 말하거나, 몇 명 이하의 사람이 거짓말을 하고 있다고 말한다. 예를 들어, 각 사람이 다음과 www.acmicpc.net 2. 풀이 K명이 거짓말 한다고 가정하자. K = 0,1,2,3,..,n이다. 각각의 경우에 대하여 실제로 각 사람들의 말과 비교할때 누가 거짓말을 하는지 알 수 있다. 이때, 정말로 거짓말하는 사람 수가 K명으로 일치한다면 그러한 K값은 정답에 포함될 것이다. 예를 들어 2명이 거짓말을 한다고 하면... "1명 이상이 거짓말하고 있다."는 참이다. 실제로 2명이 거짓말하고 있으니까 "1명 이하가 거짓말하고..
1. 문제 31287번: 장난감 강아지 (acmicpc.net) 31287번: 장난감 강아지 U, D, L, R로 이루어진 길이 $N$의 문자열 $S$가 주어진다. 문자열 $S$를 $K$번 이어 붙인 문자열을 $T$라고 하자. 장난감 강아지 타카하시는 2차원 좌표평면의 원점에서 시작해서 $T$에 적힌 문자를 하 www.acmicpc.net 2. 풀이 의외로 생각을 요구해서 배울 점이 있는 문제 위,아래,왼쪽,오른쪽으로 강아지가 움직이는데.. 문제는 길이 2000인 문자열 S를 최대 $10^{9}$번 반복시켜서 2000*1000000000번 강아지가 움직일 수 있다 이때 원점에서 움직이는데 다시 원점으로 돌아올 수 있는지 확인해야하는 문제 2000*1000000000번을 1초안에 다 해볼수는 없을 것 근데..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
