촉수 [1062090] · MS 2021 · 쪽지

2021-08-08 15:05:14
조회수 812

연습문제 1

게시글 주소: https://1ff8ipsi.orbi.kr/00038981351

[제시문 1]


함수 f: X → Y에서, 모든 y ∈ Y에 대해, 유일한 x가 있어 f(x) = y이면, 이를 일대일 대응이라 한다. 순열은, 정의역과 공역이 같은 일대일 대응을 말한다.




[제시문 2, https://ko.m.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC 참고]


버블 정렬은, 두 이웃한 원소를 비교해 자리를 바꾸며 정렬하는 과정이다.



[버블 정렬의 시행 중 일부; 자료의 위치를 바꾸면서, 리스트의 마지막에서 최댓값을 갖도록 한다]




[문제 1]



n을 양의 정수라 하자. 카멜레온을 문자 a, b, c가 정확히 n번 나타나는 3n개의 문자열로 정의하고, 스왑을 카멜레온의 두 이웃한 글자의 전치(위치 바꾸기)로 정의하자. 임의의 카멜레온 X에 대해, X로 3n^2/2보다 적은 스왑 없이 바뀔 수 없는 카멜레온 Y가 있음을 보여라.

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

  • 촉수 · 1062090 · 21/08/08 15:09 · MS 2021

    기출은 IMO 2017 Shortlist C2입니다. 인하대에서는 2011 C4까지 내는데 딱히 문제가 있을 것으로 보이지는 않습니다. 그와 별개로 이 문제는 학생이 함수의 개념을 이해하는지 확인할 수 있는 좋은 문제라 가져옵니다.

  • Dypp · 1072625 · 21/08/08 16:10 · MS 2021
    회원에 의해 삭제된 댓글입니다.
  • Dypp · 1072625 · 21/08/08 16:31 · MS 2021

    혹시 Y는 어떤 한 문자를 한쪽으로 몰아넣은 형태가 되는게 맞나요??

  • 촉수 · 1062090 · 21/08/08 16:33 · MS 2021

    왜 그렇게 되나요?