원당컴퓨터학원

위의 문제는 단순히 계산을 해보면 되는 문제 입니다.

1번문제풀이)

총합을 최소로 하고자 한다면 다음과 같은 형태로 계산을 해 볼수가 있겠네요.

어차피 가운데로 몰릴 수 밖에 없으므로..

A -> B : 4

J -> I : 1

I -> H : 1 + 1 * 2 = 3 (J가 I 에 온 시간 1시간 + I 와 J가 H 로 이동하는 시간 1시간)

H -> E : 3 + 1 * 3 = 6 (J와 I가 H에 온시간 3시간 + I,J,H가 E로 이동하는 시간 3시간)

G -> E : 1

F -> E : 1

따라서 E까지 오는 하위 시장들의 모든 시간은 8 시간

B -> C : 4 + 1 * 2 = 6

C -> D : 6 + 1 * 3 = 9

D -> E : 9 + 1 * 4 = 13

E -> D : 8 + 1 * 6 = 14

따라서 D에 모일때는 왼쪽에서 모이는 시간 9 + 오른쪽에서 모이는 시간 14 = 23

E에서 모일때는 왼쪽에서 모이는 시간 13 + 오른쪽에서 모이는 시간 8 = 21

정답은 4번 E 입니다.

2번문제풀이) 

가장 빠른 시간은 가장 먼 거리에서 오는 시간을 계산 하면 됩니다

B는 왼쪽에서 A가 오는 시간 4 시간 오른쪽에서 J가 오는 시간 6시간 이므로 6시간이 걸립니다.

C는 왼쪽에서 A가 오는 시간 5시간 오른쪽에서 J가 오는 시간 5시간이므로 가장 짧은 시간이 됩니다.

정답은 2번 C 입니다.

정보올림피아드 문제 풀이 리스트 정리

다음 프로그램이 출력하는 수를 구하여라.

const int n = 10;

int b[n] ={1,4,5,7,8,10,11,12,14,15};

int i, p, r = 0;

for (p = 0; p < (1 << n); p++){

int x = 0;

for (i = 0; i < n; i++){

if (p & (1 << i)) x ^= b[i];

}

if (x <= 9) r++;

}

printf ("%d\n",r);

P는 0~(이진수 10000000000) 1024 까지 반복 한다.

P=00000000000 일 때 r=1

P=00000000001 일 때 x=1 r=2

P=00000000010 일 때 x=4  r=3

P=00000000011 일 때 x=1^4 = 5 r=4

P=00000000100 일 때 x=5 r=5

P=00000000101 일 때 x=1^5=4 r=6

P=00000000110 일 때 x=4^5=1 r=6

P=00000000111 일 때 x=1^4^5=0

P=00000001000 일 때 x=7

이렇게 1024번을 계산 하려고 하면 몇날 몇일 이 문제 한문제만으로 날밤을 세워야 할것 같네요.^^

따라서 규칙을 찾아야 하는 문제입니다.

먼저 비트 연산이므로 b 배열의 값을 이진수로 변환하면 다음과 같습니다.

b[] = {'0001','0100','0101','0111','1000','1010','1011','1100','1110','1111'}

이것을 P의 값을 이진수로 변환해서 P의 값이 1인 위치의 값을 xor 하면서 9보다 작거나 같은 경우를 구하는 문제입니다.

가령 P=00000000000(0) 일때는 10개의 데이터 중에 하나도 선택하지 않은 경우이므로 x=0 이 나옵니다.

P=00000000001(1) 일때는 10개의 데이터 중에 0번째 배열의 데이터('0001')를 선택 하는 경우 이므로 x=1 이 나옵니다.

P=00000000011(3) 일때는 10개의 데이터 중에 0번째('0001') 와 2번째 배열의 데이터('0100')를 선택 하여 xor 를 함으로 '0101'(5) 가 됩니다.

이런 방법으로 1의 위치에 있는 데이터를 선택해서 xor 한 후에 9('1001') 보다 작거나 같은경우 선택하면 되는 데요...

