You can show up and look for a job, but it is illegal for you to actually work without a Working Visa. If you are offered a job, you can take and overnight trip to Japan and get your Working Visa from a Korean Consulate in Japan. Then you return to Korea for work.
Now if you want a teaching job, you will most likely be told to get a criminal clearance check from your native country, or the country you have lived in over the last 5 years. If you get the clearance, it has to be stamped by your country's consulate. Then in the months that follow your employment, you will probably have to get a physical. The criminal clearance check paperwork could take a while and, getting by on your passport only, you will have overstayed your welcome after 3 months.
Legally you cannot work on a tourist visa. Many people do it, but many people get caught and deported.