무브

오르비

아톰

내 태그

내 태그 설정

입시
학습
생활
클럽
직업·취업
Epioptimus
Centurion

다싶고보 [896464] · MS 2019 (수정됨) · 쪽지

2021-04-20 18:40:22
조회수 2,437

확통 한줄컷1: "이웃하지 않는다"의 "사전" 처리

게시글 주소: https://orbi.kr/00037266245

확통 한줄컷1: "이웃하지 않는다"의 "사전" 처리


제목만 보면 무슨 말인지 이해 안되는게 당연하구요, 흐름을 그대로 천천히 따라와주세요. 


1. 우리는 보통 "이웃하지 않는다"를 "사후"처리한다.

문제1) 6명(a,b,c,d,e,f)을 일렬로 나열할 때, 그 중 2명(e,f)이 이웃하지 않는 경우의 수


풀이1: "사후처리" 

우리는 보통 "이웃하지 않는다"라는 조건을 보면 이웃하지 않는 두 학생을 나중에 처리하려고 합니다. 

즉, "이웃하지 않는 것"을 사후 처리하며 나머지 학생들을 먼저 배열합니다. 

이웃하지 않는 조건이 없는 나머지 학생 4명을 먼저 배열한 후에(4!), 그 사이(@)에 2명을 넣어줍니다.

@a@b@c@d@  5(e가 갈곳)x4(f가 갈곳)


풀이2:" 사전처리"

생각을 바꿔서 "이웃하지 않는 것"을 먼저 배열하면 안될까요? 즉, "이웃하지 않는 것"을 사전 처리해 봅시다. 

e,f를 먼저 배열(2!), 4명이 남습니다. 그런 다음 e,f를 기준으로 3가지 영역이 생깁니다. (e의 앞, e와 f의 사이, f의 뒤)

 @ e @ f @ 

이 때" e와 f가 이웃하지 않는다"는 조건은 "e와 f사이에 적어도 한 명 이상이 있다"와 동치임을 반드시 숙지하고 넘어갑시다.

제가 여기서 뜬금없이 세 가지 서로 다른 영역에 사람 4명이 아니라 4개의 같은 공(구별되지 않음)을 넣어볼 겁니다. 


WHY? 바로 사람을 넣는다고 하면 상황은 매우 불리해집니다. 불가능하다는 것이 아니라 훨씬 좋은 방법이 있습니다. 우선 "같은 공"을 넣는 것입니다.


그리고 e와 f사이에는 적어도 한 명이 이상이 있으니 공을 한 개 이상을 넣을 겁니다.

그렇다면 상황은 "서로 같은 공 4개를 서로 다른 영역 3개에 넣되 가운데 영역에는 적어도 한 개 이상이 있다"로 바뀝니다. 즉, 3H3.


O O e O f O  

3H5가지 중 하나의 예시입니다. 공이 대충 이런 식으로 들어갔겠죠? 

저 공들은 사람이 아니니 당연히 아직 끝나지 않았습니다. 이제 남은 a,b,c,d를 저 공에 넣을 겁니다.

그냥 일렬로 배열하는 느낌이므로 4!입니다. 


정리하면 2!x3H3x4! 풀이 1과 결과는 같습니다. 


아니 도대체 왜 이런식으로 푸는 건지..싶겠지만 좀만 더 힘을 내서 뒤로 가봅시다. 수학에서 다양한 풀이를 배우는 이유는 A 문제에서 별로였던 풀이가 B 문제에서는 가장 좋은 풀이일 수 있습니다. 시험장에선 어떤 풀이가 본인을 살릴 지 모른다는 생각으로 최대한 많은 것을 흡수하세요.


문제2)  6개의 문자 a,a,b,b,c,c를 일렬로 나열할 때 a끼리는 이웃하지 않도록 나열하는 경우의 수는? 

(출처: 2020.4월 학평)


풀이1: "사후처리" 

4!/2!2!(b,b,c,c 나열)x 5C2(a를 사후 처리) (답:60)


풀이2:" 사전처리"

a a를 먼저 나열하는 경우의 수: 1

a를 기준으로 생기는 3가지 영역

@ a @ a @

@에 우선 같은 공 4개를 넣되, 가운데 영역에는 한 개 이상을 넣는 경우의 수: 3H3

O O a O a O (예시)

O자리에 b,b,c,c를 넣는 경우의 수: 4!/2!2! (4C2로 배열하셔도 됩니다.)

즉, 3H3x4!/2!2! (답:60)


요약하자면,

1. 이웃하지 않는 것들을 먼저 나열하고,

2. 같은 공을 그 사이에 넣되 이웃하지 않는 것들 사이에 적어도 1개를 넣는 것입니다.


다음 문제들을 풀며 이 풀이의 유용성이 느껴지길 바랍니다. 

풀이 읽지 말고 문제 먼저 풀어보세요! 


문제3) (출처:EBS) 

A,B,C,D,E를 포함한 7명의 학생을 다음 조건을 만족시키도록 일렬로 세우는 경우의 수를 구하시오.

(가) A는 B보다 왼쪽에 세우고 C는 B보다 오른쪽에 세운다.

(나) D, E는 서로 이웃하지 않게 세운다.


풀이:" 사전처리"

역시 이웃하지 않는 D,E를 먼저 배열합니다:2!

D,E를 기준으로 생기는 3가지 영역

@ D @ E @

@에 우선 같은 공 5개를 넣되, 가운데 영역에는 한 개 이상을 넣는 경우의 수: 3H4

O O D O E O O (예시)

O 자리에 A,B,C,나머지 2명을 넣어야 하는데 A,B,C끼리는 순서가 정해져 있으므로: 5C3