p의 값이 0 부터 1023 까지 순차적으로 올라가기 때문에 10비트의 숫자는 동일하게 512회씩 선택을 받게 되는 구조 입니다.

이런 경우 다이나믹 테이블을 이용해서 풀어 볼수가 있는데요...

가령 {1,4,5,7,8,10,11,12,14,15} 의 데이터 중에서

아무것도 선택하지 않은 경우 위의  0 에서 왼쪽 0 이라는 숫자를 만들 수 있습니다.

그리고 1을 선택해서 그 이전에 아무것도 선택하지 않은 경우 00(0000)와 xor 를 하면 01(0001)을 만들 수 있습니다. 따라서

(00(0000),00(0000)) 위치의 1이 (01(0001),01(0001) ) 위치로 갯수가 넘어 옵니다.

이것을 테이블로 만들어 보면 다음과 같은 형태로 나타낼 수가 있습니다.

+ 의 의미는 그 이전의 갯수를 현재 칸으로 가져온다는 의미 이고 화살표의 의미는 그 이전의 값과 현재의 값을 xor 한 경우 넘어 오는 형태를 표시 한것입니다.

이런식으로 테이블을 작성해서 보면 마지막 15를 선택했을때는 0 부터 15까지 모든 경우가 동일하게 64번씩 나오는 것을 확인할 수가 있네요.

그러면 0부터 9까지 10개의 수이므로 64 * 10 = 640 이 나온다는 것을 확인 할 수가 있었습니다.

정답은 640이 나옵니다.

풀이 과정이 쉽게 생각이 나지 않아서 학생들과 함께 머리 맞대고 고민을 많이 했던 문제였네요.^^

정보올림피아드 문제 풀이 리스트 정리

오늘 우리 학생 중 한명이 줄자 접기 문제를 설명해 주었는데..

설명에 이해가 안된것 같아서...

줄자접기 문제를 다시 한번 풀어 보겠습니다.

문제)

준성이는 1㎝ 간격으로 눈금이 매겨져 있는 줄자를 가지고 있다. 그 줄자에 있는 서로 다른 눈금 6개에 한 눈금에 하나씩 점이 찍혀 있는데, 빨간 점, 파란 점, 노란 점이 각각 두 개씩 있다.   준성이는 먼저 빨간 점이 만나도록 줄자를 접었다. 그런 후 두 파란 점이 만나도록 줄자를 접고, 또 다시 두 노란 점이 만나도록 줄자를 접었다. 줄자는 투명하여 접더라도 점들을 잘 볼 수 있다. 어떤 색깔의 두 점이 만나도록 줄자를 접었을 때, 그 다음에 접으려는 색깔의 두 점이 이미 만나고 있으면, 그 두 점에 대해서는 줄자를 접지 않는다.   예를 들어 길이 10㎝ 인 줄자에 아래 그림과 같이 2㎝ 와 7㎝ 위에에 두 빨간 점이 찍혀 있고, 5㎝ 와 4㎝위치에 파란 점이, 10㎝ 와 3㎝ 위치에 노란 점이 찍혀 있다고 하자. (그림에서 빨간 점은 별표로, 파란 점은 동그라미, 그리고 노란 점은 네모로 표시되어 있다.) 빨간 두 점이 만나도록 줄자를 접으면 줄자의 4.5㎝ 위치에서 접히고 4㎝ 와 5㎝ 눈금이 서로 만나게 된다. 그러면 줄자의 왼쪽 부분의 길이는 4.5㎝ 이고 오른쪽 부분의 길이는 5.5㎝가 되어, 접힌 줄자의 길이는 5.5㎝ 가 된다. 파란 두 점은 이미 만나므로 줄자를 접지 않고, 그런 다음 노란 두 점이 만나도록 접으면 줄자의 길이는 3.5㎝ 가 된다.     줄자의 길이와 각 색깔의 점들이 찍혀있는 위치가 주어질 때, 준성이가 빨간 색, 파란 색, 노란 색의 순서로 두 점이 만나도록 줄자를 접으면 줄자의 길이가 얼마가 되는지를 구하는 프로그램을 작성하시오.   입력 파일의 첫째 줄에 줄자의 길이가 입력된다. 줄자의 길이는 10㎝ 이상, 1,000㎝ 이하이고 단위를 나타내는 ㎝은 입력되지 않는다. 둘째 줄에는 두 빨간 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 셋째 줄에는 두 파란 점의 위치가, 넷째 줄에는 두 노란 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 입력되는 모든 점들의 위치는 서로 다르다. 한 줄에 접은 후의 줄자의 길이를 소수점 이하 한자리까지 출력한다. 소수점 이하 한자리가 0 이면 0 도 출력한다.(예 4.0) 10 2 7 5 4 10 3 3.5 출처 : KOI 전국 2004 초2

