의외로 알아내기 어려운 2의 거듭제곱을 더하면 나타나는 특징

1. 문제 27514번: 1차원 2048 (acmicpc.net) 27514번: 1차원 2048 첫 줄에 흐즈로가 정의한 연산을 $0$번 이상 수행해 만들 수 있는 가장 큰 최댓값을 출력하세요. 문제의 답은 $2^{62}$보다 크지 않음이 보장됩니다. www.acmicpc.net 2. 풀이 0이나 2의 거듭제곱으로 이루어진 수열이 있는데, 서로 같은 두 수를 찾으면 하나를 2배 해주고 다른 수는 0으로 바꿔준다 이 과정을 반복했을때, 남아있는 수열의 수 중 최댓값을 찾는 문제 처음에는 걍 수의 위치가 중요한 문제는 아니니.. 수열의 값 a와 그 개수를 value로 해서 dict[a] = value로 만들고 dict를 순회해서 value가 2개 이상 있으면 2배한 dict[2a] += 1 해주고, dict..

• format_list_bulleted 애드 혹 알고리즘
• · 2023. 10. 9.
• textsms

Binary Lifting을 이용한 개선된 최소 공통 조상(Lowest Common Ancestor) 구하는 방법 배우기2

https://www.youtube.com/watch?v=O895NbxirM8 https://kibbomi.tistory.com/201 최소 공통 조상 (LCA, Lowest Common Ancestor)(C/C++) 여러 자료를 참조하면서 LCA를 공부했는데, 어떤 자료는 너무 쉽고 깔끔하지 못하고, 어떤 자료는 난이도가 있고 깔끔하게 설명된 자료였습니다. 그래서 여러 자료를 찾아보며 이해하고, 또 이해 kibbomi.tistory.com 1. 문제 11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 8. 13.
• textsms

정수 n을 2의 거듭제곱으로 나눈 나머지를 효율적으로 구하는 방법

나머지를 구할때 %로 구하면 되는데.. 효율적으로 구한다는게 도대체 무슨말인가? %연산은 계산 비용이 높아서 비효율적으로 알려져있다. n = 98 print(n % 2) #0 print(n % 4) #2 print(n % 8) #2 print(n % 16) #2 print(n % 32) #2 계산비용을 줄이고 싶다면 % 연산자를 사용하지 않고 나머지를 구해야한다. 예를 들어 4로 나눈 나머지를 어떻게 구할 수 있을까? 컴퓨터는 모든 수를 2진수로 인식하기 때문에.. 가장 쉬운 접근은 정수 n을 2진수로 나타내보는 것이다. 위 그림을 보면 어떤 수를 4로 나눈 나머지는 0,1,2,3중 하나인데... n을 2진수로 나타냈을때 4로 나눈 나머지는... n의 2진수 표현에서 오른쪽 끝의 2비트만 가져오는 것임을..

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