합과 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

문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든 수의 합

D - Another Sigma Problem (atcoder.jp) D - Another Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  배열 A의 모든 순서쌍 (A[i],A[j])에 대하여 f(A[i],A[j])를 A[i]A[j]라고 정의 예를 들어 f(10,1) = 101이고 f(3,14) = 314 i  예를 들어 3 14 15라면 (3,14), (3,15), (14,15) 3개의 순서쌍에 대해 314, 315, 1415가 있고 이들의 합은 2044 모든 순서쌍을 찾는 것은 기본적으로 $O(..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 6. 11.
• textsms

모든 순서쌍의 합의 나머지를 합해야하는데 매 항마다 나머지를 더하면 안되는 문제

C - Sigma Problem (atcoder.jp) C - Sigma ProblemAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  f(x,y) = x + y를 $10^{8}$로 나눈 나머지라고 정의 모든 i = 1,2,3,...,n-1, i  예를 들어 3 50000001 50000002이면... (3, 50000001), (3, 50000002), ( 50000001, 50000002)가 있고... 50000004, 50000005, (100000003 % 100000000 = 3)이 된다. 이들을 합하면 10000..

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

[Java]예시문제로 자바 매개변수 탐색 기본기 배우기1

1. parametric search란 무엇인가1 - 합에 대한 탐색 1부터 n까지의 자연수의 합이 100이상인 경우 중 가능한 n의 최솟값을 구하는 프로그램을 작성해보세요. 단, 답은 1에서 30사이라고 가정합니다. 무작정 문제를 푼다면, 1,2,3,...,30 전까지 계속 더해보면서 최초로 합이 100을 넘는 경우, 그 숫자를 return하게 된다. 하지만 다음과 같이 시도해본다면? 1차시도: n = 15 15까지의 합은 120이므로 15는 답의 후보이며, n의 최솟값을 찾기 위해 이러한 합보다 더 작은 합은 1~14중 하나에서 찾을 수 있다. 2차시도: n = 7 7까지의 합은 28이므로, n은 확실히 7보다 커야하며, 8~14를 조사해본다. 3차시도: n = 11 11까지의 합은 66이므로, n은..

• format_list_bulleted 이분 탐색
• · 2023. 4. 5.
• textsms

이분 탐색 응용문제로 올바른 사고 연습하기2

1. 문제 18113번: 그르다 김가놈 (acmicpc.net) 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 2. 풀이 문제를 보면 김밥의 길이가 k보다 큰 경우, 양쪽을 균일하게 k씩 자른다 하지만 2k보다 짧은 경우, 한쪽 k만 자른다. k보다 작거나 같은 경우 김밥은 그냥 폐기한다 김밥 길이를 받을 때, L > k인 경우, L 2k일때, L-2k를 리스트에 저장한다 L == 2k일때는 문제에서 아무런 언급이 없기..

• format_list_bulleted 이분 탐색
• · 2023. 4. 4.
• textsms

탐욕적으로 생각하기 연습 -팩토리얼 분해-

1. 문제 2057번: 팩토리얼 분해 (acmicpc.net) 2057번: 팩토리얼 분해 음 아닌 정수 N이 주어졌을 때, 이 수를 서로 다른 정수 M(M ≥ 1)개의 팩토리얼의 합으로 나타낼 수 있는지 알아내는 프로그램을 작성하시오. 예를 들어 2=0!+1!로 나타낼 수 있지만, 5는 이와 같은 www.acmicpc.net 주어진 정수가 여러개의 팩토리얼의 합으로 나뉠 수 있는지 검사하는 문제 2. 풀이1 실버 5인데 왤케 어렵냐... 그리디 알고리즘이 확실히 경험이 없긴한가봐 내 해법은 일단.. 어떤 정수 N을 팩토리얼로 분해한다고 하면... 당연히 팩토리얼 값은 N보다 작아야 할 것이다 그래서 N보다 작은 팩토리얼을 일단 모두 구해놓는다 from sys import stdin n = int(stdi..

• format_list_bulleted 그리디 알고리즘
• · 2023. 1. 5.
• textsms