IPO(Input Process Output) 모델은 프로그램을 분석하거나 설명하는데 사용하는 가장 기본적인 모델입니다. 프로그램으로 들어오는 입력 자료의 구조와 형태, 처리 내용과 방식, 출력 자료의 구조와 형태를 명확하게 분석하거나 설계하는 것은 안정적인 프로그램의 시작이라 할 수 있습니다. [49-50] 다음과 같은 문제를 해결하기 위해 프로그램을 작성하였다. 물음에 답하시오. 무게가 서로 다른 개의 물건이 있다. 각 물건은 1부터 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과 를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, ..
2015년도 정보올림피아드 지역 예선 문제는 다시 봐도 참 출제를 잘 했다 싶습니다. 틀린 문제를 통해서도 중요한 학습을 하게 할 뿐만아니라 출제된 문제들을 통해서 C언어의 주요한 부분을 만날 수 있기 때문입니다. 이번에는 C언어의 기본 문법에 대한 문제들을 다루어 볼까 합니다. 18. 다음 중 변수의 이름으로 사용할 수 없는 것은? ① thisway ② int_char ③ star*star ④ that_way ⑤ _6_ 위의 문제는 C언어의 변수명 작성 규칙을 다룬 것으로 아래와 같이 아주 단순합니다. 변수명으로 사용할 수 있는 문자는 영문 대문자(A~Z), 소문자(a~z), 숫자(0~9), 그리고 언더스코어(_) 입니다.사용 가능한 문자 이외의 어떠한 문자도 사용할 수 없습니다(공백등의 특수 문자도 ..
이번 문제는 간단하지만 얕보다가 당할 수 있는 그러한 문제입니다. for문의 동작 원리를 아주 명쾌하게 습득 할 필요가 있습니다. 17. 다음 프로그램이 출력하는 값은? int t, i; t = 0; for (i = 0; i < 10; i++) { t++; } printf("%d %d\n", t, i); ① 10 10 ② 9 11 ③ 10 9 ④ 9 10 ⑤ 11 9 for (시작 표현식; 비교 표현식; 증분표현식) 문장 for 문법에 대해서는 "올림피아드 기출문제로 배우는 C언어 - 기본 문장"에서 많은 부분을 언급했으므로 언급하지 않은 부분, 유의할 부분을 다루겠습니다. 위의 문제에서 루프 반복 여부 검사에 사용하는 변수는 i이고 t 변수를 통해서 루프의 수행 회수를 카운트 하고 있습니다. 앞서 다룬..
정보올림피아드에 출전하고 싶은 자녀를 둔 부모 입장에서 지역 예선 기출문제를 받아보면 어떻게 도와주어야 할지 난감한 것이 사실입니다. 2014년도까지만 해도 이건 진짜 천재들이나 풀수있겠다 싶은 문제들만 수두룩했습니다. 그런데, 2015년 기출문제를 살펴보니 이제 C언어를 기초부터 탄탄한게 준비하고 집중력있게 사고력을 키운 친구들이라면 충분히 풀수 있는 문제들도 많이 출제되었습니다. 맞는 방향이 아닌가 싶습니다. 2016년의 출제 방향이 어떻게 바뀔지 모르겠지만 C언어 하나라도 제대로 공부한 사람인지를 검증하고 사고력을 묻는 문제들이 지속적으로 출제되었으면 하는 바램입니다. 그래야 경진대회를 준비하는 과정이 의미있고, 탈락한 친구들도 C언어 하나는 확실하게 익힐 수 있으니 말입니다. 이런 배경하에 201..
프로그래밍에 관심을 가지고 있는 아이를 키우다보니 부모인 저도 정보올림피아드에 매년 관심을 가지게 되는 군요. 사실 필자의 경우에도 예전에 고등학교부터 컴퓨터를 배우기 시작했는데, 학교에서 당시 대통령배 컴퓨터 경진대회를 준비하는 과정에서 엉겁결에 컴퓨터를 접하게 된것이었습니다. MSX, FC-100등 8비트 컴퓨터에 BASIC으로 프로그래밍을 배웠지만 저에게는 신세계였죠. 그리고 그것이 인생을 바꾸어 놓았지만......각설하고 올해 올림피아드 부터는 예년과는 다르게 변화된것이 많네요. 경시대회는 필기와 실기로 나누어 지는데 지역 예선에서는 실기는 하지 않고 필기만 한답니다. 즉 지역 예선에서 필기로 대상을 뽑고 실기는 바로 전국대회에서 치러지는 단순한 시스템으로 변화된 것이죠. 좋은 방향이라고 봅니다...
중딩 아들의 질문에 답하면서 느끼는 점이지만 수학 문제도, 정보올림피아드 문제도 일상 생활 과정에서 나오는 문제도 그 해결의 시작은 꼼꼼한 관찰을 통해서 명확한 것과 명확하지 않은 것을 구분하는데 있음을 다시금 깨닫게 됩니다. 집중력을 발휘해서 문제해결의 "단서", 즉 명확한 것을 찾는 작업에 정성을 들여야 함을 꼭 잊지 않아야 합니다. 이 문제에는 중요한 몇가지 단서가 있고 그것을 통해 문제를 푸는 과정은 아래와 같습니다. A, B, C, D, E가 모두 다른 수이고 1부터 9사이에 있다.A X E의 값은 9를 초과할 수 없다. 1과 2~9를 곱하는 조합, 2 X 3, 2 X 4 조합만이 존재한다.A X E = D이고 D X E = A 조건을 만족해야 한다. 단, D X E는 10이상의 값도 가능하고 ..
1. 1에서 10까지의 자연수를 모두 곱한 수를 X라고 하자. X를 8진수로 표기하면 제일 오른쪽에 연속으로 나타나는 0은 모두 몇 개일까?① 1 ② 2 ③ 4 ④ 6 ⑤ 8※ 1부터 N까지의 자연수를 모두 곱한 수를 N 팩토리얼이라하고 N!로 표기하는데 10!은 1부터 10까지를 모두 곱한 값입니다. 10!를 8진수로 변환해야 하는데 값도 크고(10!은 3,628,800) 시간을 단축할 필요가 있으므로 팩토리얼을 아래의 그림과 같이 적절하게 분해하는 것도 방법이겠습니다. 자연수인 10진수를 N진법으로 변환하는 과정은 10진수를 N으로 나누면서 그 나머지를 취하면 되는데 10!에서 8로 나누면 나머지는 0이고 몫은 8이 빠진 7! x 9 x 10이 됩니다. 또 8로 나누어야 하는데 2 x 4로 나누면 나..
C언어로 프로그램을 개발하면서 오류를 찾다가 의외의 장소에서 문제를 찾는 경우가 몇번 있었는데 바로 매크로 입니다. C언어에서는 "#define 매크로이름 매크로내용"의 형식으로 매크로를 정의하는데 이 매크로는 실행 과정에 영향을 미치는 것이 아니라 컴파일 과정에만 영향을 미칩니다. 컴파일러가 C 소스 코드를 본격적으로 컴파일하기에 앞서 전처리 과정을(precompile) 거치는데 이때 다루어지는 것이 #define문을 사용하는 매크로입니다. C언어에서는 #define 말고도 #include, #ifdef등의 전처리 문장이 있습니다. 2015년 정보 올림피아드 예선에서도 이 매크로를 다루었습니다. 위의 문제에서는 sq(x)라는 매크로를 정의했는데 이 매크로는 프로그램 실행 과정에 동작하는 것이 아니고 컴..
올해 올림피아드 예선에 아들을 데려다 주고 집에 오면서 들은 질문입니다. 내 아들이지만 머리속에 들어있는 생각은 도통 알수 없군요. 아무튼 질문을 받았으니 답을 주어야 겠지요. 이 문제는 최단 경로 계산하기라는 전형적인 문제입니다. 계산 공식에는 팩토리얼(factorial, 계승)이 쓰이므로 팩토리얼은 알아야겠지요. n 팩토리얼이라 함은 0부터 n까지의 자연수를 곱한값을 의미하고 n!로 표시합니다. 3팩토리얼은 3!로 표시하고 1X2X3의 값인 것입니다. 0부터 8까지의 팩토리얼 값은 0, 1, 2, 6, 24, 120, 720, 5040, 30320 입니다.문제는 다음과 같았습니다. C를 들러서 A에서 B까지 가는 최단 경로는 A에서 C까지 갈수 있는 최단 경로의 수에 C에서 B까지 갈수 있는 최단 경..
문제를 보니 올해 처음 참여한 아들이 C언어 공부를 좀더 열심히 했더라면 하는 아쉬움이 남습니다. C언어 기초만 잘 다졌어도 쉽게 맞출 수 있는 문제들이 꽤 있었는데 아쉬움이 있지만 C언어의 기초부터 잘 다져야 한다는 "교훈"을 마음에 새겼으면 하는 바램입니다. C언어 기초와 관련한 몇가지 문제를 풀어보면서 기초를 잘 다졌으면 합니다.18. 다음 중 변수의 이름으로 사용할 수 없는 것은?① thisway ② int_char ③ star*star ④ that_way ⑤ _6_C언어의 변수명은 다음과 같은 특성이 있습니다.영문과 숫자 그리고 밑줄(_ Underscore라 부릅니다)로 구성할 수 있습니다.영문 대문자와 소문자를 구별합니다(Case Sensitive라 합니다) C, C++, Java와 같은 프로..
제가 처음 C언어를 공부할때는 터보 C 2.0을 가지고 C언어도 공부하고 심지어 업무에도 사용했던 기억이 있습니다. 도트(dot) 프린터로 연속 용지를 가지고 인쇄하던 시절 터보 C 2.0으로 업무에 활용하여 도넛 그래프를 업무 보고에 사용했던 기억이 새롭습니다. 혹시나 해서 찾아보니 누군가 오픈 소스 프로젝트를 올려놓는 소스포지(sf.net)에 Turbo-C 2.0과 3.0을 올려두었군요. 교육용 목적으로 올려두었다는데 참고할만 합니다. http://sourceforge.net/projects/borlandtubroc/files/Borland%20Software/Turbo-C 2.0을 다운로드 받으셨다면 tc.exe를 실행하시면 아래와 같은 화면을 통해서 최근의 이클립스나 비주얼스튜디오 같으 IDE가 ..
데이터 정렬(Sort)과 탐색(Search)은 컴퓨터 시스템의 가장 기본적인 기능으로 데이터베이스, 웹 검색, 단순 입력창에 이르기까지 다양한 영역에서 사용하는 것이므로 꼭 알아두어야 할 개념입니다. 퍼스널 컴퓨터가 등장하기 이전 부터 데이터 정렬은 여러 형태로 발전되어 왔는데 예전에는 메모리가 크지 않은 환경이었으므로 이런 제약적인 환경에서도 활용할 수 있는 알고리즘부터 최대한 검색 시간을 줄이기 위하여 검색을 감안하여 정렬된 데이터로 보관하는 기법까지 다양한 알고리즘이 존재합니다. 이런 알고리즘의 복잡도는 O(빅오 Big-Oh)로 표시합니다.■ 버블 정렬(Bubble sort)한쪽 방향으로 이동하면서 인접한 두원소를 비교하여 그 방향 맨 끝에 가장 큰수 또는 가장 작은수를 배치하고 다음번에는 동일 방..
이전 포스팅 트리(Tree)의 개념에서 트리의 기본적인 개념과 실제로 많이 사용하는 이진트리에 대해서도 자세하게 살펴 보았습니다. 이번 포스팅에서는 트리의 운행 방법(traversal)과 관련된 알고리즘을 다루겠습니다. 위의 그림과 같은 이진 트리의 모든 노드를 방문하는 방법에는 3가지가 있는데 트리의 각 노드를 방문하는 방법을 트리의 운행(traversal) 또는 순회라 하고 크게 3가지 방법으로 나뉩니다. 각각의 방법은 다양한 형태로 응용하기 때문에 그 기법을을 꼭 알아두셔야 합니다. 트리(Tree)의 개념에서 이진트리의 각 노드는 Left 링크는 자식 노드를 가리키고 Right 링크는 형제 노드를 가리키도록하여 어떤 차수의 트리도 이진 트리로 표현할수 있다고 했는데 각 노드를 언제 방문하는가에 따라..
트리(Tree)는 가장 기본적인 자료구조의 하나로 실제로도 많이 사용하지만 매우 중요하기 때문에 최근까지도 매년 한 문제 이상을 꼭 출제하는 분야입니다. 개념과 연관 알고리즘을 잘 알아두셔야 합니다. 트리 구조는 그래프(Graph, 꼭지점과 변으로 구성)의 한 종류로 1개 이상의 노드로 구성되며 사이클이 없는(acyclic graph) 그래프로 임의의 두노드간에 하나의 경로만이 존재합니다. 각 노드는 서로 중복되지 않는 원소로 구성된 부속트리(subtree)를 가질 수 있습니다. 트리 구조는 나무를 거꾸로 뒤집어 놓은 형태이며 최상위 노드는 Root(뿌리) 노드라 하고 레벨 1입니다. 루트 노드 아래로 한 단계씩 레벨(깊이)을 가지며 자식(child) 노드가 없는 노드를 leaf(잎)노드 또는 termi..
아들의 이번 질문은 머리를 "콩"하고 쥐고 박고 싶은 문제입니다, 시간이 들지만 조금 집중하면 프로그램을 읽고 답할 수 있는 수준의 문제인데 아직 C언어 초보인 것을 감안하면서 차분하게 설명해 보겠습니다. 다음 프로그램의 출력 결과는 무엇인가? int x[10],y[10]; int i,j; int n = 10; for (i = 0; i < n; i++) x[i] = i + 1; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { y[j] = x[(i + j) % n]; } for (j = 0; j < n; j++) x[j] = y[j]; } printf("%d %d %d\n", x[3], x[6], x[9]); ① 10 3 6② 7 10 3③ 8 1 4④ 9 2 ..
까까머리 아들의 질문에 답하는 정보올림피아드 문제 풀이입니다. 푸는 과정에 오류가 있거나 더 좋은 방법이 있다면 댓글로 달아 주세요! 정보 올림피아드 문제들은 이렇게 저렇게 해보다가 맞추는 방식보다는 논리적인 계산 과정을 찾기를 원하는 것이므로 문제를 푸는 사람 또한 그런 시각에서 풀이 방법을 찾아야 합니다. 모빌이 좌우가 균형을 이루려면 양쪽에 가해지는 힘이 동일해야 하며 각각에 가해지는 힘은 거리와 추의 무게를 곱하는 방식으로 구할 수 있습니다. 위 그림의 B, C처럼 다단계 모빌의 경우 그 상단에 가해지는 힘은 단순히 양쪽에 달린 추의 무게의 합입니다. 실제 모빌의 경우 실의 무게나 실을 매다는 막대기의 무게 및 강도 등의 변수가 있지만 문제 는 논리적인 사고 능력을 요구하는 것임을 잊지 말아야 합..
2013년 30회 대회부터 정보 올림피아드 대회의 본선 개발 환경이 기존 비주얼스튜디오를 가지고 Visual C++ 이나 Visual Basic을 사용하던 것에서 혁명적인 변화가 있었습니다. 윈도우-비주얼스튜디오 환경에서 리눅스-이클립스 환경으로 Gnu C 컴파일러를 사용하는 것입니다. 리눅스를(우분투 12.04) 설치하고 개발 환경을 준비할 수도 있겠으나 필자는 이미 시스템이 준비되어 있는 가상 머신 이미지를 다운로드 받아 이후 환경을 설치했습니다. 가상 머신 종류가 여러개 있으나 오라클의 VirtualBox로 진행했습니다. 크기도 작고 좋았습니다. 우분투 12.04 이미지는 VirtualBox 사이트와 다른 여러곳에서 다운로드 받을 수 있습니다. 대표적인 링크로는 http://sourceforge.n..