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

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

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

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

생각해서 브루트포스 탐색 범위를 줄여야하는 경우1 (장난감 강아지)

1. 문제 31287번: 장난감 강아지 (acmicpc.net) 31287번: 장난감 강아지 U, D, L, R로 이루어진 길이 $N$의 문자열 $S$가 주어진다. 문자열 $S$를 $K$번 이어 붙인 문자열을 $T$라고 하자. 장난감 강아지 타카하시는 2차원 좌표평면의 원점에서 시작해서 $T$에 적힌 문자를 하 www.acmicpc.net 2. 풀이 의외로 생각을 요구해서 배울 점이 있는 문제 위,아래,왼쪽,오른쪽으로 강아지가 움직이는데.. 문제는 길이 2000인 문자열 S를 최대 $10^{9}$번 반복시켜서 2000*1000000000번 강아지가 움직일 수 있다 이때 원점에서 움직이는데 다시 원점으로 돌아올 수 있는지 확인해야하는 문제 2000*1000000000번을 1초안에 다 해볼수는 없을 것 근데..

• format_list_bulleted 브루트포스
• · 2024. 2. 3.
• textsms

그리디 알고리즘 연습 - 곱해서 최대가 되도록, 더해서 최소가 되도록 나누기

1. 문제 20915번: 숫자 카드 놀이 (acmicpc.net) 20915번: 숫자 카드 놀이 Albert 는 n장의 숫자 카드를 가지고 있다. 각 카드에는 0부터 9까지 숫자 하나씩이 적혀있고, 6이나 9가 적힌 카드를 회전할 경우 구분할 수 없다 (즉, 6이 적힌 카드는 회전하면 9로 보이고, 9가 www.acmicpc.net 2. 풀이 숫자를 두 부분으로 나눠서 곱했을때, 최대가 되도록 만들기 두 부분은 적어도 하나의 숫자를 반드시 포함해야한다 6이나 9는 회전해도 구분할 수 없으니 회전해서 사용가능하다. 그렇다면 곱했을때 최대가 될려면 6은 무조건 9로 만들어서 사용하는게 유리하다. 또한 두 수의 곱이 최대가 될려면, 앞자리에는 무조건 큰 수가 오는게 유리하다 또한 두 수 a,b에 대하여 그 차..

• format_list_bulleted 그리디 알고리즘
• · 2023. 11. 4.
• textsms