기술면접 1. 자료구조, 객체지향

Ethereal·2021년 12월 27일
객체지향기술면접자료구조
0

기술면접

목록 보기
1/5

1. 자료구조

🍎Array List vs Linked List

탐색 또는 정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결 리스트를 사용하는 것이 유리하다

특징

A : 논리적 저장 순서와 물리적 저장 순서(메모리)가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다.
L : A의 경우 인덱스 삭제, 삽입의 시간 복잡도를 개선하기 위해 나온 자료구조. LL자체는 삽입 삭제, 탐색 모두 O(n)이지만 LL를 바탕으로 Tree 자료구조들을 구성한다.

원소 찾기

A : O(1) / 인덱스만 안다면 random access 가능!
L : O(n) / 첫번째 혹은 마지막 원소부터 차례로 탐색해야해서 최대 O(n)시간 소요.

원소 삭제 및 삽입

A : O(n) / 가운데 원소를 삭제 혹은 그 위치에 삽입을 진행할 경우, 연속된 성질을 보장해야하기 원소들을 다 shift해줘야함.
L : O(1) / 각각의 원소는 이전, 그리고 다음 원소의 위치만을 가지고 있음으로, 이것만 수정해주면 삭제, 삽입은 O(1) 하지만, 탐색때문에

https://www.nextree.co.kr/p6506/

🍎Stack vs Queue

특징

S : LIFO
Q : FIFO

📌 스택의 활용 예시

스택의 특징인 후입선출(LIFO)을 활용하여 여러 분야에서 활용 가능하다.

웹 브라우저 방문기록 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다.
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다.
후위 표기법 계산
수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

📌 큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
은행 업무
콜센터 고객 대기시간
프로세스 관리
너비 우선 탐색(BFS, Breadth-First Search) 구현
캐시(Cache) 구현

출처: https://devuna.tistory.com/22 [튜나 개발일기]

1.1 Tree

트리를 구성하고 있는 구성요소들(용어)
Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

🍎Binary Tree (이진 트리)

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 진다.
또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 한다.
공집합도 이진트리에 포함.
재귀적인 정의

정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree)

정이진트리

완전이진트리는 다음 그림과 같습니다. 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리입니다.

균형이진트리는 다음 그림과 같습니다. 모든 잎새노드의 깊이 차이가 많아야 1인 트리를 가리킵니다. 균형이진트리는 예측 가능한 깊이(predictable depth)를 가지며, 노드가 n개인 균형이진트리의 깊이는 logn을 내림한 값이 됩니다.

https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

🍎BST (Binary Search Tree)

효율적인 탐색을 위한 자료구조

  • 어떻게 찾을까만 중요한게 아니라, 어떻게 저장할까가 중요하다.

탐색 시간:

O(log(N)) 좀더 정확히는 O(h) / h는 이진트리의 높이.

이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문이다. 이럴 경우 성능에 영향을 미치게 되며,

탐색의 Worst Case 가 되고 시간 복잡도는 O(n)이 된다.

이런 편향 현상을 해결하기위해 자가 균형 기법이 들어간 트리가 있다.

🍎B+tree 🛑

🍎Red Black Tree (자가 균형 이진 트리)

RBT(Red-Black Tree)는 BST 를 기반으로하는 트리 형식의 자료구조이다. 결론부터 말하자면 Red-Black Tree 에 데이터를 저장하게되면 Search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth 를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다. 동일한 노드의 개수일 때, depth 가 최소가 되는 경우는 tree 가 complete binary tree 인 경우이다.

🍎hash Table 🛑

2. 객체지향 (OOP)

객체지향 전반에 대해 읽어보기 좋은 글:
https://onlyfor-me-blog.tistory.com/367?category=808873

주요 특성 4가지는
1. 캡슐화
2. 추상화
3. 다형성
4. 상속

객체지향의 얕은 이해:
https://asfirstalways.tistory.com/177

JS에서는 다른 OOP 언어와 다르게 객체지향을 구현하여야한다!
https://parksb.github.io/article/1.html

객체 지향적 설계 원칙

  • SRP(Single Responsibility Principle) : 단일 책임 원칙
    클래스는 단 하나의 책임을 가져야 하며 클래스를 변경하는 이유는 단 하나의 이유이어야 한다.
  • OCP(Open-Closed Principle) : 개방-폐쇄 원칙
    확장에는 열려 있어야 하고 변경에는 닫혀 있어야 한다.
  • LSP(Liskov Substitution Principle) : 리스코프 치환 원칙
    상위 타입의 객체를 하위 타입의 객체로 치환해도 상위 타입을 사용하는 프로그램은 정상적으로 동작해야 한다.
  • ISP(Interface Segregation Principle) : 인터페이스 분리 원칙
    인터페이스는 그 인터페이스를 사용하는 클라이언트를 기준으로 분리해야 한다.
  • DIP(Dependency Inversion Principle) : 의존 역전 원칙
    고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다.

🍎다향성이란?

