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

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

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

Kernighan’s Algorithm

1. 문제 0과 1로 구성된 이진 비트열에서 1의 개수를 구한다면? '1101'이면 1이 3개 2. 방법1 간단하게 비트열을 돌아서 1의 개수를 세기 시간복잡도는 비트열의 길이를 S라 하면 O(S) s = '1101'count = 0for i in range(len(s)): if s[i] == '1': count += 1print(count)  비트열이 주어지지 않고 단순히 정수로 주어질 수 있다 예를 들어 '1101' = 13인데 이진 비트열로 바꾸지 않고 구할 수 있나? n의 마지막 비트와 1을 and연산하여 1이면 counting하고 n의 마지막 비트를 삭제해나간다 비트를 삭제하는 방법은 n >> 1 n의 비트를 오른쪽으로 1칸 이동시키고 최하위비트는 소멸된다..

• format_list_bulleted 비트마스킹
• · 2025. 2. 2.
• textsms

합과 bitwise or연산이 같게되는 조건

1322번: X와 K  x+y = x | y를 만족하는 k번째로 작은 자연수 y를 구하는 문제 합과 or 연산이 서로 같게되는 조건을 먼저 생각해본다 or연산은 두 bit가 1이면 1이고 두 bit가 0이면 0이고 두 bit가 1,0으로 서로 다르면 1인 연산 두 수를 합하는 것은 어떤 의미인지 생각해본다 x,y를 2진수로 바꿔서 예를 들어 5 = 101이고 12 = 1100인데 이진수끼리 서로 덧셈은 어떻게 하는가? $101 = 0 * 2^{3} + 1 * 2^{2} + 0 * 2^{1} + 1 * 2^{0}$ $1100 = 1*2^{3} + 1 * 2^{2} + 0 * 2^{1} + 0 * 2^{0}$ 우측에 2의 거듭제곱으로 바꾼 것끼리 더한다고 생각해보면,  $(0 + 1)*2^{3} + (1+1..

• format_list_bulleted 비트마스킹
• · 2025. 1. 9.
• textsms

이진수의 마지막 n개의 비트가 모두 켜져있는지 확인하는 방법

SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  정수 m의 마지막 n개의 비트가 모두 1인지 확인하는 문제 m이 $10^{8}$이고 테스트 케이스는 10000개이고 제한시간 2초라 단순하게 확인하면 시간초과날 것 같다 가장 쉬운 방법은 0부터 n-1까지 순회해서 각 비트가 1인지 검사하는 것 (1 이다. T = int(input())for test_case in range(1, T + 1): n,m = map(int,input().split()) no = False for i in range(n): if (1   다른..

• format_list_bulleted 비트마스킹
• · 2024. 5. 3.
• textsms

job assignment problem으로 알아보는 비트마스킹을 이용한 다이나믹 프로그래밍

1. 문제 1311번: 할 일 정하기 1 (acmicpc.net) 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다. 각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 이럴 때 최소비용은 얼마인가? 2. 풀이 이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후, 각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다. 3명이면 (1,2,3), (1,3,2), ..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 3. 27.
• 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