Disclosed is a method and apparatus of encoding a video, the method including: splitting video data into a maximum coding unit; encoding the video data of the maximum coding unit based on deeper coding units of hierarchical structures in which a coding unit of an upper depth is split as a depth deepens, according to at least one split region of the maximum coding unit, and determining a coding depth at which an encoding result is to be output, including inter prediction using partitions obtained by splitting the coding unit according to arbitrary ratios; and outputting a bitstream including the encoded video data corresponding to a coding depth for the at least one split region according to maximum coding units and information regarding the coding depth and encoding modes.