다음 프로그램의 출력결과는 무엇인가?

정답은 B입니다.

저희 아이들 대부분 정답 없음을 선택했네요...ㅠ.ㅠ

실제로 아스키값은 0~255 까지 나오는 것을 알고 있어서..

'A'의 아스키값이 65 이니까 x = 65 + 128 + 129 = 322 가 나와서 아스키값 범위를 넘어 가기 때문에 정답 없음을 선택 했는데요...ㅠ.ㅠ

위와 같은 코드는 시리얼 통신 프로그래밍에서 데이터가 깨졌는지 안깨졌는지 확인하기 위해 마지막 데이터에 체크썸을 두는데 이때 사용하는 체크썸을 구할 때 많이 사용하는 프로그래밍 기법이네요.

일반적으로 체크썸은 데이터 패킷을 모두 합 한 다음에 1바이트로 변환해서 체크썸을 두는 경우가 많거든요.

원리는 다음과 같습니다.

x는 int 타입이기 때문에 4byte 입니다.

따라서 322는 이진수로 바꾸면 

|0000|0000|0000|0000|0000|0001|0100|0010|

위와 같이 32bit로 표현될수 있습니다.

이것을 char 타입으로 변환하면 1byte만 사용하기 때문에 주황색 부분인 |0100|0010| 이부분만 가져 오게 됩니다.

따라서 이것을 10진수값으로 표현하면 66 이고 이것을 ASCII 값으로 변환하면 'B' 가 되는 것입니다.

결국은 322 % 256 = 66 의 값을 얻게 되는 것입니다.

정보올림피아드 문제 풀이 리스트 정리

이제 지역대회가 몇일 남지 않았네요...

그동안 지역대회를 준비한 학생들도 고생 많이 했구요...

지역대회를 위해 마지막까지 열심히 공부하고 있는 학생들에게도 응원의 메시지를 보냅니다.

오늘은 2017년 지역대회 고등부 27번 문제를 같이 풀어 보도록 하겠습니다.

이러한 프로그래밍 문제를 처음 접하게 되면 학생들은 자신의 코드가 아니다 보니 남의 코드를 보는 것을 대체로 싫어하는 경향이 있더라구요.

특히나 머리가 좋은 학생일 수록... 같은 문제를 자신의 스타일을 고집하다 보니 더더욱 다른 사람의 코드를 보는 것을 귀찮아 하는 경향이 두드러 지더라구요.

그러기는 해도 일단 지역대회를 통과해야만 전국대회에서 자신의 코드를 구현해 볼 수 있는 기회가 되다 보니...

귀찮아도 남의 코드를 보는 습관을 기르는 것이 좋을것 같기는 합니다.

일단 이러한 배열 문제가 나오면 저 같은 경우에는 무조건 그림을 먼저 그려 보게 됩니다.

소스로만 볼때와 그림을 그렸을때와 소스가 하는 역할이 훨씬 더 잘 보이거든요.

a 배열을 다음과 같이 주소값과 데이터값을 입력해서 그림을 그려 봅니다.

이때 i는 0번지 부터 9번지까지 이동을 하게 되고 

j는 i+1 번지 부터 9번지까지 이동을 하게 되네요...

if (a[i] < a[j]){

 t = a[i];

 a[i] = a[j];

 a[j] = t;

}

이 부분에서는 i가 0 번지 일때 j는 1번지 부터 9번지까지 이동을 하면서 0번지 값보다 큰값이 있으면 교환을 하네요.

