반응형


정보올림피아드 중고등부5번


이런 문제는 수학 퍼즐의 일종으로 숫자가 복면을 쓰고 있는것 같다고 해서 복면산이라고도 부릅니다.

복면산 연산의 규칙은 특별한 것은 없고 단순히 같은 문자에는 같은 숫자가 들어가야 한다는 규칙과 서로 다른 문자는 서로 다른 숫자가 들어가야 한다는 규칙 밖에는 없습니다.

복면산 문제는 2년에 한번씩은 나올 정도로 단골 문제 이면서 쉬운듯 해 보이지만 생각보다 시간이 아주 많이 걸리는 문제들이 많기 때문에...

우리 학생들에게는 이러한 문제는 가장 마지막에 하나하나 대입해 보라고 설명해 주고는 합니다.


2015년 정보올림피아드 지역대회 중고등부 5번 문제를 풀어 보도록 하겠습니다.

이 문제에서 E는 1이 될수 없습니다. (E 가 1이 되면 계산 값이 DCBA 가 아닌 마지막 A자리에 D가 될것입니다.)

또한 E*A < 10 이고 E*A<=D 입니다.(맨 앞자리 E*A 를 했을때 D 가 나온다는 얘기는 한자리 수이면서 그 이전에 올림을 했거나 하지 않은 경우로 계산이 됩니다.)

그러므로 가능한 조합 (E,A)={(2,3),(2,4),(3,2),(4,2)} 입니다. 

이 규칙을 찾으면 일일히 대입하면서 하나 하나의 숫자를 찾아 내는 방법 밖에는 없는 문제가 복면산 연산이므로 무조건 대입해 보아야 합니다.

1-(2,3) 일때

3BCD * 2 = DCB3 <-- 이때 D*2 가 홀수가 되는 경우는 존재하지 않는다.

2-(2,4) 일때

4BCD * 2 = DCB4 <-- 이때 D*2 의 마지막 자리가 4 가 되는 경우 D = 7

4BC7 * 2 = 7CB4 <-- 이때 2*4 는 8 인데 D가 8보다 작은 7이 나올수 없다.

3-(3,2)일때

2BCD * 3 = DCB2 <-- 이때 D*3 의 마지막 자리가 2가 되는 경우는 D = 4

2BC4 * 3 = 4CB2 <-- 이때 3*2는 6인데 D가 6보다 작은 4가 올수가 없다.

4-(4,2)일때

2BCD * 4 = DCB2 <-- 이때 D*4의 마지막 자리가 2가 되는 경우 D=3 또는 D=8, 여기에서 D=3 인경우 2*4 보다 작으므로 성립이 안됨 따라서 D=8

2BC8 * 4 = 8CB2 <-- C*4 = B-3( 3을 올림 받았기 때문에) B*4 < 10(2*4 = 8 이면서 D가 8 이므로),B * 4 <= C

현재 2,4,8 이 나왔으며 B-3 은 짝수이므로 B가 되는 경우는 홀수이다, 1,3,5,7,9

B*4<10 이므로 B가 될수 있는 경우는 1 밖에는 없다.

21C8 * 4 = 8C12 <--만족하는 수는 4*C의 마지막 자리가 8 이어야 하므로 C=7 인 경우밖에는 없다.

따라서 2178 * 4 = 8712


정답은 D=8 따라서 4번




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

반응형
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2018.07.13 10:08 신고

    복면산연산이라는 것이군요
    어렵네요..ㅎㅎ
    잘 보고 갑니다.

  2. Favicon of https://100mountain.tistory.com BlogIcon ☆.、 2018.07.13 16:13 신고

    상당히 복잡한 문제네요

  3. Favicon of https://heysukim114.tistory.com BlogIcon *저녁노을* 2018.07.14 06:04 신고

    잘 보고 갑니다.

    즐거운 주말 되세요^^

  4. 핑구야 날자 2018.07.14 06:49

    올림피아드를 준비하는 분들에게 도움이 많이 되겠는데요 주말 잘 보내세요

  5. Favicon of https://bubleprice.tistory.com BlogIcon 버블프라이스 2018.07.16 22:11 신고

    이번에는 ‘2015년 정보올림피아드 중고등부 5번’ 문제 풀이를 해주셔서 대회에 참가하는 학생분들에게 정말 많은 도움이 될 것 같습니다^^

