구간 내 가장 큰 해밍거리를 가지는 두 정수를 구하는 방법

33692번: 해밍 거리 두 정수 a,b의 해밍거리는 a,b를 각각 이진수로 나타내서, 동일한 위치의 비트를 비교하여 서로 다른 비트의 수를 말한다. 예를 들어 9 = 1001 12 = 1100이므로, 2번째 비트와 4번째 비트가 서로 달라 9,12의 해밍거리는 2이다. 두 정수 A,B가 주어질때 A이상 B이하에서 해밍거리가 가장 큰 두 정수 a,b를 아무거나 구한다. -------------------------------------------------------------------------------------------------------------------------------------------------------- A,B를 각각 이진수로 나타내고 이진수의 길이가 서로 다르다면, 앞..

• format_list_bulleted 애드 혹 알고리즘
• · 2025. 4. 8.
• 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

비트마스킹을 위한 비트연산 필수이론 가볍게 정리

1. 비트(bit) 정보를 구분하는 최소 단위로 이진 숫자(binary)를 뜻한다 0,1의 값을 가지며 True/False나 on/off같은 2가지 상태를 나타낼 수 있다 10진수를 2진수로 바꾸면 해당 10진수에 대응하는 하나의 비트열을 얻는다 2. 비트연산 - 비트연산은 비트열의 같은 위치끼리만 연산함 2-1) &(and) 비트 단위로 and연산을 수행 비트가 둘다 1이면 1이고, 하나라도 0이면 0인 연산 & 연산은 위 표에서 특징을 자세히 살펴보면.. 1) 0과 and연산은 무조건 결과가 0이다 0&0 = 0 0&1 = 0 2) 1과 and연산은 나머지 비트를 그대로 가져온다 1&1 = 1 1&0 = 0 2가지 성질을 잘 이용하면.. 3) 어떤 비트열에서, 특정 부분을 0으로 만들고 싶다면.. 나..

• format_list_bulleted 비트마스킹
• · 2022. 10. 23.
• textsms