i가 1번지 일때는 j가 2번지 부터 9번지까지 모두 훑으면서 1번지 값보다 큰 값이 있으면 교환을 하고요.

이렇게 그림을 그려 보니 갈수록 작아지는 내림차순을 하는 선택정렬 프로그램 이었네요...

사실 이런 문제는 기출문제를 여러 회차를 풀다 보면  

if (a[i] < a[j]){

 t = a[i];

 a[i] = a[j];

 a[j] = t;

}

이러한 유형의 코드만 확인해도 직감적으로 정렬 프로그램이구나 하는것을 알게 되거든요.

하지만 요즘에는 코드 형태만 보고서 바로 계산 하는 순간 또 다른 함정이 있는 경우가 많아서 정확히 하나 하나를 모두 돌려 보는 경우가 가장 안전하기는 한것 같습니다.

27번 문제 같은 경우는 선택정렬의 가장 기본적인 형태라서 초,중,고생 모두 어렵지 않게 풀수 있었던 문제였던것 같네요.

정답을 확인해 보면

a 배열값이 97,89,59,48,30,21,17,16,16,12 과 같이 내림차순 정렬이 되고 여기에서 0번지 부터 4번지까지의 5개의 합을 출력하는 문제입니다.

97 + 89 + 59 + 48 + 30 = 323 이 나오는 것을 확인 할 수가 있었습니다.

하지만 배열을 처음 접하는 학생들은 아무래도 머리속에 그림을 그리려고 하다 보니 실수를 하는 경우가 간혹 있어서...

저희 원생들에게는 될수 있으면 작은것 하나도 그림을 그리도록 이야기는 하고 있는데...^^

학생들이 그림 그리는 것을 무척이나 귀찮아 하는 것 같네요.^^

이번 지역대회에서 그동안 고생한 보람을 찾았으면 좋겠다는 생각을 해 보게 되네요.^^

정보올림피아드 문제 풀이 리스트 정리

오늘은 2017년 고등부 지역대회 문제를 풀어 보겠습니다.

문제

2017년 초등부 문제에는 A,B,C 세명이 만나서 악수를 하는 문제가 출제 되었는데요...

이러한 문제는 집합의 멱집합 갯수를 파악하면 해결 되는 문제 입니다.

멱집합이란 어떤 집합의 모든 부분집합의 집합을 의미 하는데요...

가령 집합의 원소가 다음과 같이 {1,2,3} 와 같이 3개의 원소로 구성 되었다면.

멱집합은

{}(공집합),{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} 과 같이 8개의 부분집합을 만들수가 있습니다.

이러한 멱집합의 갯수는 원소갯수가 n 이라 하면 2의 n승에 해당하게 됩니다.

이러한 원리는 원소를 선택하거나 선택하지 않거나의 경우로 나누어 지기 때문에 1개의 원소에 따라 각각 2가지 경우가 존재 하므로 원소의 갯수가 3개라면 2 * 2 * 2 가 되는 것이거든요.

이러한 원리를 이용해서 A,B,C,D,E 가 악수를 할 수 있는 경우를 나타내 보면 다음과 같습니다.

(A,B).(A,C),(A,D),(A,E),(B,C),(B,D),(B,E),(C,D),(C,E),(D,E) 와 같이 10개의 원소로 이루어진 집합으로 보시면 됩니다.

이러한 집합의 멱집합 갯수는 2의 10승이며 1024 가지가 됩니다.

이때 적어도 한쌍 이상이 악수를 했다는 이야기는 공집합인 경우가 없다는 이야기 이므로 1가지를 뺀 1024 - 1 = 1023 가지가 됩니다.

초등부 문제에서는 직접 세어 볼수 있는 문제이지만...

고등부 문제에서는 원리를 파악하지 않으면 풀수 없었던것 같습니다.

멱집합이 무엇이고 멱집합의 갯수는 어떻게 구성되는지 원리를 알아 보는 문제 였습니다.

정보올림피아드 준비하는 학생들을 응원하며...

좋은 결과를 얻기를 바랍니다.

정보올림피아드 문제 풀이 리스트 정리