다형성(polymorphism)이란 하나의 객체가 여러 가지 타입을 가질 수 있는 것을 의미합니다.

다형성이란 프로그램 언어 각 요소들(상수, 변수, 식, 객체, 메소드 등)이 다양한 자료형(type)에 속하는 것이 허가되는 성질을 가리킨다. - 위키피디아 중 -

자바스크립트에는 실제로 다형성이 있나요?
https://ichi.pro/ko/jaba-seukeulibteue-siljelo-dahyeongseong-i-issseubnikka-162104335497880
하지만 Js에서는 항상 일어나기 때문에 JS에서 코드의 일부에 다형성을 특별히 적용 할 방법이 없습니다. JS의 너무 많은 데이터 유형이 기본적으로 객체이고 모든 JS 객체가 전역 객체에서 상속되기 때문에 언제든지 객체 리터럴을 정의하고 원하는 메서드를 지정할 수 있습니다. 이는 우연히 동일한 이름을 가질 수 있습니다. 완전히 다른 물체에서 찾을 것으로 기대하는 방법으로.

따라서 좀더 큰 범위로 정의하자면 아래와 같다.

다형성(polymorphism)은 특정 기능을 선언(설계)부분과 구현(동작)부분으로 분리한 후 구현부분을 다양한 방법으로 만들어 선택해서 사용할 수 있게 하는 기능힙니다.

출처: https://webclub.tistory.com/406 [Web Club]

다형성(Polymorphism)은 OOP(Object Oriented Programming)에서 서로 다른 객체들 사이에서도 같은 함수에 대해서 각각이 다르게 동작하는 것입니다.

출처: https://skagh.tistory.com/4 [재수강은없다]

http://www.tcpschool.com/java/java_polymorphism_concept

참조 변수의 다형성

자바에서는 다형성을 위해 부모 클래스 타입의 참조 변수로 자식 클래스 타입의 인스턴스를 참조할 수 있도록 하고 있습니다.

이때 참조 변수가 사용할 수 있는 멤버의 개수가 실제 인스턴스의 멤버 개수보다 같거나 적어야 참조할 수 있습니다.

다음 예제는 참조 변수의 다형성을 보여주는 예제입니다.

예제
class Parent { ... }
class Child extends Parent { ... }

...

Parent pa = new Parent(); // 허용
Child ch = new Child(); // 허용
Parent pc = new Child(); // 허용
Child cp = new Parent(); // 오류 발생.

🍎다형성 2. Overriding vs Overloading

오버로딩과 오버라이딩은 다형성을 지원하는 방법 중 하나.

오버로딩(Overloading) : 같은 이름의 메서드 여러개를 가지면서 매개변수의 유형과 개수가 다르도록 하는 기술

  • 간단히 : 한 객체안에 같은 이름을 가지는 메서드를 여러개 만들어서, 각각의 메서드가 다른 매개변수에 따라 다르게 행동하도록 일일이 미리 만들어놓는 기술..

오버라이딩(Overriding) : 상위 클래스가 가지고 있는 메서드를 하위 클래스가 재정의해서 사용

  • 간단히 : 말그대로 상위 클래스에 있는 메서드를 하위 클래스가 상속받아서 (땡겨와서) 현재 클래스에 맞는 방식으로 입맛대로 고쳐서 사용

출처: https://private.tistory.com/25 [공부해서 남 주자]

오버 로딩 예시

class OverloadingTest{
    //이름이 cat인 메서드
    void cat(){
        System.out.println("매개변수 없음");
    }
    
    //매개변수 int형이 2개인 cat 메서드
    void cat(int a, int b){
        System.out.println("매개변수 :"+a+", "+b);
    }
    
    //매개변수 String형이 한 개인 cat 메서드
    void cat(String c){
        System.out.println("매개변수 : "+ c);
    }
    
}
 
public class OverTest {
 
    public static void main(String[] args) {
        
        //OverloadingTest 객체 생성
        OverloadingTest ot = new OverloadingTest();
        
        //매개변수가 없는 cat() 호출
        ot.cat();
        
        //매개변수가 int형 두개인 cat() 호출
        ot.cat(20, 80);
        
        //매개변수가 String 한개인 cat() 호출
        ot.cat("오버로딩 예제입니다.");
        
    }
 
}

오버라이딩 예시

class Woman{ //부모클래스
    public String name;
    public int age;
    
    //info 메서드
    public void info(){
        System.out.println("여자의 이름은 "+name+", 나이는 "+age+"살입니다.");
    }
    
}
 
class Job extends Woman{ //Woman클래스(부모클래스)를 상속받음 : 
 
    String job;
    
    public void info() {//부모(Woman)클래스에 있는 info()메서드를 재정의
        super.info();
        System.out.println("여자의 직업은 "+job+"입니다.");
    }
}
 
public class OverTest {
 
