CS

소프트웨어 공학 및 알고리즘 Q&A

Bubbles 2023. 9. 27. 01:44

소프트웨어 공학 및 알고리즘 관련 예상 Q&A 

  • 소프트웨어공학 질문 (디자인 패턴, 애자일 방법론, 폭포수 모델 등 )
  • 알고리즘 관련 이론 질문 

#1 ) 디자인 패턴은 무엇이고, 어떤 종류가 있나요? 

디자인 패턴이란 소프트웨어 설계에서 공통으로 발생하는 문제에 대해 자주 쓰이는 설계 방법들을 정리한 패턴을 의미합니다. 목적에 따라 생성 패턴, 구조 패턴, 행위 패턴으로 나뉩니다. 

  • 생성 : 객체 인스턴스 생성에 관여하는 패턴
    • EX : Builder, Singleton, Prototype, Factory Method, Abstract Method
  • 구조 : 더 큰 구조 형성 목적으로 클래스 / 객체 조합 다루는 패턴
    • EX : Adapter, Decorator, Bridge, Facade, Proxy .. 
  • 행위 : 클래스 || 객체의 상호작용, 역할 분담등을 다루는 패턴
    • EX : Observer, State, Template Method .. 

 

# 2 ) Extreme Programming(XP) 프로세스에 대해 설명해주세요. 

  • User story 중 이번 release에 포함시킬 user story 선정
    • User Story?
    • 사용자가 사용하는 모습을 시나리오처럼 기록 
    • 기능 하나하나를 대강 카드에 써놓음 
  • task 단위로 쪼갬 (개발자 업무 단위)
  • task 담당자 지정하고 이번 분기에서 수행할 작업 계호기 세움
  • Develop / Integrate / Test 과정 수행
    • 팀 코드에 병합되려면 먼저 해당 코드가 테스트 코드를 통과해야 하고, 팀 코드와 병합한 후에도 테스트를 통과해야 한다. 
  • 소프트웨어 Release
  • 소비자의 평가 (evaluate)

 

#3 ) TDD 란 무엇인가요? 

Test-Driven-Development의 약자로, 실제 코드를 작성하기 전 테스트 코드를 먼저 작성한 후, 테스트를 통과할 수 있는 코드를 작성해나가는 방식입니다. 먼저 테스트 코드를 작성한 후, 실제 테스트를 통과하도록 코드를 작성합니다. 그 후 리팩토링 과정을 거쳐 클린 코드로 다듬는 과정을 수행하는 것이 큰 흐름입니다. 

 

 

#4 ) Scrum Sprint cycle에 대해 설명해주세요. 

  • Product Backlog 라는, 만들려는 프로젝트의 특징, 구현해야할 기능 등 팀이 해야하는 일들의 총 집합체로부터 Sprint Backlog를 추출합니다. (해당 Sprint 동안 개발할 것을 추림)  
    • 여기까진 XP와 동일, XP의 UserStory가 Product BackLog, task가 Sprint backlog
  • 개발수행
    • Daily Scrum : 매일 개발자들이 모두 모여 상황을 공유하는 과정 
      • 주로 어제 한 것, 오늘 할 것, 문제 여부를 이야기 
      • 길게 늘어지지 않게 주로 서서 진행한다! 
      • 모든 팀원들이 참여하여 진행상황을 공유 
  • 제품 검토
  • 팀워크 및 프로세스 검토 : Sprint 회고 단계

 

 

#5 ) Scrum 방법론의 장점과 단점이 무엇인가요? 

장점

  • 프로덕트가 관리하고 이해하기 쉬운 단위로 쪼개져서 개발 편의성 증가
  • 팀원 모두가 상황을 다 공유할 수 있으므로 팀 커뮤니케이션 향상

단점

  • cycle 단위의 개발이 일어나므로 해당 사이클 당 작업량이 작을 수밖에 없다. 
  • 해당 cycle 안에 개발이 끝날지 안 끝날지 정확한 예측이 어려움 

 