반응형

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


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 입니다.


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




반응형
이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2018.06.29 18:07 신고

    얼떨결레 맞췄네요...ㅎㅎ
    초등부 문제정도 보입니다.

  2. 핑구야 날자 2018.06.30 12:40

    어려워 보이는데 해 보면 답이 나오네요 ㅋㅋ 살아있눼

반응형

2018년 중등부 15번


정답이 56이 나오는 문제였는데 지문에 정답이 없어서 이슈가 되었던 문제입니다.

올바른 괄호짝이 아닌 문자열이 모두 몇개인지 확인하려면 모든 경우의 수에서 올바른 괄호짝을 찾아서 그 경우를 빼 주면 되는 문제네요.


4개의 짝으로 만들 수 있는 경우- 즉 8개의 (,) 를 가지고 만들수 있는 모든 경우의 수는 8개의 괄호를 순서대로 나열 할 수 있는 모든 경우 8! 에서 ( 가 동일한 모양 4개 ) 가 동일한 모양 4개 이므로 4! * 4! 로 나눈 수가 전체의 경우의 수입니다.

따라서 나올수 있는 모든 경우의 수는 8!/(4!*4!)= 70 가지가 됩니다.


이제 올바른 괄호 짝을 구하는 방법을 찾아 보겠습니다.


이러한 규칙을 찾는 수열 중에 카탈란 수라고 불리우는 수열이 있습니다.

핀란드 수학자 카탈란의 이름을 단 수열이라고 하는데요. 이 수열을 이용하면 간단하게 찾을 수 있습니다.


1에서 n쌍의 괄호가 잘 짜놓는 방법의 수를 Cn 이라고 하면 C0,C1,C2...,Cn-1 을 이용하여 Cn 을 찾는 방법을 살펴 보겠습니다.

n-1쌍의 괄호가 잘 짜여진 것에 ()를 알맞은 곳에 넣어 주는 방법을 세면 됩니다.

(A)B와 같이 넣는다고 하면 A도 잘 짜여진 괄호가 되어 있어야 하고 B도 잘 짜여져 있어야 합니다.

만약 A에 괄호가 k쌍이 있다면 B에는 n-1-k 쌍이 있어야 합니다.(n-1 쌍의 괄호의 갯수이므로 A가 k쌍일때 B는 n-1-k쌍)

따라서 A와 B를 나누는 경우를 세면 됩니다.

따라서 다음과 같은 점화식을 얻을 수 있습니다.

C0=1 (괄호쌍이 없는 경우 1가지 존재)

C1=C0C0 (k=0,n-1-k = 0,k=0만 존재)

C2=C0C1 + C1C0

C3=C0C2 + C1C1 + C2C0

C4=C0C3 + C1C2 + C2C1 + C3C0

...

이렇게 계산해 보면 다음의 결과가 나오는 것을 확인 할 수 있습니다.

C0=1

C1=1

C2=1 + 1 = 2

C3=2 + 1 + 2 = 5

C4=5+2+2+5=14


따라서 정답은 70 - 14 = 56 입니다.


그 외에 카탈란수를 이용하여 구할 수 있는 경우는 다음과 같은 경우에 구할 수 있을것 같네요.

  • n개의 X와 n개의 Y로 이루어진 문자열 중 처음부터 X와 Y의 개수를 세었을 때 항상 X가 Y보다 많거나 같은 것을 가리킨다. 예를 들면, 아래의 예제는 길이가 6인 모든 뒤크 단어들을 나열한 것이다. (XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY)



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




반응형
이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. 핑구야 날자 2018.06.09 06:41

    문자 풀이를 함께 하면 도움이 많이 되겠어요

  2. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2018.06.09 15:56 신고

    수열과 관계된 문제 같은데 일정한 순서나 규칙이 들어가서 어렵네요

반응형

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

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이 나옵니다.


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



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