    public static void main(String[] args) {
        
        //Job 객체 생성
        Job job = new Job();
        
        //변수 설정
        job.name = "유리";
        job.age = 30;
        job.job = "프로그래머";
        
        //호출
        job.info();
        
    }
 
}

🍎캡슐화

  • 객체의 속성(data fields)과 행위(메서드, methods)를 하나로 묶고
  • 실제 구현 내용 일부를 외부에 감추어 은닉한다.

캡슐회는 만일의 상황(타인이 외부에서 조작)을 대비해서 외부에서 특정 속성이나 메서드를 시용자가 사용할 수 없도록 숨겨놓은 것입니다.

  1. 객체의 필드(속성), 메소드를 하나로 묶고, 실제 구현 내용을 외부에 감추는 것을 말한다.

  2. 외부 객체는 객체 내부의 구조를 얻지 못하며 객체가 노출해서 제공하는 필드와 메소드만 이용할 수 있다.

  3. 필드와 메소드를 캡슐화하여 보호하는 이유는 외부의 잘못된 사용으로 인해 객체가 손상되지 않도록 하는데 있다.

  4. 자바 언어는 캡슐화된 멤버를 노출시킬 것인지 숨길 것인지를 결정하기 위해 접근 제한자(Access Modifier)를 사용한다.

출처: https://webclub.tistory.com/156 [Web Club]

일반 OOP에서 지원하는 캡슐화

일반 OOP 언어에서는 접근지정자를 제공

public
protected
private

자바스크립트에서 캡슐화

기본 public
private,protected 에 _ 붙여 선언 (하지만 문제점은 있다)

JS에서의 Information Hiding

자바스크립트에는 은닉된 프로퍼티라는 개념이 없다. 자바에는 private, protected, public과 같은 접근제어자가 있어서 외부에서 인스턴스 멤버에 접근하는 것을 통제할 수 있지만, 자바스크립트는 클래스의 모든 프로퍼티가 public이다.

종종 프로퍼티 이름 앞에 언더스코어를 붙이는 방식(this._name)으로 private한 변수임을 표현하는 경우도 있는데, 실제로 프로퍼티가 private하게 동작하는 것은 아니기 때문에 오해를 불러일으킨다는 의견이 있다. Airbnb JavaScript 스타일 가이드를 참고.

프로퍼티 대신 변수를 사용하면 정보를 은닉하는 효과를 낼 수 있다.

https://parksb.github.io/article/1.html

// Animal.js
class Animal {
    constructor(name) {
        let name = name;

        this.getName = () => { 
            return name;
        };

        this.setName = (newName) => {
            name = newName;
        }
    }
}

export default Animal;

🍎상속

상속(Inheritance)이란

현실 세계에서 상속이란 부모가 자식에게 물려주는 행위, 부모가 자식을 선택해서 물려주는 행위이지만 객체지향 프로그래밍에서의 상속은 현실 세계와 반대로 자식이 부모를 선택해서 물려받는 것을 말합니다.

  • 자식(하위,파생) 클래스가 부모(상위) 클래스의 멤버를 물려받는 것
  • 자식이 부모를 선택해서 물려 받는 것
  • 상속 대상 : 부모의 필드와 메소드

상속의 효과

  1. 부모 클래스를 재사용해서 자식 클래스를 빨리 개발할 수 있다.
  2. 반복된 코드의 중복을 줄여준다.
  3. 유지 보수의 편리성을 제공해 준다. (부모 클래스를 한 번만 수정함으로써 자식클래스를 수정할 필요가 없음)
  4. 객체의 다형성을 구현할 수 있다.

출처: https://webclub.tistory.com/156 [Web Club]

🍎추상화

추상화어떤 실체로부터 공통적인 부분이나 관심 있는 특성들만 한곳에 모은것을 의미
객체지향에서의 추상화는 어떤 하위클래스들에 존재하는 공통적인 메소드를 인터페이스로 정의하는 것

  • 공통의 속성이나 기능을 묶어 이름을 붙이는 것
  • 객체 지향적 관점에서 클래스를 정의하는 것을 바로 추상화라고 정의 내릴 수 있겠다.
  • 좀 더 살펴보면 물고기, 사자, 토끼, 뱀이 있을 때 우리는 이것들을 각각의 객체라 하며 이 객체들을 하나로 묶으려 할 때,
    만약 동물 또는 생물이라는 어떤 추상적인 객체로 크게 정의한다고 하자. 이때 동물 또는 생물이라고 묶는 것을 추상화라고 한다.

출처: https://88240.tistory.com/228 [shaking blog]

컴퓨터 과학에서 추상화(abstraction)는 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것을 말한다.

https://ko.wikipedia.org/wiki/%EC%B6%94%EC%83%81%ED%99%94_(%EC%BB%B4%ED%93%A8%ED%84%B0_%EA%B3%BC%ED%95%99)

profile
Ethereal
꿈에다가 우리들의 돛을 달고 앞으로 다가올 그 날을 위해 밤을 지나자
다음 포스트

기술면접 2. Javascript

0개의 댓글