서로 순열이 되는 경우를 찾는 트릭(정렬해서 비교하기)

1501번: 영어 읽기 영어 단어의 첫글자와 끝글자가 서로 같고 그 사이의 글자가 순서가 뒤섞인채로 구성이 같으면 같은 단어로 취급한다 abcde는 acbde, abdce,... 등과 같다 단어 사전과 문장들이 주어질때 각 문장을 해석하는 방법의 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------- 영어 단어가 bakers, brakes, breaks,...등이 주어질때 먼저 bakers를 보면 bakers, bkaers, bekras, berkas, bearks,... 등이 서로 같은 단어들이다...

• format_list_bulleted 애드 혹 알고리즘
• · 2025. 3. 5.
• textsms

경기장 일렬 좌석에 앉을 때 사람을 지나치지 않고 전부 앉는 방법의 수

29313번: Стадион (acmicpc.net)  일렬로 된 N개의 좌석이 있는데 사람이 양쪽으로 들어가서 좌석에 앉을 수 있다고 할때,  어떤 사람이 이미 앉은 사람을 지나치지 않고 N명이 모두 앉는 방법의 수를 구하는 문제 예를 들어 3명이 앉는다고 해보면 이렇게 4가지가 있다    N개의 자리가 있을 때 _ _ _ _ _ _ ... 첫번째 자리에 먼저 앉으면 1 _ _ _ _ _ ... 나머지 N-1개의 자리는 고정적으로 2,3,4,5,6,... 으로 1가지 = N-1C0가지 결정된다 두번째 자리에 먼저 앉으면 _ 1 _ _ _ _ .... 1의 왼쪽 자리 _ 를 N-1명중 1명을 결정시키면 1의 오른쪽은 무조건 자동으로 결정되므로... N-1C1가지 왜냐하면 1의 왼쪽에 3을 앉히면 3 1 ..

• format_list_bulleted 조합론
• · 2024. 7. 26.
• textsms

배열을 뒤집었을때 생기는 반전 수의 개수 구하기

25339번: 반전 수와 쿼리 (acmicpc.net)  반전 수는 i P[j]인 (i,j)의 개수를 말한다. 배열이 [3,2,1]이면 반전수는 (인덱스 말고) (3,2), (3,1), (2,1)로 3개가 있다. l번, r번을 서로 교환하는 쿼리 [l,r]의 배열을 서로 뒤집는 쿼리가 주어질 때, 매 쿼리마다 수열의 반전 수를 2로 나눈 나머지를 구하는 문제 ---------------------------------------------------------------------------------------------------------------------------------------------------------- 배열 길이와 쿼리 수가 엄청나다보니 단순한 방법으로는 시간초과 이 문제는..

• format_list_bulleted 애드 혹 알고리즘
• · 2024. 5. 23.
• textsms

ABC 324 - D번 복기, 순열 다루는 테크닉 - 두 문자열이 서로의 순열일려면? -

1. 문제 D - Square Permutation (atcoder.jp) D - Square Permutation AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 주어진 정수 문자열의 순열이 어떤 정수의 제곱수가 될때, 그러한 순열의 개수를 구하는 문제. 길이 제한이 13이라고 해도 모든 순열을 찾고, 각 순열이 어떤 수의 제곱수인지 검사하면 매우 느리다 1) 만약 길이 N인 s의 순열이 X의 제곱수가 될려면, X는 아무리 커봐야 $\sqrt{10^{N}}$이다. 그러므로 0부터 $\sqrt{10^{N}}$까..

• format_list_bulleted Atcoder
• · 2023. 10. 15.
• textsms

같은 것이 있는 순열(복수순열) 배우기 - 숫자 만들기 -

1. 문제 4008. [모의 SW역량테스트] 숫자 만들기 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 주어진 숫자들 사이에 연산자를 집어넣어 왼쪽부터 오른쪽으로 우선순위를 무시하고 순서대로 계산을 할때, 가능한 계산결과의 최댓값과 최솟값의 차이를 구하시오 2. 같은 것이 있는 순열 배열의 원소들 중에 같은 것이 포함된 복수순열은 어떻게 구현할 수 있을까? 일반 순열을 구현할때는 배열의 j번째 원소를 사용했는지 여부를 나타내는 used를 사용해서 구현을 했는데 def permutation(i,n,r): if i == r: print(p) else: for j in range(n..

• format_list_bulleted 브루트포스
• · 2022. 10. 12.
• textsms

중복된, 비효율적인 연산을 줄이는 연습문제 -요리사-

1. 문제 4012. [모의 SW역량테스트] 요리사 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N개의 식재료를 N/2개씩 나누어 2개의 요리를 하려고 한다. 각 요리의 맛은 음식을 구성하는 식재료들의 시너지의 합으로 구해진다. 음식의 맛의 차이가 최소가 되는 경우를 찾는다면? 2. 풀이1 순열과 조합을 이용하는 문제가 될텐데 실전 문제에까지 직접 구현해서 사용할 이유는 전혀 없고 from itertools import combinations, permutations를 이용하자 처음에 풀때는 2개의 재료에 대해서는 설명이 명확한데 3개의 재료에 대해서는 시너지를 어떻게 계산하..

• format_list_bulleted 브루트포스
• · 2022. 10. 5.
• textsms