반응형
이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2018.05.30 19:41 신고

    이걸 수작업으로 하려면 정말 어려울건데 코딩으로 간단하게 하니 신기합니다.ㅎㅎ

  2. 핑구야 날자 2018.05.31 06:48

    오늘 문제는 생각보다 어렵네요 즐거운 하루 보내세요

반응형

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

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


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


문제)


 

준성이는 1㎝ 간격으로 눈금이 매겨져 있는 줄자를 가지고 있다. 그 줄자에 있는 서로 다른 눈금 6개에 한 눈금에 하나씩 점이 찍혀 있는데, 빨간 점, 파란 점, 노란 점이 각각 두 개씩 있다.

 

준성이는 먼저 빨간 점이 만나도록 줄자를 접었다. 그런 후 두 파란 점이 만나도록 줄자를 접고, 또 다시 두 노란 점이 만나도록 줄자를 접었다. 줄자는 투명하여 접더라도 점들을 잘 볼 수 있다. 어떤 색깔의 두 점이 만나도록 줄자를 접었을 때, 그 다음에 접으려는 색깔의 두 점이 이미 만나고 있으면, 그 두 점에 대해서는 줄자를 접지 않는다.

 

예를 들어 길이 10㎝ 인 줄자에 아래 그림과 같이 2㎝ 와 7㎝ 위에에 두 빨간 점이 찍혀 있고, 5㎝ 와 4㎝위치에 파란 점이, 10㎝ 와 3㎝ 위치에 노란 점이 찍혀 있다고 하자. (그림에서 빨간 점은 별표로, 파란 점은 동그라미, 그리고 노란 점은 네모로 표시되어 있다.) 빨간 두 점이 만나도록 줄자를 접으면 줄자의 4.5㎝ 위치에서 접히고 4㎝ 와 5㎝ 눈금이 서로 만나게 된다. 그러면 줄자의 왼쪽 부분의 길이는 4.5㎝ 이고 오른쪽 부분의 길이는 5.5㎝가 되어, 접힌 줄자의 길이는 5.5㎝ 가 된다. 파란 두 점은 이미 만나므로 줄자를 접지 않고, 그런 다음 노란 두 점이 만나도록 접으면 줄자의 길이는 3.5㎝ 가 된다.

 

e3050b66a1b29a01767400d7560a4131_1449727
 

줄자의 길이와 각 색깔의 점들이 찍혀있는 위치가 주어질 때, 준성이가 빨간 색, 파란 색, 노란 색의 순서로 두 점이 만나도록 줄자를 접으면 줄자의 길이가 얼마가 되는지를 구하는 프로그램을 작성하시오.

 

입력 파일의 첫째 줄에 줄자의 길이가 입력된다. 줄자의 길이는 10㎝ 이상, 1,000㎝ 이하이고 단위를 나타내는 ㎝은 입력되지 않는다. 
둘째 줄에는 두 빨간 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 
셋째 줄에는 두 파란 점의 위치가, 넷째 줄에는 두 노란 점의 위치를 나타내는 정수가 빈칸을 사이에 두고 입력된다. 
입력되는 모든 점들의 위치는 서로 다르다.



한 줄에 접은 후의 줄자의 길이를 소수점 이하 한자리까지 출력한다. 소수점 이하 한자리가 0 이면 0 도 출력한다.(예 4.0)


10
2 7
5 4
10 3
3.5





문제풀이)


입력 예제와 같이 붉은 점이 2,7 위치에 있고

파랑색 점이 4와 5위치에 있고

노랑색 점이 3과 10위치에 있으며

처음 줄자의 길이는 총 10 인 줄자를 처음에 붉은점이 만나도록 접어야 하므로 (2+7)/2 의 위치인 4.5 위치에서 접게 됩니다.


그렇게 되면 파랑색 점은 4 위치의 점이 5 위치로 가고 5 위치는 그냥 5 위치에 남게 됩니다.(이것을 계산 하는 방법은 각각을 접는 위치와 차이를 구해서 접는 위치 + 차이 를 계산해 주면 오른쪽으로 이동하게 됩니다. 만약 오른쪽에 있는 점이라고 하면 그냥 오른쪽에 있을것이고 왼쪽에 있는 점이라면 접는 방향 오른쪽으로 이동할 것입니다.)

