CS 스터디 01-7 전산기초: 디자인 패턴과 알고리즘

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main

GitHub - JaeYeopHan/Interview_Question_for_Beginner: :boy: Technical-Interview guidelines written for those who started studying

 

디자인 패턴 사용 이유

개발의 효율성과 유지보수성, 운용성이 높아지며 프로그램의 최적화에 도움이 됩니다.

디자인 패턴 유형

디자인 패턴의 유형은 목적과 범위에 따라 나눠질 수 있습니다.

목적

• 생성(Creational): 객체의 생성 방식을 결정하는 패턴
• 구조(Structural): 클래스나 객체를 조합해 더 큰 구조를 만드는 패턴
• 행위(Behavioral): 객체나 클래스 사이의 알고리즘이나 책임 분배에 관련된 패턴

범위

• 클래스: 클래스 간 관련성(상속 관계를 다루는 패턴)
• 객체: 객체 간 관련성을 다루는 패턴

디자인 패턴 종류

생성 패턴

생성 패턴은 객체의 생성과 관련된 디자인 패턴으로 객체의 생성과 조합을 캡슐화해 특정 객체가 생성되거나 변경되어도 프로그램 구조에 영향을 크게 받지 않도록 유연성을 제공한다.

• 빌더 패턴(Builder): 복잡한 인스턴스를 조립하여 만드는 구조로 복합 객체를 생성할 때 객체를 생성하는 방법(과정)과 객체를 구현(표현)하는 방법을 분리함으로써 동일한 생성 절차에서 다양한 표현 결과를 만들 수 있는 디자인 패턴
• 원형 패턴(Prototype): 생성할 객체의 종류를 명시하는 데 원형이 되는 예시물을 사용하고 새로운 객체를 이 원형들을 복사함으로써 필요한 부분만 수정하여 사용하는 디자인 패턴
• 싱글톤 패턴(Singleton): 전역 변수를 사용하지 않고 객체를 하나만 생성하도록 하며, 생성된 객체를 어디에서든지 참조할 수 있도록 하는 디자인 패턴
• 추상팩토리 패턴(Abstract Factory): 구체적인 클래스를 지정하지 않고 관련성이 있거나 독립적인 객체들을 생성하기 위한 인터페이스를 제공하는 디자인 패턴
• 팩토리 메서드 패턴(Factory Method): 상위 클래스에서 객체를 생성하는 인터페이스를 정의하고, 하위 클래스에서 인스턴스를 생성하도록 하는 디자인 패턴

구조 패턴

구조 패턴은 클래스나 객체를 조합해 더 큰 구조를 만드는 패턴이다. 서로 다른 인터페이스를 지닌 2개의 객체를 묶어 단일 인터페이스를 제공하거나 서로 다른 객체들을 묶어 새로운 기능을 제공하는 패턴이다.

• 적응자 패턴(Adapter): 클래스의 인터페이스를 사용자가 기대하는 다른 인터페이스로 변환하는 패턴으로 호환성이 없는 인터페이스 때문에 함께 동작할 수 없는 클래스들이 함께 작동하도록 해주는 디자인 패턴
• 브리지 패턴(Bridge): 기능의 클래스 계층과 구현의 클래스 계층을 연결하고, 구현부에서 추상 계층을 분리하여 추상화된 부분과 실제 구현 부분을 독립적으로 확장할 수 있는 디자인 패턴
• 데코레이터 패턴(Decorator): 기존에 구현되어 있는 클래스에 필요한 기능을 추가해 나가는 설계 패턴으로 기능 확장이 필요할 때 객체 간의 결합을 통해 기능을 동적으로 유연하게 확장할 수 있게 해주어 상속의 대안으로 사용되는 디자인 패턴
• 프록시 패턴(Proxy): 어떤 다른 객체로 접근하는 것을 통제하기 위해 그 객체의 매니저 또는 자리 채움자를 제공하는 디자인 패턴
• 퍼사드 패턴(Facade): 복잡한 시스템에 대하여 단순한 통합된 인터페이스를 제공함으로써 사용자의 시스템 간 또는 여타 시스템과의 결합도를 낮추어 시스템 구조에 대한 파악을 쉽게 하는 디자인 패턴

