I had to go through this process from Canada several times with my Korean wife. It is much better to get it while in Korea. Any police station can do it and it takes about ten minutes. The document you want is called a Criminal History Information Record (CHIR). Make sure they search 'lapsed records". Often the police won't do that if you don't specifically ask and CIC will reject it as incomplete.
You can't get a CHIR from your local Korean embassy. They will however provide you with a document similar to a power of attorney which permits you to appoint someone (friend, acquaintance) to do the search for you in Korea. Close family members can also do it for you at a police station in Korea without any special documentation.