또한 노랑색 점은 3 위치의 점은 6 위치로 이동하고 10위치는 그냥 10위치에 남게 됩니다.


이때 시작점 0 의 위치는 9의 위치로 이동하는데 이것은 마지막 10의 위치보다 안쪽에 있기 때문에 마지막 점은 10의 위치에 그냥 남게 됩니다. 


그리고 4.5 위치에서 접혔기 때문에 시작점은 4.5 위치로 이동하게 됩니다. 따라서 붉은 위치의 지점에서 접은 상태의 길이는 4.5에서 시작해서 10의 위치에서 끝나는 길이 5.5의 줄자의 길이가 됩니다.


그리고 나서 파랑색을 만나게 접으려고 보니 이미 5와 5가 만나 있어서 다시 접을 필요가 없습니다.


따라서 다음 노랑색의 6과 10이 만나도록 접어야 합니다.


노랑색이 만나도록 접기 위해서는 (6+10)/2 = 8 의 위치를 접게 됩니다.

이렇게 접으면 처음 시작점 4.5 는 11.5의 위치로 이동하게 됩니다. 이때 마지막 점인 10 보다 더 큰수가 되기 때문에 이 점이 마지막 점이 됩니다.


그리고 나서 시작점은 접은 위치인 8로 이동하게 되면 이때의 줄자의 길이는 11.5 - 8 = 3.5 의 길이가 남게 됩니다.


이것은 반복문이나 복잡한 알고리즘 없이 그냥 단순하게 몇번만 접는 계산을 하면 될것 같습니다.


다음은 c언어 코드로 구현을 해 보았습니다.


 

#include <iostream>

#include <stdio.h>

#include <math.h>


using namespace std;


int main()

{

    double r1,r2;//붉은 점 위치

    double y1,y2; //노랑색 위치

    double b1,b2; //파랑색 위치


    double m;


    double s=0; //줄자의 시작 위치 초기값은 0

    double e;   //줄자의 마지막 위치;


    scanf("%lf",&e); //줄자의 마지막 위치를 입력 받자.

    scanf("%lf %lf %lf %lf %lf %lf",&r1,&r2,&b1,&b2,&y1,&y2); //점의 위치를 입력 받자


    //만약 r1과 r2 가 서로 다른 경우라면 접어서 두 점을 만나게 하자.

    if(r1 != r2)

    {

        m = (r1 + r2)/2; //접을 위치를 결정하자.

        //b1과 b2의 위치를 이동하자.

        b1 = m + fabs(m-b1); //b1의 위치는 접는 위치 m 에서 m과 b1의 차이를 더하면 그 위치가 나온다.

        b2 = m + fabs(m-b2);

        //y1과 y2의 위치를 이동하자.

        y1 = m + fabs(m-y1); //y1의 위치는 접는 위치 m 에서 m과 y1의 차이를 더하면 그 위치가 나온다.

        y2 = m + fabs(m-y2);

        //시작점의 위치를 이동하자.

        s = m + fabs(m-s);

        if(s > e) e = s; //시작점이 마지막 점을 넘어 가는 경우 마지막 점을 바꾼다.

        s = m; //접는 위치가 시작점이 된다.

    }

    //만약 b1과 b2 가 서로 다른 경우라면 접어서 두 점을 만나게 하자.

    if(b1 != b2)

    {

        m = (b1 + b2)/2; //접을 위치를 결정하자.

        //y1과 y2의 위치를 이동하자.

        y1 = m + fabs(m-y1); //y1의 위치는 접는 위치 m 에서 m과 y1의 차이를 더하면 그 위치가 나온다.

        y2 = m + fabs(m-y2);

        //시작점의 위치를 이동하자.

        s = m + fabs(m-s);

        if(s > e) e = s; //시작점이 마지막 점을 넘어 가는 경우 마지막 점을 바꾼다.

        s = m; //접는 위치가 시작점이 된다.

    }

    //만약 y1과 y2 가 서로 다른 경우라면 접어서 두 점을 만나게 하자.

    if(y1 != y2)

    {

        m = (y1 + y2)/2; //접을 위치를 결정하자.


        //시작점의 위치를 이동하자.

        s = m + fabs(m-s);

        if(s > e) e = s; //시작점이 마지막 점을 넘어 가는 경우 마지막 점을 바꾼다.

        s = m; //접는 위치가 시작점이 된다.

    }


    printf("%.1lf",e-s); //마지막 점과 시작점의 차이를 출력 한다.



    return 0;

}