행위 패턴

행위 패턴은 객체나 클래스 사이의 알고리즘이나 책임 분배에 관련된 패턴이다. 한 객체가 혼자 수행할 수 없는 작업을 여러개의 객체로 어떻게 분배하는지, 또 그러면서 객체 사이의 결합도를 최소화 하는 것에 중점을 두는 방식이다.

• 상태 패턴(State): 객체의 내부 상태가 변경될 때 행위 내용이 변경되는 패턴으로, 객체는 자신의 클래스가 변경되는 것처럼 보이게 된다.
• 옵저버 패턴(Observer): 객체들 사이에 1 : N 의존관계를 정의하여 어떤 객체의 상태가 변할 때, 의존관계에 있는 모든 객체들에 연락이 가고 내용이 자동적으로 갱신될 수 있게 만드는 디자인 패턴
• 템플릿 메서드 패턴(Template Method): 상위 클래스에는 추상메서드를 통해 기능의 골격을 제공하고, 하위 클래스의 메서드에서 세부 처리를 구체화하는 방식으로 코드 양을 줄이고 유지보수를 용이하게 만드는 디자인 패턴
• 비지터 패턴(Visitor): 각 클래스 데이터 구조로부터 처리 기능을 분리하여 별도의 클래스를 만들어 놓고 해당 클래스의 메서드가 각 클래스를 돌아다니며 특정 작업을 수행하도록 만드는 패턴으로, 객체의 구조는 변경하지 않으면서 기능만 따로 추가하거나 확장할 때 사용하는 디자인 패턴
• 미디에이터 패턴(Mediator): 한 집합에 속해있는 객체들의 상호 작용을 캡슐화하는 객체를 정의하는 패턴입니다. 중재자는 객체들이 직접 서로 참조하지 않도록 함으로써 객체들간의 느슨한 연결을 촉진시키며 객체들의 상호작용을 독립적으로 다양화 시킬 수 있도록 합니다.
• 이터레이터 패턴(Iterator): 컬렉션 구현 방법을 노출시키지 않으면서도 그 집합체 안에 들어있는 모든 항목에 접근할 방법을 제공하는 디자인 패턴
• 스트레이트지 패턴(Strategy): 동일 계열의 알고리즘을 정의하고, 각각 캡슐화하여 이들을 상호작용 가능하도록 만드는 것이다. 알고리즘을 사용하는 사용자로부터 독립적으로 알고리즘이 변경될 수 있도록 하는 디자인 패턴

💡 Algorithm (알고리즘) Link

• 손코딩 및 코딩 테스트 대비 => 대부분의 내용이 코드이기 때문에 별도의 Java Algorithm Training Repository에 저장합니다.
• 코딩 테스트를 위한 Tip
• 문제 해결을 위한 전략적 접근
• Sorting Algorithm
• Prime Number Algorithm

---

1. 디자인 패턴을 사용하는 이유는 무엇인가요?

답변:
디자인 패턴을 사용하면 개발의 효율성, 유지보수성, 운용성이 향상됩니다. 이는 개발 과정에서 발생하는 문제들을 표준화된 방식으로 해결함으로써 코드의 재사용성과 일관성을 높이기 때문입니다. 또한, 디자인 패턴을 통해 프로그램을 최적화하고 구조화함으로써 유지보수와 협업이 수월해집니다.

---

2. 디자인 패턴의 유형은 어떻게 나뉘나요?

답변:
디자인 패턴은 목적과 범위에 따라 나뉩니다. 목적에 따라 객체의 생성 방식을 결정하는 생성 패턴(Creational), 클래스나 객체를 조합해 구조를 만드는 구조 패턴(Structural), 객체나 클래스 간의 알고리즘과 책임 분배에 관련된 행위 패턴(Behavioral)으로 구분됩니다. 범위에 따라 클래스 패턴은 클래스 간의 상속 관계를 다루고, 객체 패턴은 객체 간의 관련성을 다룹니다.

---