# 6 ) 폭포수 모델에 대해 설명해주세요. 

  • 소프트웨어 생명주기 모델(소프트웨어 프로세스 모델) 중 전통적인 모델(가장 오래됨)
  • 각 단계를 확실히 마무리 지은 후 다음 단계로 넘어간다. 
  • 단계별 정의와 산출물이 명확하다. (각 단계가 끝나면 document가 나오고, 승인을 받음) 
  • 요구사항 변경이 어렵다.
    • 고객의 요구가 변경되거나 비 격식적 소통이 가능한 관계라면(ex : 이거 바꿔줘 이런게 쉽게 말할 수 있는) 적합하지 않음
    • 명확히 고객 - 개발사 간 계약 단위로 정의가 내려지는 요구사항이 명확한 시스템, 변경이 어려운 임베디드 시스템, 대규모 개발 팀 등에 적합
  • 과정
    • 요구사항 분석 및 정의
    • 시스템 및 소프트웨어 디자인 
      • 전반적인 시스템 구성, 각 요소간 관계 등을 정리 
    • 구현 & 유닛 테스트 수행 : 각자 구현하고 자기가 만든 unit들을 대상으로 unit 테스트 수행
    • 통합 후 전체 시스템 테스트 수행 
    • 유지보수 

 

 

# 7 ) 그래프 표현하는 방식들에 대해 설명해보세요

 

에지리스트

  • 구현이 쉬우나, 특정 노드 관련 에지 탐색이 어려움
  • 노드 중심 알고리즘에는 사용하지 않음
  • 벨만-포드(한 노드에서 다른 노드까지의 최단 거리, 음의 가중치 있을 경우 사용)
  • 크루스칼 (그래프 내 모든 정점들을 사이클 없이 최소 비용으로 연결 == 최소신장 트리 찾는데 사용)

인접행렬 

  • 노드 개수 * 노드 개수 사이즈의 배열에 연결정보 저장
  • 빠르게 연결 여부, 가중치 여부 확인 가능
  • 노드 개수에 비해 에지 개수가 적으면 효율성이 떨어짐
  • 노드 개수가 너무 많으면 메모리초과 날 수 있음. 3만개 정도까지 노드개수에 적합 

인접리스트

  • 구현 방식이 복잡하지만 공간효율, 에지 탐색시간 짧아서 자주 사용된다.

 

#8 ) 최소신장트리의 정의와 구하는 단계에 대해 설명해주세요.

최소 신장 트리

  • 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리
  • 사이클 포함하지 않아야 하며, N개의 노드가 있다면 에지의 개수는 항상 N-1개이다.
  • 에지를 기준으로 하기 때문에 위에서 언급한 에지 리스트로 그래프를 표현하고, 사이클 판별을 위해 유니온 파인드 사용 

과정

  • 에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬
  • 가중치 낮은 에지부터 연결 시도
  • 사이클 형성 유무 확인 후(find 연산으로 대표 노드 같다면 사이클 O), 사이클 형성되지 않았다면 union 연산으로 두 노드 연결 
  • 연결된 에지 개수가 N-1개 되었을 때 완료

 

# 9 ) 병합 정렬과 퀵 정렬 비교? (시간복잡도, 공간복잡도) 

병합 정렬 

  • 가장 작은 그룹으로 나눈 후, 2개씩 그룹을 합쳐가며 오름차순 정렬 
  • 투포인터 개념 활용하여 왼쪽, 오른쪽 그룹 병합
  • O(nlogn)의 시간복잡도를 일정하게 가진다. 

 

 

퀵 정렬 

  • 기준값을 설정, 해당 값보다 작은 데이터와 큰 데이터로 분류하는 작업을 반복해서 정렬
  • 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것 
  • 기준값이 어떻게 선정되었느냐에 따라 O(nlogn) ~ O(n^2)의 시간복잡도를 가진다. 

 

 

 

 

#10 ) 위상 정렬 알고리즘에 대해 설명해주세요. 

  • 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
  • 시간복잡도 : O(V + E) 
    • V : 노드 수
    • E : 에지 수
  • 항상 유일한 값으로 정렬되지 않는다. 
  • 과정 
    • 그래프를 인접리스트로 저장한다. 이 과정에서 각 노드 별 진입차수를 진입차수 배열에 저장해둔다. 
    • 진입 차수가 0인 노드를 선택하고, 선택한 노드를 정렬 배열에 저장
      • 진입차수 : 자기 자신으로 들어오는 에지 수
    • 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 뺀다. 
    • 이 과정을 모든 노드가 정렬배열에 들어갈때까지 반복.