0과1

1. 문제정의 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다. 모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 그림을 가로 세로로..

1. 문제정의 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다. 판자의 너비는 모두 1이라고 가정합니다. 입력 첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 ..

알고리듬을 평가하는 두가지 기준 1. 시간 : 알고리듬의 수행 속도의 특성을 분석 2. 공간 : 알고리듬의 메모리 사용 특성을 분석 -> 시간이 빠르면서 메모리도 더 적게 사용하는 알고리듬이 이상(理想)! BUT! 두 기준은 서로 상충하는 경우가 많다. 즉, 메모리 사용량을 희생해 속도를 높이거나, 속도를 희생해서 메모리 사용량을 줄여인 알고리듬들을 훨씬 자주 볼 것이다. 시간복잡도 분석(Time complexity) 알고리듬의 수행 속도를 측정하는 방법 1. 프로그램의 수행 시간을 측정(Timer) -> 가장 직관적인 방법이지만 하드웨어, 사용 언어, 운영체제 등 외부 요소가 시간에 영향을 미치므로 부적합! 2. 수행 시간 기준 기본적인 연산의 수 비교 (ex. 사칙연산, 대소비교, 대입연산) -> 가..

알고리듬? 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것 ※ 좋은 알고리듬은 아래 특징을 따른다. 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다. 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. 타당성 : 구현할 수 있고 실용적이어야 한다. 입력 : 정의된 입력을 받아들일 수 있어야 한다. 출력 : 답으로 출력을 내보낼 수 있어야 한다. 유한성 : 특정 수의 작업 이후에 정지해야 한다. 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다. 알고리듬 구현 방식? 자연어, 의사코드, 순서도, 프로그래밍 언어로 다양 알고리듬 개발의 정형적인 단계 문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화 즉,..