[Spring] 절차지향/객체지향/함수형 프로그래밍 & 시간복잡도/공간복잡도

Q. 절차지향 / 객체지향 / 함수형 프로그래밍이란 무엇이고 차이점은 무엇인가?

 

절차지향 프로그래밍은 프로그램의 순서와 흐름을 먼저 세우고, 필요한 자료구조와 함수들을 설계하는 방식입니다.

대표적인 프로그래밍 언어로 C, Visual Basic, Fortran, Pascal이 있습니다.

 

특징

• 하나의 큰 기능을 처리하기 위해 작은 단위의 기능들로 나누어 처리하는 Top-Down 접근 방식으로 설계된다.
• 데이터와 함수를 별개로 취급한다.
• 모든 함수는 데이터 공유가 가능하다.
• 정해진 순서대로 입력해야 하므로 순서가 바뀌면 결과를 도출하기 어렵다.
• 프로그램이 커질수록 구조가 복잡해져 유지보수가 어렵다. (소형 프로젝트에 적합)

 

객체지향 프로그래밍은 자료구조와 이를 중심으로 한 모듈들을 먼저 설계한 다음에, 이들의 실행순서와 흐름을 짜는 방식입니다.

대표적인 프로그래밍 언어로 C++, C#, Java, Python이 있습니다.

 

장점

• 상속, 캡슐화, 다형성의 특징으로 코드를 재사용하거나 확장하기 좋아서 유지보수가 쉽다.
• 관련이 많은 객체의 상호작용을 생각해 실세계에 대한 모델링을 좀 더 쉽게 해준다.
• 캡슐화 특징으로 실제로 구현되는 부분을 외부에 드러나지 않도록 은닉하여 보안성이 높다.

단점

• 캡슐화와 격리구조 때문에 절차지향 프로그래밍보다 실행 속도가 느리다.
• 객체 단위의 구성으로 필요한 절차지향 프로그래밍보다 메모리 비용이 크다.

특징

1. 추상화(abstraction)

구체적으로 정의하는 것이 아니라 필요한 정보만을 중심으로 간소화 하는 것을 의미한다. 지하철 노선도 처럼 실제 지형도보다 지하철역 간의 상대 위치가 중요하게 정리된 것이 추상화의 대표적인 예로 볼수 있다.

2. 캡슐화(Encapsulation)

객체가 독립적인 역할을 할 수 있도록 데이터와 기능을 하나로 묶어서 관리하는 것을 말한다. 실제로 구현되는 부분을 외부에 드러나지 않도록 하여 정보를 은닉할 수 있다.

3. 상속성(Inheritance)

하나의 클래스가 가진 데이터나 기능을 다른 클래스가 그대로 물려받는 것을 말한다. 기존 코드를 재사용하여 확장시킬 수 있다.

4. 다형성(Polymorphism)

하나의 클래스나 메서드가 다양한 방식으로 동작이 가능한 것을 말한다. 오버라이딩과 오버로딩이 있다.

오버라이딩(Overriding): 상속받은 자식 클래스에서 부모 클래스의 메서드와 같은 이름을 사용하고 매개변수와 리턴 타입도 같은 상태에서 기능을 재정의하는 것을 말한다.
오버로딩(Overloading): 같은 이름의 함수를 매개변수를 다르게 하여 기능을 재정의하는 것을 말한다.

 

함수형 프로그래밍은 순수 함수를 조합하고 프로그램을 만드는 방식입니다.

대표적인 언어로는 Haskell, Scala, Clojure 등이 있습니다.

 

특징

• 함수형 프로그래밍은 과정(Process)보다 결과(Result)에 관심이 많다.
• 무엇(What)이 실행될 지를 강조한다.
• 데이터는 불변(immutable)하다.
• 함수형 프로그래밍은 문제를 함수로 분해(Decompose)한다.
• 함수형 프로그래밍은 수학적 함수의 개념에 기반한다.
• 함수형 프로그래밍은 If-Else와 같은 조건문 혹은 반복문을 지원하지 않는다.

 

 

Q. 알고리즘에서 '시간복잡도'와 '공간복잡도'란 무엇인가? 그리고 이것들은 왜 중요한가?

 

알고리즘 성능을 평가하기 위해 복잡도의 척도를 사용합니다. 동일한 기능을 수행하는 알고리즘이 있을 때 복잡도가 낮을수록 좋은 알고리즘이라고 합니다. 

 

최근 대용량 시스템이 보편화되면서 공간복잡도보다는 시간복잡도를 더 우선하여 프로그래밍을 작성합니다.

 

시간복잡도는 특정 알고리즘이 문제를 해결하는데 걸리는 시간을 의미합니다.

 

빅-오 표기법 : 최악의 경우를 계산하는 방식

시간복잡도 그래프

faster O(1) < O(log n) < O(nlog n) < O(n²) < O(2ⁿ) slower

빅-오 표기법 예제

• O(1) : 스택의 Push, Pop
• O(log n) : 이진트리
• O(n) : for 문
• O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
• O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
• O(2ⁿ) : 피보나치 수열

 

공간복잡도는 작성한 프로그램이 얼마나 많은 메모리를 차지하느냐를 분석하는 방법입니다.

 

a = 5;

공간이 하나 생성되는 것을 1이라고 표현합니다. O(1)

 

sum = 0;
for(int i = 0; i < 10; i++) {
	sum += i;
}

반복문이 N번 반복해도 for문 안에서의 지역변수이므로 공간복잡도는 O(1)입니다.

 

public int factorial(n) {
	if(n == 1) {
    	return 1;
    }
    return n * factorial(n-1);
}

재귀함수의 경우 매개변수 n의 값에 따라 공간복잡도가 달라지므로 공간복잡도는 O(n)입니다.

 

알고리즘 성능 분석의 필요성

 

프로그램의 규모는 시간이 지날수록 방대해지고 있어 처리해야하는 데이터 양이 많아지고 있습니다.

입력하는 데이터가 적을 때는 상관없지만 양이 많아지면 알고리즘간 효율성 차이가 커집니다.

입력 데이터 수	알고리즘A (n^2)	알고리즘B (2^n)
n = 6	36s	64s
n = 100	10,000s	2^100s

알고리즘 실행에 걸리는 시간이 짧고, 연산하는 컴퓨터 내의 메모리 같은 자원을 덜 사용하는 효율적인 프로그래밍을 위해 알고리즘 성능 분석이 필요합니다.

 

 

 

참고

https://dev-jwblog.tistory.com/86

https://code-lab1.tistory.com/245

https://velog.io/@goblin820/%EC%A0%88%EC%B0%A8%EC%A7%80%ED%96%A5-%EB%B0%8F-%EA%B0%9D%EC%B2%B4%EC%A7%80%ED%96%A5-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D

https://velog.io/@cha-suyeon/Algorithm-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%B5%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

https://madplay.github.io/post/time-complexity-space-complexity