1206번: 사람의 수 (acmicpc.net) n명의 사람이 0점부터 10점까지 정수로 존재하는 설문조사 문항에 점수를 내서 각 문항마다 평균을 낸 점수가 실수로 주어질때, n이 될 수 있는 가장 작은 정수를 구하는 문제 평균이 소수점 셋째자리까지만 주어진다 예를 들어 32/106 = 0.3018867924528302... 인데 0.301만 주어지는 ---------------------------------------------------------------------------------------------------------------------------------- 만약 설문조사한 사람 수가 x명이고 i번째 문항의 점수 합이 v이면 $$\frac{v}{x} \approx A[i]$$ A..
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 ..
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 중복이 안되더라? 그러면 주어진 문자열..
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..
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..
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..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
