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

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

맨 위 정수가 주어질때, 아래 두 수의 합이 위 정수가 되는 피라미드 만들기

17802번: Integral Pyramid (acmicpc.net)  가장 위의 정수가 주어지고, 몇줄로 구성해야하는지 주어지고, 현재 정수 x는 바로 아래 줄의 2개의 정수 합으로 구성되도록 만든다. 현재 줄이 n개라면 아래 줄은 n+1개로 구성되어야한다. 예를 들어 15가 맨 위에 있고 3줄로 구성해야한다면  15 8 73 5 2 어떻게 할 수 있을까? 그냥 생각했을 때는 맨 위의 정수부터 시작해서 아래로 내려가도록 구성해야할 것 같다 맨 아래에서 위로 올라오기는 어려울 것 같다 이 말이지 그러면 맨 위의 정수를 절반으로 나눠서 15면 8과 7로 나누고... 8은 4와 4로 나눈 다음... 우측의 4와 7을 비교해서 7은 4와 3으로 나누고... 789를 6줄로 나누는 것도 789를 절반으로 해서 ..

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

게임이론 기본기 익히기2 - 2~9 사이 정수 곱하기 게임에서 이기는법

4370번: 곱셈 게임 (acmicpc.net)  1  p >= n에 먼저 도달하는 사람이 이길 때, 두 사람이 완벽하게 게임한다면 n에 대하여 선공과 후공중 누가 이길까?  1. 다이나믹 프로그래밍 n의 제한이 너무 크기때문에 dp배열을 초기화해서 해결하기는 어렵다 그래서 dict를 이용해서 배열의 크기는 잡지말고 필요한 값만 저장하도록 하는 dp를 이용 현재 상태가 p라고 한다면, 이 게임은 i = 2,3,..,9중 하나를 곱해서 상태를 변화시킬 수 있고 이기거나 지거나 둘중 하나이고 완벽하게 게임하므로  현재 이기는 상태라면 상태 변화를 통해 상대가 지는 상태가 되는거고 현재 지는 상태라면, 상태 변화를 통해 상대가 이기는 상태가 된다 p = 1부터 시작해서 재귀적으로 모든 i = 2,3,4,..,..

• format_list_bulleted 게임이론
• · 2024. 9. 5.
• textsms

배열에서 두 수의 합이 s가 되는 경우의 수(서로 다른 방향으로 움직이는 투 포인터)

29940번: Sum (acmicpc.net) 배열이 서로 다른 원소들로 이루어져있고 정렬되어 있을때, 여기서 고른 서로 다른 두 수의 합이 s가 되는 경우의 수를 구하는 문제 투 포인터로 어떻게 해결할 수 있을까 보통 투 포인터하면 i = 0, j = 0으로 같은 방향에서 시작해서 j를 1씩 계속 증가시키다가, 특정 조건에서 멈추고 다시 i를 1 증가시키고 다시 j를 계속 증가시키고... 같은 방향으로 움직이지만 두 수 A[i] + A[j] = s가 될려면 i = 0으로 고정되어 있을 때 A[j] = s - A[0]로 확정적으로 구할 수 있다. 그러면 배열 A가 서로 다른 수로 이루어져 있고 정렬되어 있으므로  모든 i = 0,1,2,..,n-1는 작은 수부터 시작하므로 반대편 A[j] = s - A[..

• format_list_bulleted 투 포인터 알고리즘
• · 2024. 9. 2.
• textsms

여사건을 이용한 경우의 수1 - 특정 수를 포함하는 부분집합 구하는 법

20214번: Binary Seating (acmicpc.net)  두 강의실 0번과 1번에 n명의 학생이 1/2의 확률로 선택하여 입장할때,  1번 강의실에서 모든 시험이 끝날 때까지 걸리는 시간의 기댓값을 구하는 문제 걸리는 시간을 X라고 한다면...? 예를 들어 학생이 5명이고 각각 t = 1,4,5,2,3 만큼 시험을 보고 떠난다고 할때, 가능한 X = 1,2,3,4,5이다. 그러므로 E(X) = 1*P(X = 1) + 2*P(X = 2) + 3*P(X = 3) + 4*P(X = 4) + 5*P(X = 5) P(X = 1)은 어떻게 구할까? t = 1인 학생이 1번 강의실에 들어간 경우 (1) P(X = 2)는 어떻게 구할까? t = 2인 학생이 1번 강의실에 들어간 경우 (2) t = 1인 학생..

• format_list_bulleted 조합론
• · 2024. 8. 23.
• textsms