인접한 두 수를 분해하여 적절하게 바꿔서 정렬하는 방법

33708번: 인수분해 정렬 두 수 A[i]와 A[i+1]을 a*b = A[i]*A[i+1], a+b != A[i]+A[i+1]을 만족하는 a,b로 바꿀 때  원하는 만큼 이 연산을 시행해서 주어진 수열 A를 비내림차순으로 바꿀 수 있는가? ------------------------------------------------------------------------------------------------------------------------------------------- a = 1, b = A[i]*A[i+1]이라고 하면, A[i],A[i+1]을 반드시 1,A[i]*A[i+1] 반대로 a = A[i]*A[i+1], b = 1이라고 하면 A[i],A[i+1]을 반드시 A[i]*A[i+1],..

• format_list_bulleted 애드 혹 알고리즘
• · 2025. 4. 10.
• textsms

두 팀중 적어도 한 팀이 소수만큼 점수를 얻을 확률

1344번: 축구  90분간 이루어지는 축구 경기를 5분 간격으로 나눈다. 처음 간격은 처음 5분, 두번째 간격은 그 다음 5분... 각 간격에서 A,B팀이 각각 득점할 확률이 주어진다 각 간격에서 A,B팀은 각각 많아야 한골씩 득점할 수 있다 경기가 끝났을 때 적어도 한 팀이 소수로 득점할 확률은? ------------------------------------------------------------------------------------------------------------------------------------ 5분씩 간격이 나눠지고 전체 경기 시간은 90분이므로 총 18간격씩 이루어진다 각 간격에서 두 팀은 독립적으로 최대 1골씩 넣을 수 있다 dp[i][a][b] = i번째 간..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 3. 2.
• textsms

문자열 수를 10진법으로 바꾸는 테크닉2 - n을 n번 이어붙인 정수

D - 88888888 (atcoder.jp) D - 88888888AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n을 n번 이어붙였을때, 그것을 998244353으로 나눈 나머지를 구하는 문제 숫자를 이어붙인 문제는... 한번 10진법으로 바꿔보면 해결법이 보이는 경우가 있다 https://deepdata.tistory.com/1235 문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든D - Another Sigma Problem (atcoder.jp) D - Another..

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

10진수를 다른 진법으로 바꾸는 방법

1. 1보다 큰 10진수를 다른 진수로 변환하는 방법 주어진 수를 변환하고자하는 진수의 base로 계속 나누고 나머지를 써둔다 마지막에 저장해둔 나머지 뒤에서부터 가지고옴 예를 들어 133은 3진법으로 변환하면 $11221_{(3)}$이다.   2. 10진수 소수를 진수 바꾸는 방법 반면 소수는 방법이 조금 다른데 base를 계속 곱해나간 뒤 소수점을 넘은 정수는 옆에 따로 저장해두고 정수를 뺀 나머지를 다음 단계로 보낸 뒤 base를 계속 곱해 다음 단계로 보낸 나머지 부분이 0이 될때까지 반복함 정수 변환은 맨 뒤에서부터 앞으로 가지고 왔지만 맨 처음부터 따로 저장한 수를 맨 뒤까지 가지고 오면 끝 예를 들어 0.375는 8진수로 변환하면 $0.3_{(8)}$이고 0.1을 2진수로 변환하면 $0.00..

• format_list_bulleted 정수론
• · 2024. 9. 1.
• textsms

골드바흐의 추측을 이용해 정수 n을 k개의 소수 합으로 표현하기

25309번: K개의 소수 (acmicpc.net) 정수 n을 k개의 소수 합으로 표현하라는 문제 여기서 핵심은 서로 다른 k개의 소수가 아니라, 같은 소수를 사용해도 좋다. 그리고 문제는 n이 최대 $10^{8}$이고 k는 최대 10000이라 단순한 방법으로는 어렵다 먼저 생각할 수 있는 것은 가장 작은 소수가 2이기 때문에, 2를 k개 사용하여 2k가 만들 수 있는 정수의 최솟값이다. 따라서 n = 2k이면 일단 분해하는 것이 가능하다. n,k = map(int,input().split())if n   만약 k = 1이면 n 자체로 소수인지 아닌지 판단하면 된다.  $O(\sqrt{n})$에 소수 판단할 수 있다. def is_prime(n): for i in range(2,int(n**..

• format_list_bulleted 정수론
• · 2024. 5. 24.
• textsms

문자열 hashing function 빠르게 계산하는 방법

1. 왜 문자열의 hashing이 필요한가? https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing stringdeepdata.tistory.com  두 문자열 S1, S2가 서로 같은지 다른지 비교하고 싶을 때가 있..

• format_list_bulleted 문자열 알고리즘
• · 2024. 5. 18.
• textsms