해밍거리 + BFS 경로 역추적하기

2479번: 경로 찾기 이진 코드들이 주어질때, A 이진코드에서 B 이진코드로 가는 경로를 찾을려고 한다 이때 경로를 구성한 노드간 서로 인접한 코드끼리의 해밍거리가 1이어야한다 해밍거리는 길이가 같은 두 이진코드들에서 왼쪽부터 오른쪽으로 차례로 비교할 때 서로 다른 값을 가진 비트의 수이다 예를 들어 010과 110은 서로 다른 비트가 0번째 비트로 1개이므로 해밍 거리가 1이다 코드 번호 A,B가 주어질때 가장 짧은 해밍 경로를 찾는다 -------------------------------------------------------------------------------------------------------------------------------------------------- 두 코..

• format_list_bulleted DFS BFS 정복기
• · 2025. 2. 3.
• textsms

XOR 문제에 접근하기 위해 반드시 필요한 스킬3 -모든 쌍의 XOR의 합(sum of all pair of xor)-

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}$에 대하여 최대..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 1. 27.
• textsms

XOR 문제에 접근하기 위해 반드시 필요한 스킬2 - 연속하는 부분열의 XOR-

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_..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 1. 25.
• textsms

XOR 문제에 접근하기 위해 반드시 필요한 스킬1 - 기본 성질 -

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을 ..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 1. 23.
• textsms

gcd와 xor의 성질, 연속하는 두 자연수는 서로소, dict보다 list를 먼저 고려하기

1. 문제 21004번: GCD vs. XOR (acmicpc.net) 21004번: GCD vs. XOR For each test case output a single integer: the number of pairs $(a_i, a_j)$ with $i y이면 p-q ..

• format_list_bulleted 정수론
• · 2023. 8. 13.
• textsms

알고리즘 문제 해결(PS)을 위한 게임이론 기초지식 - 님 게임(Nim game) 배우기

1. 님 게임(Nim game) 게임이론에서 가장 중요한 게임 형태중 한가지라고 할 수 있다. ""수학적 전략 게임으로, 여러 개의 돌 무더기가 있다고 가정하자. 두 사람이 서로 차례를 번갈아가며 게임을 한다. 자신의 차례에 하나의 돌 무더기를 선택하고, 1개이상의 원하는 만큼의 돌을 제거한다. 마지막 남은 돌을 제거하는 사람이 게임에서 승리한다."" 2. 게임의 수학적 기술 현재 시점에 n개의 돌 무더기에 있는 돌의 개수가 $x_{1}, x_{2}, ... , x_{n}$이라고 하자. 내가 어떤 돌 무더기를 하나를 선택하여 돌을 가져가고 나서 변화된 돌의 개수는 $y_{1}, y_{2}, ... , y_{n}$이라고 하자. 만약 k번째의 돌 무더기를 선택하고 돌을 가져갔다면.. 돌의 개수는 줄어드니까 ..

• format_list_bulleted 게임이론
• · 2023. 5. 15.
• textsms