그냥 순차적으로 접는것을 세번 반복하면 될것 같네요.


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





반응형
이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://moldone.tistory.com BlogIcon 청결원 2018.04.22 07:39 신고

    포스팅 잘 보고 갑니다~
    휴일 잘 보내세요^^

  2. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2018.04.22 11:09 신고

    이게 초딩 올림피아드 문젠가요? ㅎ성인들도 풀기 어려을데요.
    대단합니다.

  3. 핑구야 날자 2018.04.23 06:59

    수준이 높은 편이네요 잘 보고 갑니다

반응형

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


 

int x = 'A' + 128;

x += 129;

printf("%c\n", x);



정답은 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 의 값을 얻게 되는 것입니다.




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



반응형
이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://invitetour.tistory.com BlogIcon 휴식같은 친구 2018.04.18 12:44 신고

    정보올림피아드 수준이 꽤 높은것 같네요.
    전산전공인 저도...ㅠ
    어느학년 수준인지 궁금합니다.ㅎ

  2. 핑구야 날자 2018.04.19 06:42

    올림피아드를 준비하는 분들에게 도움이 많이 되겠어요

  3. Favicon of https://bubleprice.tistory.com BlogIcon 버블프라이스 2018.04.28 21:16 신고

    2018년 정보올림피아드 지역대회 초등부 17번 문제 풀이를 해주셔서 해당 시험을 준비하는 학생분들이게 많은 도움이 될 것 같습니다.
    이 글을 읽은 학생분들은 시험에서 좋은 결과 있길 바랍니다

반응형

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

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


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


오늘은 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 이 나오는 것을 확인 할 수가 있었습니다.


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

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


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


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


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


반응형
이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. Favicon of https://deborah.tistory.com BlogIcon Deborah 2018.04.05 06:06 신고

    아..프로그래밍은 남편이 잘 아는 분야네요. 남편이 컴퓨터 프로그래머에요. ㅎㅎ
    올려주신 자료는 잘 이해는 못하지만 구경하고 갑니다.
    행복한하루되세요.

  2. 핑구야 날자 2018.04.05 06:48

    풀이과정이 궁금했던 학생들에게 도움이 되겠어요

  3. Favicon of https://bubleprice.tistory.com BlogIcon 버블프라이스 2018.04.10 20:44 신고

    정말 시험때는 처음 보는 어려운 문제를 풀고 혼자 연구를 하다가 전문가의 조언? 힌트 등을 얻어서 문제를 푼다면 다음에 해당 문제와 같은 유형이 나왔을때 긴장하지 않고 바로 풀 수 있게 되더라고요 ^^
    2017년 지역대회 고등부 27번 문제 풀이를 해주셔서 학생분들에 많은 도움이 될것 같습니다.

반응형


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


문제

 

A, B, C, D, E가 처음 만나서 몇 명이 서로악수를 했다. 이 때, 악수를 한 두 사람의 쌍(순서쌍아님)들의 집합을 X라 하자. 적어도 한 쌍이 악수를 했고, 누구도 같은 사람과는 2번 이상 악수를 하지 않았다면 X가 될 수 있는 집합은 모두 몇 개인가?




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 가지가 됩니다.


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

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


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


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

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


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





반응형
이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 사이버몰의 이용약관 바로가기
  1. 핑구야 날자 2018.03.12 06:44

    올림피아드를 준비하는 분들에게 도움이 되겠군요 잘 알고 갑니다

  2. Favicon of https://moldone.tistory.com BlogIcon 청결원 2018.03.12 15:58 신고

    오늘도 포스팅 잘 보고 가네요~
    한주 시작 잘 하세요^^

+ Recent posts