1. 동적 계획법(DP)에 대해 설명해주세요. 동적 계획법: 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법 DP를 적용하기 위해서는 2가지 조건을 만족해야 합니다. 첫째, 중복 문제 동일한 작은 문제들이 반복되어야, 부분 문제의 결과를 저장하여 재활용하여 전체의 답을 구할 수 있기 때문입니다. 둘째, 최적 부분 구조 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있어야 합니다. 구현 방법 1. Bottom-Up 작은 부분 문제부터 반복문을 통해 문제를 해결하고 값을 저장합니다.(메모이제이션) 2. Top-Down 큰 문제를 재귀 함수를 사용해 작은 부분 문제로 나누고, 중복 계산을 피하기 위해 메모이제이션을 활용합니다. 대표적으로 피보나치 문제, 배낭 문제가..
1. 스택과 큐의 차이점을 설명해주세요. 스택은 나중에 들어온 데이터가 가장 먼저 나가는 후입선출 방식의 선형 데이터 구조입니다. 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 선입선출 방식의 선형 데이터 구조입니다. 스택은 재귀 알고리즘 같이 호출이 끝난 뒤 돌아갈 주소를 반환하는 용도에서 주로 사용됩니다. 예를 들어 뒤로 가기와 문자열 뒤집기 등이 있습니다. 큐는 프린터의 출력 처리, BFS 알고리즘 등과 같이 먼저 들어오는 것을 먼저 실행하는 작업에 주로 사용됩니다. 2. Array와 LinkedList의 차이점을 설명해주세요. Array(배열)은 정적 자료구조로 선언한 크기 만큼의 연속된 메모리 주소를 할당 받습니다. 연속된 메모리 주소를 할당 받기 때문에 인덱스에 해당하는 데이터의 탐색이 용이..
1. 키의 종류 5가지와 각각 특징을 설명하세요. 우선, 데이터베이스에서 키란 조건에 맞는 튜플을 찾거나, 순서대로 정렬할 때 다른 튜플과 구별할 수 있는 기준입니다. 또한 키의 특징에 들어가기 전 유일성과 최소성 개념에 대해 알아봅시다. 유일성 : 하나의 키값으로 튜플을 유일하게 식별할 수 있는 성질 최소성 : 키를 구성하는 속성들 중 꼭 필요한 최소한의 속성들로만 키를 구성하는 성질 슈퍼키 : 유일성 O, 최소성 X. 키 값이 같은 튜플에 존재할 수 없음, 나이+이름이면 성립X 후보키: 유일성 O, 최소성 O. 기본키가 될 수 있는 후보이기 때문에 후보키라고 불린다. 예를 들면, 주민등록번호, 학번 등 기본키: 후보 키에서 선택된 키. NULL값이 들어갈 수 없으며, 기본키로 선택된 속성(Attrib..