3. 생성 패턴이란 무엇인가요?

답변:
생성 패턴(Creational Pattern)은 객체 생성의 과정을 캡슐화하여 객체가 생성되거나 변경되어도 프로그램 구조에 영향을 최소화할 수 있도록 돕는 패턴입니다. 이를 통해 객체 생성 방식의 유연성을 제공합니다.

---

4. 빌더 패턴(Builder Pattern)이란 무엇인가요?

답변:
빌더 패턴은 복잡한 객체를 생성하는 방법과 표현하는 방법을 분리하여 동일한 생성 절차에서 다양한 표현 결과를 얻을 수 있도록 하는 패턴입니다. 객체 생성의 과정을 세분화하여 단계별로 객체를 조립할 수 있어 유연한 구조를 제공합니다.

---

5. 원형 패턴(Prototype Pattern)이란 무엇인가요?

답변:
원형 패턴은 생성할 객체의 원형이 되는 예시물을 기반으로 복사하여 새로운 객체를 생성하는 패턴입니다. 이를 통해 객체 생성 비용을 줄이고, 복사된 객체를 필요에 맞게 수정하여 사용합니다.

---

6. 싱글톤 패턴(Singleton Pattern)이란 무엇인가요?

답변:
싱글톤 패턴은 특정 클래스의 인스턴스를 오직 하나만 생성하여 전역적으로 공유하는 패턴입니다. 이를 통해 자원의 낭비를 막고, 하나의 객체를 필요할 때마다 재사용할 수 있습니다. 예를 들어, 애플리케이션에서 하나의 데이터베이스 연결을 여러 군데서 사용해야 할 때 유용합니다.

---

7. 추상 팩토리 패턴(Abstract Factory Pattern)이란 무엇인가요?

답변:
추상 팩토리 패턴은 구체적인 클래스에 의존하지 않고 관련 객체들을 생성하는 인터페이스를 제공하는 패턴입니다. 서로 연관되거나 독립적인 객체들을 그룹으로 생성할 때 사용됩니다. 다양한 객체들을 일관성 있게 생성해야 할 때 유용합니다.

---

8. 팩토리 메서드 패턴(Factory Method Pattern)이란 무엇인가요?

답변:
팩토리 메서드 패턴은 상위 클래스에서 객체 생성 인터페이스를 정의하고, 하위 클래스에서 구체적인 객체 생성 방식을 구현하는 패턴입니다. 이를 통해 객체 생성 과정을 하위 클래스로 위임하여 코드의 유연성과 확장성을 높입니다.

---

9. 구조 패턴이란 무엇인가요?

답변:
구조 패턴(Structural Pattern)은 클래스나 객체를 조합해 더 큰 구조를 만드는 패턴입니다. 이를 통해 객체 간의 관계를 효율적으로 설정하고, 복잡한 시스템을 간단하게 구성할 수 있습니다.

---

10. 적응자 패턴(Adapter Pattern)이란 무엇인가요?

답변:
적응자 패턴은 클래스의 인터페이스를 사용자가 기대하는 다른 인터페이스로 변환하여 호환되지 않는 클래스들이 함께 동작할 수 있도록 만드는 패턴입니다. 예를 들어, 서로 다른 전압의 전자기기를 어댑터를 사용해 연결하는 것과 비슷합니다.

---

11. 브리지 패턴(Bridge Pattern)이란 무엇인가요?

답변:
브리지 패턴은 추상화된 부분과 구현된 부분을 분리하여 독립적으로 확장할 수 있도록 하는 패턴입니다. 이를 통해 클래스 계층 구조를 더욱 유연하게 확장할 수 있습니다.

---

12. 데코레이터 패턴(Decorator Pattern)이란 무엇인가요?

답변:
데코레이터 패턴은 기존 클래스에 기능을 추가할 때 상속 대신 객체 간 결합을 사용하여 유연하게 기능을 확장하는 패턴입니다. 기존 클래스의 코드를 수정하지 않고도 기능을 덧붙일 수 있어 확장성이 뛰어납니다.

---

13. 프록시 패턴(Proxy Pattern)이란 무엇인가요?

