cs 메모장

2024-06-19 컬렉션/ 해시테이블 , 바이너리서치트리 비교/ 컴파일러와 인터프리터/ 스택과 스택의 공유/ 최소 스패닝 트리/ 메모이제이션 알고리즘 / 선형구조 가산성과 동차성/ 병렬프로그래밍/ 배열안 중복제거/ Enum

nakgopsae 2024. 6. 19. 19:38

컬렉션에 대해서 설명해주세요.

여러개의 데이터를 하나의 구조안에 저장하는 데이터 구조를 말합니다 

데이터를 그룹화 하고 관리하면 접근하는 다양한 방법을 제공합니다 

list/set/map등이 있고 각 클래스는 고유한 특징과 목적을 가지고있으며 

데이터의 중복여부 , 순서 유지여부 , 키- 값 쌍으로 매핑등을 다르게 처리합니다


- 순서가 있는 목록인 List형

- 순서가 중요하지 않은 목록인 Set형

- 먼저 들어온 것이 먼저 나가는 Queue형

- KEY-VALUE의 형태로 저장되는 Map형

등이 있습니다

검색 자료구조로서 해쉬 테이블과 바이너리 서치 트리를 비교해주세요

해쉬 테이블은 데이터를 키와 해쉬값을 이용해 배열의 인덱스에 저장하고
이 인덱스를 통해 빠르게 데이터를 접근할 수 있습니다

해쉬 테이블은 평균적으로 상수 시간 복잡도로 검색이 가능하지만
해쉬 충돌이 발생할 경우 처리 속도가 느려질 수 있습니다

바이너리 서치 트리는 이진 탐색 트리로 각 노드가 최대 두 개의 자식 노드를 가지며왼쪽 자식 노드의 값은 부모 노드보다 작고
오른쪽 자식 노드의 값은 부모 노드보다 큰 특성을 가집니다
이를 이용해 정렬된 데이터를 빠르게 검색할 수 있으며 최악의 경우 로그 시간 복잡도를 가질 수 있습니다
그러나 삽입과 삭제 시 트리의 균형을 유지하기 위해 추가적인 알고리즘이 필요할 수 있습니다

컴파일러와 인터프리터를 비교해서 설명해주세요

컴파일러는
소스 코드를 전체적으로 한 번에 기계어 코드로 변환한 후 실행합니다
 프로그램의 문법 오류를 미리 검사하고 최적화하여 실행 속도가 빠릅니다
하지만 코드가 변경되면 다시 컴파일을 해야합니다

인터프리터는
소스 코드를 한 줄씩 읽어가며 바로 실행합니다. 
이 방식은 코드 실행 속도가 느릴 수 있지만 코드 수정 후 즉시 실행할 수 있어 디버깅에 유리합니다

스택에서 다른 스택으로의 자원을 서로 공유할 수 있나요

각 스택은 독립적으로 동작하도록 설계되어야 하며
스택 간의 데이터 공유는 예기치 않은 동작이나 상태 불일치를 초래할 수 있습니다.
하지만, 프로그래밍 언어의 메모리 모델이나 특정 상황에서는 스택 간의 자원 공유가 가능할 수 있으며
이 경우에는 적절한 동기화가 필요합니다

 

최소 스패닝 트리란 무엇인가요

그래프에서 모든 노드를 연결하는 최소 가중치의 부분 그래프입니다
그래프의 모든 노드를 최소 비용으로 연결하는 간선들의 집합입니다
크루스칼 알고리즘(Kruskal's algorithm)이나 프림 알고리즘(Prim's algorithm)과 같은 알고리즘을 사용하여
최소 스패닝 트리를 찾을 수 있습니다
//모든정점을 사이크없이 이을수있으면 최소스패닝트리입니다

 

메모이제이션을 적용할 수 있는 알고리즘에 대해서 설명하여 보세요

