depends on where you are going, some places like down at haeundae beach in busan will be booked out from mid july on as with places along the east coast and soraksan and prices will skyrocket then
couple of points to remember:
1) there are in many areas tons of "love motels" used for illicit meetings thing is most are nice (in fact nicer than many upscale hotels for half the price) my wife stays in them while traveling on business here, they are around bus terminals and train stations but you can find them anywhere only listing of them are in korean. check the blog brian in jeollanam-do think he has done a couple of articles on love motels
2) 99% of the love motels wont take reservations or even speak a word of english so you will have to rely on walk ins or somebody who speaks korean.
3) not many hostels here in korea think there is one in gyeongju and one here in seoul, may be a couple of others
2)