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