A video encoding apparatus includes a candidate block type configuration unit for configuring block type candidates for encoding an image by using variable sized macroblocks; a video encoder for encoding an input image for each block type candidate; and a block type determiner for determining a block type based on encoding costs by the block type candidate, and generating a bitstream including image data encoded by the determined block type and information for the determined block type. Determining the block type to match the image characteristics enables combinations of diverse modes such as a large block and macroblock size, a minimum subblock size, available divisional block type, prediction mode type within a macroblock, and so on to achieve more effective encoding and decoding of high resolution images.