나눗셈 실수오차가 생긴다면 직접 나눗셈을 구현하기

1206번: 사람의 수 (acmicpc.net)  n명의 사람이 0점부터 10점까지 정수로 존재하는 설문조사 문항에 점수를 내서 각 문항마다 평균을 낸 점수가 실수로 주어질때, n이 될 수 있는 가장 작은 정수를 구하는 문제 평균이 소수점 셋째자리까지만 주어진다 예를 들어 32/106 = 0.3018867924528302... 인데 0.301만 주어지는 ---------------------------------------------------------------------------------------------------------------------------------- 만약 설문조사한 사람 수가 x명이고 i번째 문항의 점수 합이 v이면  $$\frac{v}{x} \approx A[i]$$  A..

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

좌표들이 주어질때 좌표간 간격이 될 수 있는 모든 수를 찾는 방법

30105번: 아즈버의 이빨 자국 (acmicpc.net) 초코바에 이빨 자국을 남기는데 이빨간 간격이 k라고 한다면 0이상의 수 x에 대하여 x부터 x+k에 이빨 자국을 남긴다 이빨자국을 동일한 위치에 여러번 남겨도 한번만 보인다 이빨자국이 남겨진 좌표들 x0,x1,x2,...,xn이 주어진다면 가능한 k를 모두 구해본다면?  1. 무식하게 찾는 방법 쉽게 생각할 수 있는 방법은.. 일단 모든 좌표쌍 (xi,xj)에 대하여 간격 k = xj - xi를 구하고 간격 k에 대응하는 xi,xj를 저장해둔다 모든 간격 k에 대하여 간격 k에 대응하는 x좌표가 주어진 이빨 자국 수와 같다면 해당 간격 k는 가능한 k라는 것 예를 들어 [0,5,10,15]로 주어질때 모든 쌍에 대하여 5-0 = 5이므로 h[5]..

• format_list_bulleted 브루트포스
• · 2024. 9. 24.
• textsms

논리식의 일부를 바꿔서 원하는 결과가 나오게 만드는 방법

31835번: 수식 고치기 (acmicpc.net) T,F,&,|으로만 이루어진 논리식에서 일부를 바꿔서 원하는 결과가 나오게 만들고 싶다. 연산은 왼쪽에서 오른쪽으로 차례대로 진행하고, 논리식을 최소로 바꿀때, 최소횟수를 구한다면 예를 들어 F & F가 주어질때 연산 결과를 T로 만들고 싶다면 T & T로 바꾸면 되니 2번이다. 단순하게 생각한다면 가능한 경우 다 조사해서 다 바꿔볼려고  할텐데..  그러자니 어떻게 바꿔야할지도 모르겠고 길이가 N  하다가 머리를 굴려보니.. &와 |으로 이루어진 연산을 생각해보면 T & T = T T & F = F F & T = F F & F = F T | T = T T | F = T F | T = T F | F = F 이렇게 되니까 a1 b1 a2 b2 a3 b3 ..

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

a b k d e g h i l m n ng o p r s t u w y 순서로 정렬하기?

1599번: 민식어 (acmicpc.net) 주어진 문자열들을 알파벳 순서가 아니라 a b k d e g h i l m n ng o p r s t u w y 순서로 정렬한 결과를 출력 처음에는 문자열 한쌍씩 알파벳 하나하나 비교해서 버블정렬로 해볼까? 생각은 했는데 상당히 까다로울 것 같더라고 근데 문득 자세히 보니까  a b k d e g h i l m n ng o p r s t u w y에서 k를 c로 바꿔보고 a,b,c,d,e...  g를 f로 h를 g로 i를 h로 l을 i로... 해서 바꿔볼 생각을 하니까  a b k d e g h i l m n ng o p r s t u w y a b c d e f  ghi  j  k    l m n o p q r s t  중복이 안되더라? 그러면 주어진 문자열..

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

그래프에서 서로 연결된 세 정점의 차수 합의 최솟값 찾기

17089번: 세 친구 (acmicpc.net) 서로 친구인 a,b,c에 대하여 a의 친구 수 + b의 친구 수 + c의 친구 수가 최소가 되도록 만들고 싶다. a의 친구 수에는 b,c는 제외해야한다. 마찬가지로 b,c의 친구 수에는 a,c, a,b는 제외해야한다. a의 친구 수 + b의 친구 수 + c의 친구 수 - 6의 최솟값을 찾아야한다는 소리 친구 관계를 그래프로 만드는데 각 정점에 연결된 정점을 set()으로 만들어서 O(1)로 서로 친구인 정점을 찾도록 만들자 from sys import stdinn,m = map(int,stdin.readline().split())graph = [set() for _ in range(n+1)]for _ in range(m): a,b = map(int,s..

• format_list_bulleted 브루트포스
• · 2024. 9. 10.
• textsms

모든 집합의 합집합과 다르게 되는 일부를 골라 만든 최대 합집합

30237번: 합집합 (acmicpc.net) s1,s2,...,sn 집합이 주어질때, 이들 중 일부를 골라 만든 합집합 s와 모든 집합의 합집합 s1 ∪ s2 ∪ ... ∪ sn이  서로 다르게 되는 가장 큰 합집합 s를 구하고 싶다 집합을 기준으로 s1 넣어보고 s2는 넣지말고... sn은 넣고 등등으로 해서 s를 다 조사해보는건 $O(2^{50})$으로 어렵다 모든 집합의 합집합을 먼저 구하고 그 중에서 하나의 집합만 빼는 방법은 어떨까? 집합 합칠수록 원소가 많아질테니까... s2 ∪ s3 ∪ ... ∪ sn s1 ∪ s3 ∪  ... ∪  sn ... 이러면 O(N)정도니까 괜찮을것 같은데 [1], [3,6,10], [9], [1,3], [5,8,9]를 보면 모든 집합의 합집합은 [1,3,5,6..

• format_list_bulleted 브루트포스
• · 2024. 9. 9.
• textsms