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초안에 다 해볼수는 없을 것 근데..
1. 모든 원소 쌍의 XOR 합 $A_{0}, A_{1}, ... , A_{n-1}$에 대하여 $\sum_{i=0}^{i=n-1} \sum_{j=i+1}^{j=n-1} A_{i} \oplus A_{j}$을 구하는 문제 단순하게 풀면 $O(N^{2})$이지만 조금 더 생각해본다면 $O(N)$에 가깝게 해결할 수 있다. 결국 구하고자 하는 값은 $V = A_{i} \oplus A_{j}$라고 할 때, 이 V들의 합이다. 그런데 V를 2진수로 나타낸다면.. $$V = a_{k}2^{k} + a_{k-1}2^{k-1} + ... + a_{1}*2 + a_{0}$$로 나타낼 수 있다. 여기서 $a_{i} = 0$이거나 $a_{i} = 1$이다. 만약 모든 $V = A_{i} \oplus A_{j}$에 대하여 최대..
1. 연속하는 부분열에 대한 XOR n개의 음이 아닌 정수 $A_{1}, A_{2}, ... , A_{n}$에 대하여 L번부터 R번까지의 XOR $A_{L} \oplus A_{L+1} \oplus ... A_{R}$의 값은? 만약 $V_{0} = 0, V_{i} = A_{1} \oplus A_{2} \oplus ... \oplus A_{i}$라고 하자. $V_{L-1} = A_{1} \oplus A_{2} \oplus A_{3} .... \oplus A_{L-1}$이다. 그러면, $0 \oplus x = x, x \oplus x = 0$이므로.. 0을 xor해도 값이 달라지지 않는다. $$A_{L} \oplus A_{L+1} \oplus ... A_{R} = 0 \oplus (A_{L} \oplus A_..
1. 기본 성질 정수 x,y,z에 대하여... $$ x \oplus 0 = x $$ $$ x \oplus x = 0 $$ $$ x \oplus y = y \oplus x $$ $$ (x \oplus y) \oplus z = x \oplus (y \oplus z)$$ 사실 교환법칙, 결합법칙이 성립하고 0을 xor하면 그대로 나오고 자기자신을 xor하면 0이 나온다는거 아는데 만약 n개의 원소 a1,a2,a3,...,an에 대하여.. a1 ^ a2 ^ a3 ^ ... ^ an을 생각해보자. a2 ^ a3 ^ a4 ^ ... ^ an의 값을 알고 싶다면 어떻게 해야할까? a1+a2+a3+...+an을 알고있다면 그냥 a1을 뺀다면 되는데 xor에서는 이런 빼기 연산이 있는건가? 다시 a2,a3,..,an을 ..
1. 문제 C - Loong Tracking (atcoder.jp) C - Loong Tracking AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 1번부터 N번까지 좌표가 있고, 1번 좌표는 쿼리에 의해 움직이게 된다. 1번 좌표가 움직이면, 2번,3번,4번,...,N번 좌표는 각각 1번,2번,3번,...,N-1번 좌표가 된다. 쿼리가 20만개이고 좌표수도 최대 100만개라 단순하게 접근하면 시간초과를 받을 것인데 그림으로 생각해보면 접근법을 생각할 수 있다 처음에 배열에 1번부터 N번까지 좌표가 있는데, ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
