생각하는 아이들

보호되어 있는 글입니다.

허프만 코드란 주어진 문자열을 트리를 이용해 2진수로 압축하는 알고리즘의 하나입니다. 즉 일반적으로 문자 'A'를 표현하기 위해서는 'A'의 ASCII 값이 65 이므로 2진수로 표현하면 01000001 처럼 8비트를 사용하게 됩니다. 따라서 다음과 같은 데이터를 표현할때 다음과 같은 비트를 사용하게 됩니다. AAAAAAAAAAB 라는 문자열을 표현하기 위해서는 다음과 같이 88비트를 사용하게 됩니다. 01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000001(A)01000010(B) 하지만 이것을 A는(00) B는(01) 과 같이 정의 하게 되면 다음과 같이 22비트만으로 위의 문자를 표현..

부동소수점 수(정수와 소수를 포함하는 수) 22.3125를 2진수로 변환하는 방법에 대해 알아 보겠습니다. 먼저 22.3125 에서 정수 부분과 소수 부분을 각각 2진수로 변환합니다. 변환하는 방법은 다음과 같습니다. 정수 부분은 해당 진수로 나누어 주면서 나머지를 거꾸로 읽어 가면 되며 소수 부분은 해당 진수로 곱해 주면서 정수 부분을 차례대로 표기해 주면 됩니다. 즉 22.3125는 정수 부분 10110(2) 과 소수 부분 0.0101(2) 의 합 10110.0101(2) 으로 표현 할 수 있습니다.

다음과 같은 힙(heap)에서 가장 일반적인 방법으로 세 개의 원소를 삭제하면 힙의 모양은 어떻게 되는가? 정답) 4 문제풀이) 맨위의 7이 삭제 되면 가장 뒤의 4가 맨 위로 올라 오고 다시 순서를 매칭 하면 6이 루 트로 올라가고 5가 6의 자리 4는 5의 자리로 이동하게 된다. 이와 같이 3번을 반복하면 다음과 같은 모양이 된다.

출처 : 정보올림피아드 2005년 중등부 12번 정답) 14 문제풀이)

출처 : 정보올림피아드 2005년 중등부 8번문제 정답) 5 문제풀이) 작은삼각형 9 중간 삼각형 3, 큰삼각형 1,그림의 삼각형 2 따라서 15개

정답) 1 문제풀이)

다음과 같은 도형 위에 삼각형을 그리려고 한다. 도형과 삼각형과의 교차점의 최대 개수는 몇 개인가? 출처 : 정보올림피아드 2007년 중등부 3번 정답) 10 문제풀이)

다음은 각 지점을 연결하는 도로 상황을 나타내는 그림이다. 각 도로는 화살표를 따라 일방통행만 가능하며 화살표 위에는 도로 이용 시 드는 비용이 쓰여 있다. A지점부터 K지점까지 가는데 드는 최소 비용은 얼마인가? 출처 : 정보올림피아드 2007년 초등부 13번 정답) 9 이렇게 찾아가는 알고리즘으로는 다익스트라 알고리즘이 있다. A,B,C,D,E,F,G,H,I,J,K 0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF 먼저 위와 같이 A출발점만 0 을 설정하고 A에서 갈 수 있는 곳을 A까지 온 거리 누적해서 최단거리를 설정한다. A,B,C,D,E,F,G,H,I,J,K 0,3,1,5,INF,INF,INF,INF,INF,INF,INF 여기서 그 다음 방문하지 않은 곳에서 가장 짧은..

출처 : 정보올림피아드 2007년 초등부 6번 문제 정답) 3 문제풀이) 위와 같이 정사각형과 정삼각형의 형태를 살펴보면 정삼각형이 정사각형을 채울수가 없다. 따라서 B1B2 와 C1C2의 길이의 합은 B2C2 의 길이보다 더 길어 지게 된다. 따라서 빗금친 부분이 내부의 정사각형보다 크다.