PS 란? (알고리즘)

Problem Solving 이란?

용어 사용, 용어 해석에 있어 작성자의 개인적인 생각이 포함되어 있습니다.

• The Feynman Algorithm

1. Write down the problem
2. Think hard
3. Write down the solution

Problem Solving(이하 PS)은 '문제 해결'이라는 단어 그대로 주어진 문제를 적절하게 해결 할 수 있는 방법을 찾아 해결하는 것을 뜻합니다.

---

!

 

프로그래밍으로 본다면 '원하는 결과를 적정한 시간과 메모리 이내에 처리하는 프로그램을 만드는 것'을 뜻합니다.

• 여기서 '적정한 시간'은 사람이 문제를 해결하는데 걸리는 시간이 아니라, 해당 프로그램이 입력을 받은 후 결과를 내놓기 전까지 걸린 시간을 의미합니다.

---

예시

정수 A와 B를 입력받아 A+B를 출력하는 프로그램을 작성하시오.
(0≤ A, B ≤ 1,000,000,000 / 시간제한 : 0.5초 / 메모리제한 : 100MB)

• 예시 입력 : 5 6
• 예시 출력 : 11
• 간단한 예시지만, 어떻게 짜야할지 한번 생각해봐 주세요.
  위 예시를 해결하기 위한 코드는 다양한 언어로, 다양한 방식으로 짤 수 있습니다. 저는 자바와 파이썬으로 짜봤습니다. 하나로 정해진 정답같은건 없습니다. 위 제시된 문제를 해결만 할 수 있다면 정답입니다.

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.print(a+b);
    }
}

Python

a,b = map(int, input().split())
print(a+b)

• 이렇게 어떠한 문제를 해결하는 코드를 짜는것을 PS라고 합니다. 물론 방법은 한가지가 아닙니다. 단순하게 A, B를 입력받아 출력하는 프로그램이라도 여러사람에게 시켜보면 같은 코드가 나오기는 힘듭니다.
  예를들어 위 Java 예시에서 Scanner로 입력받지않고 BufferedReader를 사용하여 입력받을수도 있고, Scanner로 nextLine()을 받아 split() 후 parseInt() 할수도 있습니다. Python 예시에서도 map으로 int로 변환해서 받지않고 그냥 a,b에 바로 받은 뒤 print하는곳에서 int로 형변환하는 사람도 있겠죠.
• 어떤 방식으로 문제를 해결하던지 해당 시간제한, 메모리제한내에 수행 가능한 프로그램이라면 문제를 해결한것입니다.*

---

PS는 경계가 모호한 면이 있어 여러 단어로 불립니다.

• 알고리즘은 대중적으로 가장 잘 알려진 단어라 보통 구체적으로 설명하기 뭐하면 그냥 알고리즘이라고 설명하곤 합니다(그냥 PS한다고 하면 포토샵 하는줄 암). 실제로는 자료구조, 알고리즘, 수학적 사고방식, 구조적 생각능력, 구현력(?) 등 여러가지가 복합적으로 필요하지만 가장 두드러지는 부분이 알고리즘이므로 PS를 설명하기에 부적합한것도 아닙니다.
  또한 알고리즘이라는 단어를 흔히 프로그래밍에서 말하는 프로시저(BFS, DFS, 다익스트라 처럼)로 보는 것 외에, 단어의 정의 그대로 '문제를 해결하기 위한 절차나 방법'으로 넓게 보면 역시 PS라고 할 수 있으니 딱히 틀린 용어 사용도 아닙니다.
• 특정 기업들에서 입사할 때 보는 코딩테스트(이하 코테)도 PS에 속합니다. 코딩테스트도 결국 위 '예시'와 같이 문제를 주고 시간제한, 메모리제한을 두고 문제를 푸는 것입니다. 다만 프로그램이 동작하는 시간제한 외에 추가적으로 문제를 읽고 해결하는데까지 걸리는 총 시간에 제한을 두며, 상대평가로 빨리 해결할수록 좋겠죠.
• 위의 코테처럼 마치 스포츠처럼 서로 경쟁하며 PS 하는것을 CP(Competitive Programing)라고 별도 단어로 표현하기도 합니다. 정보 올림피아드나 Topcoder, Codeforces와 같은 온라인 프로그래밍 대회, 구글 코드잼 등과 같은 PS대회가 CP에 해당하며, 결국 CP도 PS의 일부분 입니다.
• 전반적으로 PS를 취미로 하고있는 사람들끼리는 그냥 'PS' 라고만 명명하면 다들 알아먹고, 대중적으로 말할때는 그냥 '코테같은거' 라던지 '알고리즘 푼다' 정도로 말합니다.

---

그래서 PS가 일하는데 도움이 됨?

• 회사에서 개발하는 것 자체를 PS라 볼 수 있습니다.
  '배관 데이터를 보여주는 리스트 화면을 만드시오.'
  '해당 리스트에 항목을 클릭 시 해당 항목의 상세 내용을 보여주는 화면으로 이동'
  ...
  다만 주로 사용하는 라이브러리의 사용법을 익히고, 프레임워크의 사용법을 익히는게 더 효율적일수도 있습니다. 실상 대부분의 개발업무에서 알고리즘이 필요한 연산의 대부분은 쿼리 수준에서 처리됩니다.
• 코딩을 잘하는데 PS를 못하는 사람은 있어도, PS를 잘하는데 코딩을 못하는 사람은 없습니다.
  물론 과유불급이라는 말이 있듯이, 너무 과한 수준으로 한다면 현업 업무와 동떨어진 수준이 될 수는 있습니다. (A+B를 기똥찬 방법으로 빠르게 출력하는 프로그램은 짤 수 있지만, A와 B를 입력받아 A+B를 웹페이지에 출력하는 웹개발은 못한다던지)
• PS는 결국 현재 제시된 문제를 파악하는 능력, 문제를 해결하기 위한 적절한 자료구조와 알고리즘 등을 사용하는 능력, 생각난 해결법을 코드로 옮기는 구현력 등이 모두 필요합니다. 효율성은 차치하더라도 도움이 안될수는 없습니다. 특히 뭔가를 짜야 할 때 자신감이 생길 수 있습니다.

---