이전 포스팅 트리(Tree)의 개념에서 트리의 기본적인 개념과 실제로 많이 사용하는 이진트리에 대해서도 자세하게 살펴 보았습니다. 이번 포스팅에서는 트리의 운행 방법(traversal)과 관련된 알고리즘을 다루겠습니다. 위의 그림과 같은 이진 트리의 모든 노드를 방문하는 방법에는 3가지가 있는데 트리의 각 노드를 방문하는 방법을 트리의 운행(traversal) 또는 순회라 하고 크게 3가지 방법으로 나뉩니다. 각각의 방법은 다양한 형태로 응용하기 때문에 그 기법을을 꼭 알아두셔야 합니다. 트리(Tree)의 개념에서 이진트리의 각 노드는 Left 링크는 자식 노드를 가리키고 Right 링크는 형제 노드를 가리키도록하여 어떤 차수의 트리도 이진 트리로 표현할수 있다고 했는데 각 노드를 언제 방문하는가에 따라..
트리(Tree)는 가장 기본적인 자료구조의 하나로 실제로도 많이 사용하지만 매우 중요하기 때문에 최근까지도 매년 한 문제 이상을 꼭 출제하는 분야입니다. 개념과 연관 알고리즘을 잘 알아두셔야 합니다. 트리 구조는 그래프(Graph, 꼭지점과 변으로 구성)의 한 종류로 1개 이상의 노드로 구성되며 사이클이 없는(acyclic graph) 그래프로 임의의 두노드간에 하나의 경로만이 존재합니다. 각 노드는 서로 중복되지 않는 원소로 구성된 부속트리(subtree)를 가질 수 있습니다. 트리 구조는 나무를 거꾸로 뒤집어 놓은 형태이며 최상위 노드는 Root(뿌리) 노드라 하고 레벨 1입니다. 루트 노드 아래로 한 단계씩 레벨(깊이)을 가지며 자식(child) 노드가 없는 노드를 leaf(잎)노드 또는 termi..
진법은 수를 표현하는 방법을 나타내는 것으로 일상 생활에서 일반적으로 사용하는 진법은 10진법입니다. 십진수 2345는 다음과 같이 표현 할 수 있습니다. 위의 식은 각 진법을 지수 형태로 표현한 것입니다. N진수를 10진수로 변환하는 방법은 위의 식과 같이 N진수의 각 자릿수에 해당하는 밑수 N(base)을 n제곱한 값에 각 자리의 값을 곱한 결과를 합산하는 것입니다. 모든 밑수의 의 값은 1입니다. 반대로 10진수를 N진수로 변환하는 방법은 아래의 그림과 같이 십진수를 N으로 나누면서 더이상 나누어지지 않을 때까지 나머지를 계산하고 그 결과를 배열하면 됩니다. 2진수는 맨 우측부터 3자리씩 묶으면 8진수로 4자리씩 묶으면 16진수로 손쉽게 변환 할 수 있습니다. 이런 특성 때문에 컴퓨터에서 2진수, ..
아들의 이번 질문은 머리를 "콩"하고 쥐고 박고 싶은 문제입니다, 시간이 들지만 조금 집중하면 프로그램을 읽고 답할 수 있는 수준의 문제인데 아직 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 ..
아이 때문에 문제를 풀어보기는 하지만 "정말 어렵구나"하는 탄식이 절로 나옵니다. 이럴때는 머리 좋은 사람들이 얼마나 부러운지......그럼에도 불구하고 생각을 조금 집중하면 천재가 아니어도 풀수있는 문제들이 있습니다. 이번에 아이가 질문해온 문제는 아래와 같습니다. * 네 명의 선생님 A, B, C, D 와 다섯 명의 학생 E, F, G, H, I 가 세 개의 조로 나누어서 봉사활동을 하기로 하였다. 다음과 같은 조건으로 세 개의 조 1, 2, 3으로 나눈다고 할 때, 아래 질문에 답하시오.(1) 각 조는 반드시 세 명으로 구성되어야 한다.(2) 각 조에는 적어도 한 명의 선생님이 포함되어 있어야 한다.(3) E와 H는 같은 조에 배치되어야 한다.(4) D와 F는 같은 조에 배치되어서는 안된다.(5) ..
C 언어를 처음 배우는 사람들이 어려워하고 잘 이해하지 못하는 것중에 하나가 포인터(Pointer)와 함께 재귀함수(recursive function)입니다. C언어의 재귀함수는 단순하게 함수 내부에서 자신을 호출하는 것을 의미합니다. 그렇지만 프로그래밍 영역에서 많이 사용하는 개념이니만큼 올림피아드에서도 출제 빈도가 높습니다. 일단 제 아들이 질문한 문제를 먼저 만나보도록 하겠습니다. 이런 문제는 프로그램을 읽는 능력을 알아보기 위한 것으로 실제 업무 영역에서도 프로그래밍 능력은 이러한 프로그램 읽기 능력과 비례한다고 해도 과언이 아닙니다. 재귀함수를 대할 때 가장 유념해야 할 것은 변수의 영향 범위(Scope)입니다. C언어는 함수 내부에 선언한 변수는 지역(Local) 변수로 다른 함수에서는 전혀 ..
까까머리 아들의 질문에 답하는 정보올림피아드 문제 풀이입니다. 푸는 과정에 오류가 있거나 더 좋은 방법이 있다면 댓글로 달아 주세요! 정보 올림피아드 문제들은 이렇게 저렇게 해보다가 맞추는 방식보다는 논리적인 계산 과정을 찾기를 원하는 것이므로 문제를 푸는 사람 또한 그런 시각에서 풀이 방법을 찾아야 합니다. 모빌이 좌우가 균형을 이루려면 양쪽에 가해지는 힘이 동일해야 하며 각각에 가해지는 힘은 거리와 추의 무게를 곱하는 방식으로 구할 수 있습니다. 위 그림의 B, C처럼 다단계 모빌의 경우 그 상단에 가해지는 힘은 단순히 양쪽에 달린 추의 무게의 합입니다. 실제 모빌의 경우 실의 무게나 실을 매다는 막대기의 무게 및 강도 등의 변수가 있지만 문제 는 논리적인 사고 능력을 요구하는 것임을 잊지 말아야 합..
2013년 30회 대회부터 정보 올림피아드 대회의 본선 개발 환경이 기존 비주얼스튜디오를 가지고 Visual C++ 이나 Visual Basic을 사용하던 것에서 혁명적인 변화가 있었습니다. 윈도우-비주얼스튜디오 환경에서 리눅스-이클립스 환경으로 Gnu C 컴파일러를 사용하는 것입니다. 리눅스를(우분투 12.04) 설치하고 개발 환경을 준비할 수도 있겠으나 필자는 이미 시스템이 준비되어 있는 가상 머신 이미지를 다운로드 받아 이후 환경을 설치했습니다. 가상 머신 종류가 여러개 있으나 오라클의 VirtualBox로 진행했습니다. 크기도 작고 좋았습니다. 우분투 12.04 이미지는 VirtualBox 사이트와 다른 여러곳에서 다운로드 받을 수 있습니다. 대표적인 링크로는 http://sourceforge.n..