메모이제이션(Memoization)은 컴퓨터 프로그램이 동일한 계산을 반복하지 않도록
이전에 계산한 결과를 저장해두고 필요할 때 재사용하는 최적화 기법입니다

이를 통해 시간 복잡도를 크게 줄일 수 있습니다

메모이제이션은 주로 재귀적 알고리즘에 적용되어 중복되는 계산을 방지합니다

예를 들어, 피보나치 수열을 계산하는 알고리즘에서 이전의 값을 저장해두고
필요할 때마다 이를 참조하여 계산 시간을 줄일 수 있습니다

 

 

선형구조의 형태의 자료형에서 가산성과 동차성에 대해서 설명해보세요

가산성(Associativity)은 연산의 순서에 관계없이 결과가 동일한 성질을 의미합니다

//주어진 선형 구조가 두 개 이상의 요소를 합칠 때, 그 결과가 개별 요소의 결과의 합과 동일하다는 것을 의미합니다

동차성(Commutativity)은 두 피연산자의 순서와 관계없이 결과가 동일한 성질을 의미합니다

//동차성은 주어진 선형 구조가 임의의 스칼라 배수에 대해 일정하게 반응하는 특성을 의미합니다

 

병렬 프로그래밍에 대해 설명해보세요

병렬 프로그래밍은 하나의 작업을 여러 개의 작은 작업으로 분할하고, 이를 동시에 처리하는 프로그래밍 기법입니다
이를 통해 작업 수행 시간을 단축하고 전체 시스템의 성능을 향상시킬 수 있습니다

장점

성능 향상: 여러 작업을 동시에 수행하여 작업 완료 시간을 단축할 수 있습니다

자원 활용 극대화: 멀티코어 프로세서와 같은 하드웨어 자원을 효율적으로 사용할 수 있습니다

확장성: 병렬 프로그래밍은 큰 문제를 작은 부분으로 나누어 해결할 수 있어, 
클러스터나 분산 컴퓨팅 환경에서 유리합니다

단점

복잡성 증가: 병렬 프로그램은 설계, 구현, 디버깅이 어렵습니다

동기화 문제: 데이터 일관성을 유지하기 위한 동기화 작업이 필요하며,
잘못된 동기화는 데드락이나 레이스 컨디션(race condition)과 같은 문제를 일으킬 수 있습니다

오버헤드: 스레드나 프로세스 간의 통신과 동기화에 따른 오버헤드가 발생할 수 있습니다

 

배열 안 중복제거를 위한 방법이 뭐가 있을까요

정렬 후 인접 요소 비교: 배열을 정렬한 후, 인접한 요소를 비교하여 중복되는 요소를 제거하는 방법입니다.
이 방법은 정렬 알고리즘의 시간 복잡도에 따라 성능이 달라집니다.

해시 테이블 활용: 해시 테이블을 사용하여 각 요소의 존재 여부를 빠르게 확인할 수 있습니다.
이를 통해 중복된 요소를 제거할 수 있습니다.

Set 자료구조 사용: 집합(Set) 자료구조는 중복을 허용하지 않는 특성을 가지고 있어,
배열의 중복 요소를 제거하는 데 유용합니다.

배열 복사 및 인덱스 관리: 새로운 배열을 만들어 기존 배열의 요소를 중복 없이 복사하는 방법입니다.
이때 인덱스를 관리하여 중복된 요소를 건너뛰도록 합니다.

정렬 후 인접 요소 비교 (투 포인터): 정렬된 배열에서 두 개의 포인터를 사용하여 중복된 요소를 찾아내고 제거하는 방법입니다

 

Enum 사용해보셨나요? Enum 이란 무엇인가요

열거형은 관련된 상수들의 집합을 정의하는 타입입니다

의미 있는 이름을 가진 상수를 정의하여 코드의 가독성을 높이고, 오류를 줄이는 데 도움을 줍니다

값의 유효성을 컴파일 타임에 검사할 수 있으며, 코드의 의도를 명확하게 표현할 수 있습니다