답변:
프록시 패턴은 다른 객체에 대한 접근을 제어하기 위해 대리자 역할을 하는 객체를 제공하는 패턴입니다. 이를 통해 접근 권한을 제어하거나, 원본 객체에 대한 접근을 지연시킬 수 있습니다.

---

14. 퍼사드 패턴(Facade Pattern)이란 무엇인가요?

답변:
퍼사드 패턴은 복잡한 시스템에 대해 간단한 인터페이스를 제공하여 시스템 간의 결합도를 낮추고, 사용자가 시스템을 쉽게 사용할 수 있게 하는 패턴입니다. 예를 들어, 하나의 퍼사드 클래스가 복잡한 서브시스템을 관리하고 사용자는 단순한 인터페이스로 시스템에 접근할 수 있습니다.

---

15. 행위 패턴이란 무엇인가요?

답변:
행위 패턴(Behavioral Pattern)은 객체나 클래스 간의 상호작용과 책임 분배에 관련된 패턴입니다. 주로 객체들 사이에서 복잡한 작업을 분배하면서도 결합도를 낮추는 데 중점을 둡니다.

---

16. 상태 패턴(State Pattern)이란 무엇인가요?

답변:
상태 패턴은 객체의 내부 상태에 따라 객체의 행동을 변경하는 패턴입니다. 객체는 상태 변화에 따라 다른 클래스로 변하는 것처럼 보이게 됩니다. 이를 통해 복잡한 상태 전이를 쉽게 관리할 수 있습니다.

---

17. 옵저버 패턴(Observer Pattern)이란 무엇인가요?

답변:
옵저버 패턴은 객체들 사이에 1:N 의존관계를 정의하여, 한 객체의 상태가 변할 때 관련된 다른 객체들에게 자동으로 알리고 갱신하는 패턴입니다. 이벤트 시스템에서 주로 사용되며, 대표적인 예로 구독 시스템이 있습니다.

---

18. 템플릿 메서드 패턴(Template Method Pattern)이란 무엇인가요?

답변:
템플릿 메서드 패턴은 상위 클래스에서 작업의 골격을 정의하고, 하위 클래스에서 구체적인 세부 처리를 구현하도록 하는 패턴입니다. 이 패턴은 코드 중복을 줄이고, 코드의 재사용성을 높여 유지보수를 쉽게 만듭니다.

---

19. 비지터 패턴(Visitor Pattern)이란 무엇인가요?

답변:
비지터 패턴은 데이터 구조에서 처리 기능을 분리하여 새로운 기능을 쉽게 추가할 수 있도록 돕는 패턴입니다. 객체의 구조는 변경하지 않고 기능을 추가하거나 확장할 때 유용합니다.

---

20. 미디에이터 패턴(Mediator Pattern)이란 무엇인가요?

답변:
미디에이터 패턴은 객체들 간의 상호작용을 중재하는 객체를 정의하여 객체들이 직접 참조하지 않도록 하는 패턴입니다. 이를 통해 객체 간의 결합도를 낮추고 상호작용을 독립적으로 관리할 수 있습니다.

---

21. 이터레이터 패턴(Iterator Pattern)이란 무엇인가요?

답변:
이터레이터 패턴은 컬렉션 내의 요소들을 순차적으로 접근할 수 있도록 하는 패턴입니다. 이를 통해 컬렉션의 내부 구조를 노출하지 않고도 각 요소에 접근할 수 있습니다.

---

22. 스트레이트지 패턴(Strategy Pattern)이란 무엇인가요?

답변:
스트레이트지 패턴은 동일한 작업을 수행하는 여러 알고리즘을 정의하고, 실행 시점에 필요에 따라 선택할 수 있도록 하는 패턴입니다. 이를 통해 동일 계열의 알고리즘을 정의하고, 각각 캡슐화하여 이들을 상호작용 가능하도록 만들 수 있습니다.

---

---

알고리즘

1. 문제 해결을 위한 전략적 접근

질문: 문제를 해결할 때 어떤 전략적 접근 방식을 취하시나요?

