2023-02-27

면접 스터디를 시작하고 매주 받는 과제들로부터 조사한 내용들의 정리

 

 

 

 

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

프로그래밍 패러다임의 대표적인 방법들 입니다.

 

절차 지향 프로그래밍

데이터와 함수를 분리해서 생각하는 방식으로, 순차적으로 처리되는 프로그램을 만드는 데 중점을 두는 프로그래밍 방식 입니다.

코드의 가독성이 좋으며 컴퓨터의 처리구조와 비슷해 실행속도가 빠릅니다. 하지만, 각각의 코드가 순서대로 실행되기에 유지보수에 있어 불리합니다.

 

객체 지향 프로그래밍

객체를 중심으로 프로그래밍 하는 방식으로, 객체의 상호작용을 통해서 프로그램을 구현합니다.

추상화, 캡슐화, 상속성, 다형성 이라는 4가지 특징 덕분에 코드의 재사용이 가능해 확장과 유지보수에 있어서 유리합니다. 하지만, 상대적으로 처리속도가 느리며 설계시 많은 시간이 소요됩니다.

 

함수형 프로그래밍

입력과 출력만으로 구성된 함수를 조합하여 프로그램을 구현하는 방식입니다.

“순수 함수” 만을 사용해 상태 제어라기 보다는 빨리 처리하는데 초점을 둔 방법입니다. 실행 순서를 지정하지 않기에 비절차형 언어라고도 합니다.

어떠한 외부 요인도 함수의 입출력에 영향을 주지 않기 때문에 외부 상태로 인한 부작용이 없어 안정적이라는 특징이 있습니다.

함수의 동작부가 간결해 객체지향에 비해 코드 이해도와 가독성이 좋고 테스트에 용이합니다. 하지만, 외부 데이터 혹은 내부 데이터의 상태를 조작할 수 없습니다.

 

// 순수 함수
void sum(a, b) {
	return a + b;    // 인자로 들어온 값만 참조해, 리턴값을 생성합니다.
}

// 비순수 함수
void sum(a, b) {
	return a + b + c; // 외부 요인(c)에 따라 리턴값이 변경됩니다.
}

데이터와 함수의 관점, 프로그램의 구조, 코드의 재사용성 등의 차이가 있습니다.

 

정리하자면..

절차지향 프로그래밍은 수행해야할 기능을 순차적인 처리 과정으로 진행하는 방식,

객체지향 프로그래밍은 객체들의 집합으로 프로그램의 상호작용으로 진행하는 방식,

함수형 프로그래밍은 순수 함수를 조합하여 소프트웨어를 만드는 방식입니다.

 

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

알고리즘의 효율성(성능)을 평가하는 두가지 방법입니다.

 

시간 복잡도

알고리즘이 문제를 해결하는 데 걸리는 시간을 말합니다.

이를 측정하는 방법으로 점근적 표기법을 사용하는데, 대표적인 표기법으로는 Big-O 표기법이 있습니다.

 

표기법의 종류

• Big-O : 최악의 경우
• Big-Omega : 최선의 경우
• Big-Theta : 평균적인 상황의 경우

보통 Big-O 표기법을 가장 많이 사용합니다.

그 이유는, 대부분의 경우 가장 최악의 경우에 어떻게 될 것인지가에 가장 무게를 두기 때문입니다.

즉, 최악의 경우 얼마나 나빠질 수 있는지에 대해서 가장 신뢰를 얻고 있습니다.

 

표기법을 사용하는 이유는 알고리즘의 효율성을 나타내는 지표이기 때문입니다.

또 다른 개발자와 알고리즘에 대하여 얘기할 때, 표기법을 이용하여 소통하는 편이 더 원할하기 때문입니다.

 

읽어도 이해가 않가는 표기법 설명
표기법은 수학적으로 생각한다면,

• 요소 n 이 증가하면 그에 비례해서 시간이 일정하게 증가하는 경우 n만큼 걸린다고 볼 수 있습니다.
• 그리고 2배로 비례해서 증가한다면 2n 이 됩니다.
• 또, 제곱으로 비례해서 증가한다면 n2 라고 볼 수 있습니다.

이렇게 입력값의 크기에 따라 알고리즘이 얼마나 실행속도가 증가하는지 알아보는 것을 실행 시간의 성장률(rate of growth) 이라고 부릅니다.

6n2 + 100n + 300 이라는 성장률에 대한 함수가 있을 때, 우리는 이를 간소화해서 보는 편이 더 좋을 것입니다. 실제로 n이 증가함에 따라 6n2 에 비해서 100n + 300의 비중은 그리 크지 않게 됩니다.

 

따라서 우리는 약속을 합니다. 계수인 6, 그리고 나머지 항목인 100n + 300을 제외하고 실질적으로 알고리즘의 실행속도에 가장 큰 영향을 미치는 부분인 n2 만으로도 충분하다는 의미입니다.

 

이렇게 중요하지 않은 항과 상수 계수를 제거하면 알고리즘을 이해하는데 방해되는 불필요한 부분을 생각하지 않을 수 있어서 알고리즘에서 중요한 부분인 성장률에 집중할 수 있습니다.

 

이렇게 중요하지 않은 항과, 상수 계수를 제거한 표기법을 점근적 표기법이라고 합니다.

 

 

 

 

공간 복잡도

알고리즘이 완료에 얼마나 많은 공간(메모리) 를 필요로 하는지를 의미합니다.

다만, 최근에는 컴퓨터 성능의 발달로 인해 메모리의 여유 공간이 많아졌기 때문에 시간 복잡도에 더 무게를 두고 사용합니다.

공간복잡도를 결정하는 요소에는 보통 배열의 크기, 동적할당에서 얼마만큼이 예상되는지, 재귀함수라면 호출빈도 등이 영향을 미칩니다.

따라서, 프로그램 또는 알고리즘에 필요한 공간은 크게 두가지로 나눌 수 있습니다.

1. 고정 공간
2. 가변 공간

이렇게 나눌 수 있습니다.

 

시간적인 측면을 무시하고 공간복잡도만을 고려한다면, 고정 공간보다는 가변 공간을 사용할 수 있는 자료구조들을 사용하는 것이 효율적입니다.

 

또한 함수 호출시 할당되는 지역 변수들이나 동적 할당되는 객체들도 모두 공간이 필요합니다.

 

특히 재귀함수의 경우 매 함수 호출마다 함수의 매개변수, 지역변수, 함수의 복귀 주소 등을 저장할 공간이 필요하기 때문에 반복문으로도 가능하다면 반복문으로 짜는 것이 더 효율적입니다.

 

알고리즘의 효율성을 판단하는 중요한 기준이 되기 때문에 이들을 사용합니다.