A method of encoding a video includes: splitting a picture into a maximum coding unit; for the maximum coding unit, determining coding units having a tree structure including coding units of coded depths and determining encoding modes for the coding units of the coded depths by performing encoding based on coding units according to depths, the coding units according to depths obtained by hierarchically splitting the maximum coding unit as a depth deepens; and outputting information about a maximum coding unit size and, for the maximum coding unit, information indicating an order of split information and skip mode information which is selectively determined for the coding units according to depths, information about the encoding modes for the coding units of the coded depths including the split information and the skip mode information which are arranged according to the order, and encoded video data.