답변: 문제를 해결할 때 저는 상향식과 하향식 접근법을 번갈아 사용합니다. 상향식 접근법은 문제를 세부적으로 분석하여 작은 단위부터 해결책을 도출하는 방법입니다. 반면, 하향식 접근법은 큰 그림을 먼저 그리고, 그에 맞는 알고리즘이나 데이터 구조를 선택하여 문제를 해결하는 방식입니다. 또한, 문제의 성격에 따라 Divide and Conquer나 동적 계획법(Dynamic Programming), 탐욕 알고리즘(Greedy Algorithm), 재귀(Recursion) 등의 알고리즘 기법을 사용합니다. 다양한 관점에서 문제를 바라보면 최적의 해결책을 찾기 쉽습니다.

---

2. Sorting Algorithm

질문: 대표적인 정렬 알고리즘을 설명해 주세요.

답변: 정렬 알고리즘에는 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 등이 있습니다.

• 버블 정렬: 인접한 두 개의 요소를 비교해 교환하면서 정렬하는 방식으로, 시간 복잡도는 O(n²)입니다. 데이터가 거의 정렬되어 있는 경우에 효율적입니다.
• 선택 정렬: 배열에서 최소값을 찾아 차례대로 교환하는 방식으로, 시간 복잡도는 O(n²)입니다.
• 삽입 정렬: 각 요소를 이미 정렬된 배열에 삽입하는 방식으로, 시간 복잡도는 O(n²)이지만, 데이터가 거의 정렬된 경우 효율적입니다.
• 퀵 정렬: 분할 정복 방식을 사용하여 피벗을 기준으로 왼쪽과 오른쪽을 나누어 정렬하는 방식으로, 평균 시간 복잡도는 O(n log n)이지만 최악의 경우 O(n²)입니다.
• 병합 정렬: 배열을 반으로 나누고 각각을 정렬한 후 병합하는 방식으로, 안정적인 O(n log n)의 시간 복잡도를 가집니다.

---

3. Prime Number Algorithm

질문: 소수를 찾는 알고리즘은 어떤 것이 있나요?

답변: 대표적인 소수를 찾는 알고리즘으로는 에라토스테네스의 체가 있습니다. 이 알고리즘은 소수를 효율적으로 구할 수 있는 방법으로, 소수의 배수를 제거해 나가는 방식입니다. 구체적으로는 2부터 시작하여 그 수의 배수를 제거하고, 그다음 수로 이동해 또다시 배수를 제거합니다. 이를 통해 빠르게 소수를 찾을 수 있으며, 시간 복잡도는 O(n log log n)입니다. 소수의 성질을 이용해 범위를 줄이는 방법이나 동적 계획법으로 효율적으로 소수를 구할 수도 있습니다.

---

4. Divide and Conquer

질문: Divide and Conquer(분할 정복) 알고리즘이란 무엇인가요?

답변: Divide and Conquer는 문제를 작은 단위로 나누어 각각을 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 방식입니다. 대표적인 예로는 퀵 정렬과 병합 정렬이 있습니다. 문제를 분할하는 과정에서 더 이상 나눌 수 없을 때까지 나누고, 각각을 해결한 후 병합하는 방식으로 효율적으로 문제를 해결할 수 있습니다. 특히 대규모 데이터 처리에 유리하며, 시간 복잡도는 보통 O(n log n)입니다.

---

5. Dynamic Programming / Memoization

질문: 동적 계획법(Dynamic Programming)과 메모이제이션(Memoization)에 대해 설명해주세요.

답변: 동적 계획법(Dynamic Programming, DP)은 문제를 부분 문제로 나누어, 같은 부분 문제가 반복되는 경우, 그 결과를 저장하여 중복 계산을 피하는 알고리즘입니다. 이때 결과를 저장하는 기법을 메모이제이션(Memoization)이라고 합니다. 예를 들어, 피보나치 수열을 구할 때 DP를 사용하면 재귀 호출의 중복을 피하고, 연산 시간을 O(n)으로 줄일 수 있습니다. DP는 문제를 하위 문제로 나누어 해결하고, 그 결과를 저장하여 효율성을 극대화합니다.

