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

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

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

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

특정한 정점들을 반드시 포함하는 최소 정점 트리 만들기 - list말고 반드시 set을 사용해야하는 경우

https://atcoder.jp/contests/abc368/tasks/abc368_d D - Minimum Steiner TreeAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  1부터 n까지 번호를 가진 정점을 가진 트리에서 어떤 정점들을 제거할때, 특정한 정점 v1,v2,...,vk를 반드시 포함하게 하는 트리를 만들고 싶다면, 그러한 트리의 최소 정점 수는? 예를 들어 왼쪽 트리에서 1,3,5를 반드시 포함하는 트리를 만들고 싶을때, 4번, 6번, 7번을 제거하면 된다     사실 테크닉에 감탄해서 복기하는거긴 한..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 8. 31.
• textsms

n개의 구간 각각에서 어떤 정수들을 골라 합해 0을 만들 수 있는가?

https://atcoder.jp/contests/abc362/tasks/abc362_c C - Sum = 0AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n개의 구간 (Li,Ri)가 주어질때, 이 구간들 각각에서 정수 Xi를 하나 골라 n개 합쳐서 0을 만들 수 있는지? 그렇다면 그러한 정수 배열을 하나 찾는 문제 먼저 그러한 정수 배열이 존재하는지 알 수 있을까? 이것부터 어렵더라고 근데 생각보다 간단했다  $$L_{1}$$ L_{2}  ...  $$L_{n}  이들을 합해도 부등식이 유지되므로,$$ \sum_{i =..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 8. 24.
• textsms