면접대비 - 프로그래밍, 시간복잡도 vs 공간복잡도

🙃아직 2차 정리가 필요한 글!

 

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

 

프로그래밍 패러다임 종류

 

📍절차지향 프로그래밍 (구조적)

• 실행 순서, 절차가 중점, 프로그램 전체가 유기적으로 연결되는 프로그래밍 방식
• 전체 기능의 동작을 고려해 단계별로 기능을 구현
• 컴퓨터의 처리구조와 유사하기 때문에 객체지향보다 속력이 빠르다.
• 프로젝트가 커지면 그만큼 구조가 복잡해진다
• 순서를 바꾸기 어려우며, 중복 코드의 가능성이 높아 유지보수가 어렵다. 디버깅 또한 어렵다 
• 대표적인 언어 C

 

📍객체지향 프로그래밍

• 객체들의 종류와 속성을 중점
• 필요한 데이터를 추상화 시켜 상태와 행위를 가진 객체를 만들고, 객체를 설계하여 각 객체의 상호작용을 설계하는 방식
• 특징은 4가지: 캡슐화, 상속, 추상화, 다형성
• 절차지향보다는 속도가 느리지만 구조 파악이 쉽다
• 객체로 코드를 재사용하여 생산성을 높이며, 유지보수가 쉽다.
• 대표적인 언어로 자바, 파이썬, C++ 등이 있다.

 

📍 함수형 프로그래밍

• 자료처리를 수학적 함수의 계산으로 취급해 상태와 가변 상태를 멀리한다. 
• 함수형 프로그래밍은 수학과 밀접한 연관이 있어 배우는 것이 어렵지만 최근 AI,빅데이터 등으로 방대한 데이터를 빠르게 병렬적으로 계산할 필요로 각광받기 시작
• 함수형 프로그래밍 만을 위한 언어도 존재하지만 객체지향 프로그래밍에 함수형 프로그래밍의 특징을 접목한 프로그래밍 언어도 있다. 자바도 그 중 하나이다.
• 어떤 값을 넣어도 항상 동일한 결과 값을 갖는 순수함수를 갖는다. 함수에서 외부 상태값을 참조하거나 외부 상태를 변경하는 건 순수 함수가 아니다.
• 데이터는 비상태성,불변성을 가져야 한다. 함수에 인자로 전달된 데이터를 변경하는 건 함수형이 아니며, 함수형 경우 데이터가 변경이 필요하다면 그건 원본데이터를 변경하는게 아니라 복사본으로 새롭게 만들어 변경하여 반환하는 방식으로 사용한다. 
• 선언형 함수로 if, switch, for 등의 명령문을 사용하지 않고 함수형 코드를 사용해야한다.
• 자바에서는 JDK8 부터 StreamAPI와 함수형 인터페이스 람다를 제공하고 있다. 

 

📍인터프리터란

 

📍객체란 

객체는 프로그램에서 사용되는 데이터 또는 식별자에 의해 참조되는 공간을 의미하며 값을 저장 할 변수와 작업을 수행 할 메소드를 서로 연관된 것들끼리 묶어서 만든 것을 객체라고 할 수 있다. 

 

📍StreamAPI

 

📍람다

 

https://choirim.tistory.com/69

https://www.youtube.com/watch?v=4ezXhCuT2mw

 

 

 

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

📍시간 복잡도

알고리즘이 문제를 해결 하는데 걸리는 시간 ( 실제로는 연산 실행 횟수 ) 

최고차항을 제외한 모든 항과 최고차항의 계수를 제외시킨다. 

 

📍공간 복잡도

알고리즘이 문제를 해결 하는데 사용하는 메모리 ( 고정 공간과 가변 공간을 더해 구함 )

 

S(P) = c + Sp(n)c: 고정 공간 (코드 저장 공간, 단순 변수, 고정크기의 구조 변수, 상수)Sp(n): 가변 공간 (동적으로 필요한 공간)

 

📍공통점

둘다 알고리즘 성능 분석 방법. 하드웨어와 상관없이 알고리즘 그 자체 만을 평가하기 위한 방법.

 

📍표기법

점근적 표기법

Big-O (빅오): 최악의 경우를 표기, 상한

Big-Omega (빅오메가): 최선의 경우를 표기, 하한

Big-Theta (빅세타): 평균, 상한과 하한의 교집합

 

📍서로 관계

서로 반비례 하는 경향이 있다 

 

📍왜 중요할까?

알고리즘 분석을 빠르게 할 수 있고, 언제 무엇에 쓸지 빠르게 파악이 가능하다

개발자로 하여금 자신의 코드가 미래에 어떻게 작동할지 알 수 있기 때문에 코드를 평가하여 더 나은 방법을 찾아볼 수 있게 한다. 

 

📍알고리즘

어떤 문제를 풀거나 계산하기 위한 일련의 유한한 절차 

 

📍좋은 알고리즘은 어떤걸까요?

- 모든 입력에 대한 올바른 출력을 생성

- 적은 실행시간과 적은 메모리 사용으로 효율적인 실행

- 다른사람이 이해하기 쉬운 알고리즘

- 재사용하기 좋은 알고리즘

 

📍좋아하는 알고리즘이 있나요?

정렬 알고리즘에 흥미가 있다

버블, 선택, 삽입 알고리즘 셋다 같은 O(n^2)의 시간 복잡도를 가지고 있지만 과정과 평균 성능으로 보면 전혀 다른 차이를 보인다. 어떤 것을 판별하는데 단 한가지 요소가 아니라 여러가지 요소를 가지고 detail하게 판별해봐야 한다는 생각이 들어 흥미를 갖게 되었다. 

 

- 버블 정렬 알고리즘 : 앞에서 부터 2개씩 비교하여 완전히 정렬될 때까지 비교와 스왑을 반복하는 알고리즘. 한번의 싸이클당 n-1 비교와 여러번의 스왑이 일어날수 있으며 마지막 위치면 다시 앞으로 돌아가 반복.

- 선택 정렬 알고리즘 : 전체의 아이템 중 가장 작은 아이템의 위치와 현재 아이템의 위치를 스왑하는 알고리즘. 가장 작은 아이템부터 앞에서 정리하기 때문에 한 싸이클당 n-1번 비교하는 것은 동일하나 단 한번의 스왑이 일어난다.

- 삽입 정렬 알고리즘 : 두 알고리즘과 달리 전체를 비교해서 정렬하는 것이 아닌 삽입하려는 아이템만을 비교하여 적절한 위치에 정렬하는 방식

 

📍최악의 상황이 뭔가요? 그럴만한 케이스를 생각해본 적 있나요?

 

📍최악의 정도가 심한 알고리즘 중에 평균 성능이 좋은 케이스도 있다. 이런 경우 무엇을 선택할 것인가

 

📍추가적인 여러 기법들 : 평활 분석법, 분할상환분석 

- 평활 분석법

 

- 분할상환분석 

알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법

다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려

 

📍시간 복잡도를 계산해 개선해본 경험이 있느냐 

 

📍시간 복잡도 계산