---

6. Greedy Algorithm

질문: 탐욕 알고리즘(Greedy Algorithm)이란 무엇인가요?

답변: 탐욕 알고리즘은 매 순간 최적의 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다. 이 방식은 항상 최선의 선택을 하므로 결과적으로 전체 문제에 대한 최적의 해를 보장하지는 않지만, 특정 조건에서는 효율적으로 해결할 수 있습니다. 대표적인 예로 최소 신장 트리를 구하는 크루스칼 알고리즘이나 프림 알고리즘이 있습니다. 이러한 알고리즘들은 항상 현재 상황에서 가장 적은 비용을 선택하여 최종 해답을 찾아내는 방식입니다.

---

7. Recursion

질문: 재귀(Recursion)에 대해 설명해 주세요.

답변: 재귀(Recursion)는 함수가 자기 자신을 호출하여 반복적인 문제를 해결하는 방법입니다. 일반적으로 반복문으로 해결할 수 있는 문제도 재귀로 해결할 수 있지만, 재귀는 문제를 더 간결하게 표현할 수 있습니다. 그러나 재귀는 스택 메모리를 사용하므로 호출 횟수가 많아지면 스택 오버플로우가 발생할 수 있습니다. 재귀는 특히 분할 정복이나 동적 계획법에서 많이 사용되며, 팩토리얼 계산이나 피보나치 수열 등에서 자주 활용됩니다.

---

8. Algorithms Associated with a Specific Data Structure

질문: 특정 데이터 구조와 관련된 알고리즘이 있나요?

답변: 특정 데이터 구조는 그에 맞는 알고리즘을 갖고 있습니다. 예를 들어:

• 배열(Array): 정렬 알고리즘인 퀵 정렬, 병합 정렬이 배열과 잘 맞습니다.
• 스택(Stack) / 큐(Queue): 깊이 우선 탐색(DFS)은 스택을 사용하고, 너비 우선 탐색(BFS)는 큐를 사용합니다.
• 해시맵(HashMap): 해시 테이블을 기반으로 효율적인 탐색 및 삽입을 제공합니다. O(1)의 시간 복잡도를 기대할 수 있습니다.
• 트리(Tree): 이진 탐색 트리(BST), AVL 트리, 그리고 힙 구조를 사용한 우선순위 큐 등이 있습니다.
• 그래프(Graph): 최단 경로 탐색에서는 다익스트라 알고리즘과 플로이드-워셜 알고리즘 등이 사용됩니다.

---

9. Array vs Linked List

질문: 배열(Array)과 연결 리스트(Linked List)의 차이점은 무엇인가요?

답변: 배열은 메모리의 연속된 공간에 데이터를 저장하며, 인덱스를 통해 접근할 수 있어 접근 속도가 빠릅니다(O(1)). 그러나 배열은 크기가 고정되어 있으며, 삽입 및 삭제 시 전체 데이터를 이동해야 하기 때문에 삽입/삭제의 시간 복잡도는 O(n)입니다. 반면, 연결 리스트는 요소들이 포인터를 통해 연결된 구조로, 동적 크기 조절이 가능하며, 삽입/삭제가 빠릅니다(O(1)), 하지만 인덱스가 없어서 특정 요소에 접근하려면 순차 탐색이 필요해 접근 속도는 느립니다(O(n)).

---

10. Graph Algorithm

질문: 그래프 탐색 알고리즘에 대해 설명해주세요.

답변: 그래프 탐색 알고리즘에는 DFS(Depth First Search)와 BFS(Breadth First Search)가 있습니다.

• DFS는 스택을 사용하여 한 경로를 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 이전 경로로 돌아와 다른 경로를 탐색하는 방식입니다. 주로 재귀적으로 구현되며, 그래프의 모든 경로를 탐색할 때 유용합니다.
• BFS는 큐를 사용하여 한 정점에서 인접한 모든 정점을 탐색한 후, 다음 레벨로 이동해 탐색하는 방식입니다. 주로 최단 경로 탐색에서 사용되며, 특정 목표를 찾을 때 효율적입니다.

---