Provided herein may be a semiconductor memory device and a method of operating the semiconductor memory device to program a selected physical page of the semiconductor memory device. The method may include performing a plurality of program loops. Each of the program loops may include: applying a bit line voltage based on data input to a page buffer of the semiconductor memory device; applying a two-step program pulse to a word line coupled to the selected physical page; performing a program verify operation on the selected physical page using a double verify scheme; and determining a bit line voltage to be applied in a subsequent program loop based on a result of the program verify operation.