나머지 2명 배열: 2!

즉, 2!x3H4x5C3x2! (답: 600)


문제4) (출처: 2021년 3월 학평)

숫자 1, 2, 3, 3, 4, 4, 4가 하나씩 적힌 7장의 카드를 모두 한 번씩 사용하여 일렬로 나열할 때, 1이 적힌 카드와 2가 적힌 카드 사이에 두 장 이상의 카드가 있도록 나열하는 경우의 수는?  


풀이:" 사전처리"

앞선 문제와의 차이점은 앞선 문제들은 이웃하지 않는다(사이에 1명 이상), 이 문제는 사이에 2명 이상이네요. 

역시 1,2를 먼저 배열: 2!

1,2를 기준으로 생기는 3가지 영역

@ 1 @ 2 @

@에 우선 같은 공 5개를 넣되, 가운데 영역에는 2개 이상을 넣는 경우의 수: 3H3

O O 1 O O 2 O (예시)

O 자리에 3,3,4,4,4를 넣는 경우의 수: 5!/2!3! (or 5C2)

즉, 2!x3H3x5!/2!3! (답:200)


문제5,6,7은 앞선 문제보다 더 낯설 수 있습니다. 

자리들이 이미 세팅되어있으면 같은 공을 넣기만 해도 자리가 정해집니다. 말이 너무 추상적이므로 문제를 많이 곱씹고서 결국 앞선 문제들과 똑같은 문제라는 것을 느꼈으면 좋겠습니다.


문제5) (출처: 2019년 7월 학평)

어느 수영장에 1번부터 8번까지 8개의 레인이 있다. 3명의 학생이 서로 다른 레인의 번호를 각각 1개씩 선택할 때 , 3명의 학생이 선택한 레인의 세 번호 중 어느 두 번호도 연속되지 않도록 선택하는 경우의 수는?



풀이:" 사전처리"

이번엔 3명이 모두 이웃하지 않아야 합니다.

우선 3명(A,B,C라 합시다.) 배열: 3!

A,B,C를 기준으로 생기는 4가지 영역

@ A @ B @ C @

@에 우선 같은 공 5개를 넣되, A와 B사이 @에 적어도 1개, B와 C사이 @에 적어도 1개를 넣는 경우의 수: 4H3

O  A  O  B   O  C  O  O (예시)

그럼 자동으로 A는 2번 레인, B는 4번 레인, C는 6번레인이 됩니다. 더 무엇을 할 필요가 없습니다.

즉, 3!x4H3 (답:120)


문제6)  (출처: 2007학년도 6월 평가원)

그림과 같이 8개의 포트를 가진 컴퓨터용 허브가 있다. 이 허브에 컴퓨터 C1,C2,C3을 왼쪽부터 이 순서로 다음 조건을 만족시키도록 연결하는 방법의 수를 구하시오.


조건: 컴퓨터 Ck가 연결되는 포트와 컴퓨터 Ck+1이 연결되는 포트 사이에는 k개 이상의 포트가 비어 있다. (단,k=1,2이다.)

풀이:" 사전처리"

k=1대입: C1과 C2사이에 한 개 이상 포트

k=2대입: C2와 C3사이에 두 개 이상 포트

컴퓨터 C1,C2,C3 먼저 배열: 1가지 (발문에서 C1,C2,C3 순서로 연결하자고 함)

C1,C2,C3을 기준으로 생기는 4가지 영역

@ C1 @ C2 @ C3 @ 

@에 우선 같은 공 5개를 넣되, C1과 C2사이 @에 적어도 1개, C2와 C3 사이 @에 적어도 2개를 넣는 경우의 수: 4H2

O C1 O C2 O O C3 O (예시)

그럼 자동으로 C1은 2번째 포트, C2는 4번째 포트, C3은 7번째 포트가 됩니다.

즉, 4H2 (답: 10)


문제7) (출처: 2010학년도 9월 평가원)

1부터 9까지 자연수가 하나씩 적혀 있는 9장의 카드가 있다. 이 카드 중에서 동시에 3장을 선택할 때, 카드에 적힌 어느 두 수도 연속하지 않는 경우의 수는?


풀이:" 사전처리"

1 2 3 4 5 6 7 8 9 중 어느 두수도 연속하지 않는 3개의 수를 뽑는 문제입니다.

연속하지 않는다는 것도 결국 붙어 있지 않다는 뜻이므로, 사이에 적어도 1개가 있다고 해석할 수 있습니다.

이 문제에선 우선 같은 공 3개를 나열하겠습니다.(경우의 수:1)

이 같은 공 3개들이 우리가 뽑을 3개의 수가 될 것입니다.

@ O @ O @ O @

@에 같은 네모 6개를 넣되, O 사이의 @에는 한 개 이상을 넣겠습니다.(경우의 수:4H4)

□ □  O □ O □ O □ □ 

그럼 자동으로 O들은 각각 3,5,7이 됩니다. 

즉, 4H4 (답: 35)


긴 칼럼 읽어주셔서 감사합니다! 여러분들의 수험 생활을 응원합니다!



0 XDK (+2,000)

  1. 1,000

  2. 1,000

다싶고보 [896464]

쪽지 보내기

글쓰기
오르비 1339008번째 회원 가입
ddna
1,422,072 건의 게시물이
블록체인에 디지털 공증되었습니다.
901,751
497,321
22,267
574
159

오늘의 추천 글

2025 수능D - 54

오르비 플레이

오르비 RARE

오르비 과외시장
Move
our corporate site
Orbi Class
on-line classes
Atom
educational books & resources
Gae9
humor and fun

© 2000-2024 Move Inc.

orbisoptimus (v17-c3c98b)