A video encoding apparatus includes: an inter prediction unit to determine a motion parameter of a current block and generate a predicted block of the current block, by performing a motion estimation on the current block; and an optimal mode determining unit to set a prediction mode of the current block as a SKIP mode when (i) the motion parameter of the current block is identical to a motion parameter of a candidate block among a plurality of candidate blocks and (ii) all-zero coefficients result from a transform and a quantization performed on a residual data block representing the difference between the current block and the predicted block.