CS 기술면접 (26.10.08)

About this offer

기술면접 질문 정리 자료구조 3. 해시테이블은 어떻게 동작하나요? 해시 충돌은 어떻게 해결하나요? 답변 해시테이블은 Key-Value 형태로 데이터를 저장하고, 해시 함수를 통해 데이터의 저장 위치를 결정하는 자료구조 임. Key를 해시 함수에 입력하면 해시값이 생성되고, 이를 배열의 인덱스로 변환하여 해당 위치에 데이터를 저장하거나 조회함. 일반적으로 삽입, 삭제, 조회의 평균 시간 복잡도가 O(1) 이므로 빠른 데이터 접근이 가능함. 다만 서로 다른 Key가 동일한 저장 위치에 매핑되는 해시 충돌(Hash Collision) 이 발생할 수 있음. 대표적인 해결 방법으로는 체이닝(Chaining) 과 개방 주소법(Open Addressing) 이 있음. 체이닝 : 동일한 인덱스에 여러 데이터를 연결 리스트 등의 자료구조로 저장 개방 주소법 : 충돌이 발생하면 다른 빈 공간을 탐색하여 데이터를 저장 핵심 정리 구분 내용 저장 방식 Key-Value 핵심 원리 해시 함수를 통해 저장 위치 계산 평균 조회 O(1) 평균 삽입/삭제 O(1) 최악 시간 복잡도 O(n) 주요 문제 해시 충돌 충돌 해결 체이닝, 개방 주소법 대표 활용 HashMap, HashSet, 캐시 등 해시 충돌 예시 해시 함수가 key % 5 인 경우 Key = 7 → 7 % 5 = 2 Key = 12 → 12 % 5 = 2 서로 다른 Key가 동일한 인덱스 2에 저장되려 함 → 해시 충돌 발생 체이닝 방식을 사용하면 다음과 같이 데이터를 저장할 수 있음. Index 0 → null 1 → null 2 → [7] → [12] → null 3 → null 4 → null 추가로 알아둘 내용 Q. 해시테이블의 시간 복잡도가 최악의 경우 O(n)이 되는 이유? 여러 Key가 동일한 인덱스에 집중되면 해당 위치에 저장된 데이터를 순차적으로 탐색해야 할 수 있기 때문. Q. Java의 HashMap은 어떻게 충돌을 해결하나요? Java의 HashMap은 기본적으로 체이닝 방식을 사용하며, 하나의 버킷에 데이터가 많이 쌓이면 일정 조건에서 연결 리스트를 균형 트리 구조로 변환하여 탐색 성능을 개선함. 또한 데이터가 많아지면 로드 팩터(Load Factor) 를 기준으로 저장 공간을 확장하여 충돌 가능성을 줄임. 4. 트리와 그래프의 차이는 무엇인가요? 답변 트리와 그래프는 모두 노드(Vertex)와 간선(Edge)을 이용하여 데이터 간 관계를 표현하는 비선형 자료구조 임. 그래프는 노드 간의 관계를 자유롭게 표현할 수 있는 일반적인 구조로, 방향성이 존재할 수 있고 사이클이 발생할 수도 있음. 반면 트리는 사이클이 없는 연결 그래프 로, 노드가 n 개라면 간선은 반드시 n-1 개임. 특히 루트가 있는 트리에서는 부모와 자식의 계층 관계를 표현할 수 있으며, 루트를 제외한 모든 노드는 하나의 부모를 가짐. 따라서 계층적 관계를 표현할 때는 트리 , 복잡한 연결 관계를 표현할 때는 그래프 가 적합함. 핵심 정리 구분 트리(Tree) 그래프(Graph) 구조 계층적 관계 표현에 적합 일반적인 연결 관계 사이클 없음 존재 가능 연결성 모든 노드가 연결 연결되지 않을 수 있음 간선 수 n-1 구조에 따라 다름 경로 두 노드 사이 단순 경로 하나 여러 경로 존재 가능 대표 활용 파일 시스템, 조직도, BST 지도, SNS, 네트워크 대표적인 예시 트리 구조 A / \ B C / \ D E → 계층적 관계 → 사이클 없음 그래프 구조 A ─── B │ / │ │ / │ C ─── D → 복잡한 연결 관계 → 사이클 존재 가능 추가로 알아둘 내용 트리는 그래프의 특수한 형태 임. 트리는 모든 노드가 연결되어 있으면서 사이클이 없는 무방향 그래프라고 볼 수 있음. 그래프와 트리 모두 DFS와 BFS를 이용하여 탐색할 수 있음. 다만 일반적인 그래프에서는 사이클이 존재할 수 있으므로 같은 노드를 반복 방문하지 않도록 방문 여부를 관리하는 과정 이 필요함. 알고리즘 3. 재귀와 반복문의 차이, 그리고 재귀를 쓸 때 주의할 점은? 답변 재귀는 함수가 자기 자신을 다시 호출하여 문제를 해결하는 방식 이고, 반복문은 for , while 등을 이용하여 동일한 작업을 반복하는 방식임. 재귀는 큰 문제를 작은 문제로 나누어 해결하는 분할 정복, 트리 탐색, DFS 등에 적합하며 코드가 직관적일 수 있음. 반면 반복문은 별도의 함수 호출 없이 반복을 수행하므로 일반적으로 함수 호출에 따른 추가 비용이 적음. 재귀를 사용할 때는 반드시 종료 조건(Base Case) 이 필요하며, 종료 조건이 없거나 재귀 호출이 지나치게 깊어지면 Stack Overflow 가 발생할 수 있음. 따라서 단순한 반복 작업에는 반복문이 유리한 경우가 많고, 계층적 구조나 분할 정복 문제에서는 재귀가 코드의 가독성을 높일 수 있음. 핵심 정리 구분 재귀(Recursion) 반복문(Iteration) 동작 방식 자기 자신 호출 반복 제어문 사용 종료 조건 Base Case 반복 조건 메모리 호출 스택 사용 일반적으로 추가 메모리 적음 장점 복잡한 구조를 직관적으로 표현 호출 비용 및 메모리 관리에 유리 단점 Stack Overflow 가능 복잡한 탐색에서 코드가 길어질 수 있음 대표 활용 DFS, 트리 탐색, 분할 정복 배열 순회, 단순 반복 Java 예시 재귀 방식 int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); } 반복문 방식 int factorial(int n) { int result = 1; for (int i = 2; i <= n; i++) { result *= i; } return result; } 두 방식 모두 시간 복잡도는 O(n) 이지만, 재귀 방식은 호출 스택으로 인해 O(n) 의 추가 공간이 필요하고 반복문 방식은 O(1) 의 추가 공간으로 처리 가능함. 추가로 알아둘 내용 재귀를 사용할 때 주의할 세 가지 종료 조건 : 언제 재귀 호출을 멈출 것인지 문제 축소 : 호출할 때마다 종료 조건에 가까워지는지 호출 깊이 : 호출 스택이 지나치게 깊어지지 않는지 Java는 꼬리 재귀 최적화를 보장하지 않으므로 재귀 깊이가 매우 커질 수 있다면 반복문으로 변경하는 것이 안전할 수 있음. 4. 탐욕 알고리즘(Greedy)과 동적 계획법(DP)의 차이는 무엇인가요? 답변 탐욕 알고리즘은 매 순간 가장 좋아 보이는 선택을 하여 문제를 해결하는 방식 임. 이전에 내린 선택을 일반적으로 다시 검토하지 않으며, 현재의 최적 선택이 전체 최적해로 이어지는 문제에서 사용함. 반면 동적 계획법(DP)은 큰 문제를 작은 부분 문제로 나누고, 부분 문제의 결과를 저장하여 중복 계산을 줄이는 방식 임. DP는 최적 부분 구조와 중복되는 부분 문제가 존재하는 상황에서 효과적으로 활용할 수 있음. 따라서 Greedy는 지역 최적 선택이 전체 최적해를 보장하는 경우 , DP는 여러 선택의 결과를 비교하고 부분 문제의 결과를 재사용해야 하는 경우 에 적합함. 핵심 정리 구분 Greedy DP 핵심 원리 현재 가장 좋은 선택 부분 문제의 결과 저장 및 재사용 선택 방식 지역 최적 선택 여러 상태와 선택 고려 최적해 보장 탐욕 선택 속성이 성립할 때 올바른 상태·점화식 설계 시 메모리 상대적으로 적은 경우가 많음 상태 저장 공간 필요 대표 문제 활동 선택, 일부 거스름돈 문제 배낭 문제, 계단 오르기, 피보나치 대표적인 예시 동전이 1원, 3원, 4원 이고 총 6원 을 만들어야 하는 상황. Greedy 방식 현재 가장 큰 동전부터 선택 4원 + 1원 + 1원 → 총 3개 DP 방식 가능한 선택을 비교 4원 + 1원 + 1원 = 3개 3원 + 3원 = 2개 → 최소 2개 이처럼 탐욕 알고리즘은 문제의 조건에 따라 최적해를 보장하지 못할 수 있음. 추가로 알아둘 내용 Q. Greedy가 항상 최적해를 보장하지 않는 이유? 현재 시점에서 가장 유리한 선택이 이후의 선택에 영향을 주어 전체적으로는 더 나쁜 결과를 만들 수 있기 때문. Q. DP의 핵심 개념은? 최적 부분 구조(Optimal Substructure) : 전체 문제의 최적해를 부분 문제의 최적해로 구성 가능 중복 부분 문제(Overlapping Subproblems) : 동일한 부분 문제가 반복적으로 등장 메모이제이션(Memoization) : 재귀 방식에서 계산 결과를 저장 타뷸레이션(Tabulation) : 반복문을 통해 작은 문제부터 결과를 계산하고 저장 DP는 무조건 재귀를 사용하는 것이 아니라 반복문으로도 구현 가능함. 운영체제 3. 프로세스의 생명주기(상태 전이)를 설명해보세요. 답변 프로세스는 실행되는 동안 운영체제의 스케줄링과 자원 사용 상황에 따라 여러 상태를 거침. 대표적인 프로세스 상태는 생성(New), 준비(Ready), 실행(Running), 대기(Waiting), 종료(Terminated) 의 다섯 가지임. 프로세스가 생성되면 실행 준비 상태로 이동하고, CPU 스케줄러에 의해 CPU를 할당받으면 실행 상태가 됨. 실행 중 I/O 작업이나 특정 이벤트를 기다려야 하는 경우 대기 상태로 이동하며, 해당 작업이 완료되면 다시 준비 상태로 돌아감. 또한 실행 중인 프로세스는 할당된 CPU 시간이 끝나거나 우선순위가 높은 작업에 의해 선점되면 준비 상태로 이동할 수 있음. 마지막으로 작업을 완료하면 종료 상태가 됨. 핵심 정리 상태 의미 New 프로세스 생성 중 Ready CPU 할당을 기다리는 상태 Running CPU에서 명령어 실행 중 Waiting I/O 또는 특정 이벤트를 기다리는 상태 Terminated 실행이 종료된 상태 프로세스 상태 전이 CPU 할당 Ready ─────────────────> Running ↑ │ │ │ │ I/O 요청 / 이벤트 대기 │ ↓ └──────────────────── Waiting I/O 완료 / 이벤트 발생 New → Ready Running → Ready (CPU 선점 또는 할당 시간 종료) Running → Terminated (프로세스 실행 종료) 추가로 알아둘 내용 Q. Ready와 Waiting의 차이는 무엇인가요? Ready : CPU만 할당받으면 바로 실행할 수 있는 상태 Waiting : CPU를 할당받더라도 I/O나 이벤트가 완료되지 않으면 실행을 계속할 수 없는 상태 Q. CPU 스케줄링은 무엇인가요? 여러 프로세스 중 어떤 프로세스에 CPU를 할당할지 운영체제가 결정하는 과정임. 대표적인 스케줄링 알고리즘으로 FCFS, SJF, Round Robin 등이 있음. 4. 컨텍스트 스위칭이란 무엇이고, 비용이 발생하는 이유는? 답변 컨텍스트 스위칭(Context Switching)은 CPU가 현재 실행 중인 프로세스나 스레드의 실행 상태를 저장하고, 다른 프로세스나 스레드의 실행 상태를 복원하여 실행 대상을 전환하는 과정 임. 운영체제는 여러 작업을 동시에 처리하는 것처럼 보이게 하기 위해 CPU의 실행 대상을 빠르게 전환함. 이때 현재 작업의 프로그램 카운터(PC), 레지스터 등의 실행 상태를 저장하고 다음 작업의 상태를 복원해야 함. 이러한 과정에는 CPU 시간과 시스템 자원이 사용되므로 비용이 발생함. 또한 실행 대상이 변경되면 CPU 캐시나 TLB의 활용 효율이 낮아질 수 있어 추가적인 성능 저하가 발생할 수 있음. 따라서 컨텍스트 스위칭이 지나치게 빈번하면 실제 작업에 사용하는 CPU 시간이 줄어들어 전체 성능이 저하될 수 있음. 핵심 정리 구분 내용 의미 CPU 실행 대상 전환 발생 상황 CPU 선점, I/O 대기, 스레드 스케줄링 등 저장 정보 PC, 레지스터, 스택 포인터 등 직접적인 비용 상태 저장 및 복원 간접적인 비용 캐시 지역성 저하, TLB 관련 비용 등 성능 영향 전환이 과도하면 처리량 감소 가능 컨텍스트 스위칭 과정 Process A 실행 ↓ 인터럽트 또는 스케줄링 이벤트 발생 ↓ Process A의 실행 상태 저장 ↓ Process B의 실행 상태 복원 ↓ Process B 실행 추가로 알아둘 내용 Q. 프로세스 간 전환과 스레드 간 전환 중 일반적으로 어느 쪽의 비용이 더 큰가요? 일반적으로 서로 다른 주소 공간을 사용하는 프로세스 간 전환이 같은 프로세스 내부의 스레드 간 전환보다 비용이 클 수 있음. 프로세스 간 전환에서는 주소 공간 변경과 관련된 추가 작업이 발생할 수 있지만, 같은 프로세스의 스레드들은 주소 공간을 공유하기 때문. 다만 실제 비용은 운영체제와 CPU 구조, 캐시 상태 등에 따라 달라짐. Q. 컨텍스트 스위칭과 모드 스위칭은 같은 개념인가요? 서로 다른 개념임. 컨텍스트 스위칭 : CPU에서 실행할 프로세스나 스레드 변경 모드 스위칭 : 사용자 모드와 커널 모드 사이의 전환 시스템 콜로 커널 모드에 진입했다고 해서 반드시 컨텍스트 스위칭이 발생하는 것은 아님. 네트워크 3. HTTP와 HTTPS의 차이는 무엇인가요? 답변 HTTP는 클라이언트와 서버가 데이터를 주고받기 위한 애플리케이션 계층 프로토콜 임. HTTP 자체에는 통신 내용을 암호화하는 기능이 없으므로, 별도의 보안 계층 없이 통신하면 중간에서 데이터를 확인하거나 변조할 위험이 있음. 반면 HTTPS는 HTTP 통신에 TLS(Transport Layer Security)를 적용하여 데이터를 안전하게 전송하는 방식 임. TLS를 통해 통신 내용을 암호화하고, 데이터의 무결성을 보호하며, 인증서를 이용해 서버의 신원을 검증할 수 있음. 따라서 로그인 정보, 결제 정보, 개인정보 등 민감한 데이터를 전송할 때 HTTPS를 사용하는 것이 중요함. 핵심 정리 구분 HTTP HTTPS 의미 HyperText Transfer Protocol HTTP over TLS 암호화 기본 제공하지 않음 TLS를 통한 암호화 기본 포트 80 443 인증서 기본적으로 필요 없음 일반적으로 서버 인증서 사용 기밀성 기본적으로 보장하지 않음 보장 무결성 기본적으로 보장하지 않음 보호 대표 활용 내부 테스트 등 일반적인 웹 서비스 HTTPS 통신 과정 일반적인 HTTPS 연결에서는 다음 과정이 수행됨. 1. 클라이언트가 서버에 연결 요청 2. TLS 핸드셰이크 진행 3. 서버 인증서 전달 및 검증 4. 암호화에 사용할 세션 키 합의 5. 암호화된 HTTP 데이터 송수신 HTTP/1.1 및 HTTP/2에서는 일반적으로 TCP 연결 이후 TLS 핸드셰이크가 수행됨. HTTP/3은 UDP 기반 QUIC을 사용하며 TLS 1.3의 보안 기능이 QUIC에 통합되어 있음. 추가로 알아둘 내용 Q. HTTPS는 대칭키와 비대칭키 중 무엇을 사용하나요? 일반적인 최신 TLS 연결에서는 비대칭키 암호 기술을 이용한 인증 및 키 합의 와 대칭키 암호화를 이용한 실제 데이터 전송 을 함께 사용함. 비대칭키 암호 기술 : 서버 인증 및 안전한 키 합의에 활용 대칭키 암호화 : 합의된 세션 키로 실제 통신 데이터 암호화 대칭키 암호화는 대량의 데이터를 효율적으로 암호화할 수 있으므로 실제 데이터 전송에 사용됨. Q. HTTPS를 사용하면 모든 보안 문제가 해결되나요? 그렇지 않음. HTTPS는 주로 전송 구간의 보안을 제공하며, SQL Injection, XSS, 서버 내부 정보 유출 등의 애플리케이션 보안 문제까지 해결하지는 못함. 4. OSI 7계층을 간단히 설명해보세요. 답변 OSI 7계층은 네트워크 통신 과정을 일곱 개의 계층으로 나누어 각 계층의 역할을 설명하는 참조 모델 임. 각 계층은 서로 다른 역할을 담당하며, 계층별로 기능을 분리함으로써 네트워크 구조를 이해하고 문제를 분석하기 쉽게 함. 상위 계층은 사용자와 가까운 데이터 처리 및 서비스 기능을 담당하고, 하위 계층은 실제 데이터 전송과 관련된 기능을 담당함. 실제 인터넷에서는 OSI 모델보다 TCP/IP 모델 을 중심으로 프로토콜이 구현되지만, OSI 7계층은 네트워크 개념을 이해하는 데 널리 활용됨. 핵심 정리 계층 이름 주요 역할 대표 예시 7 응용(Application) 사용자 서비스 및 네트워크 기능 제공 HTTP, DNS, SMTP 6 표현(Presentation) 데이터 형식 변환, 인코딩, 암호화 등 문자 인코딩, 데이터 직렬화 5 세션(Session) 통신 세션 설정 및 관리 세션 관리 기능 4 전송(Transport) 종단 간 데이터 전송 TCP, UDP 3 네트워크(Network) IP 주소 기반 경로 선택 IP, Router 2 데이터 링크(Data Link) 같은 링크 내 프레임 전송 Ethernet, Switch 1 물리(Physical) 전기·광 신호 등을 통한 비트 전송 케이블, 물리 매체 데이터 전송 과정 클라이언트가 서버에 HTTP 요청을 보내는 경우를 단순화하면 다음과 같음. [클라이언트] 7. 응용 계층 HTTP 요청 생성 ↓ 6. 표현 계층 데이터 표현 및 변환 ↓ 5. 세션 계층 세션 관련 기능 ↓ 4. 전송 계층 TCP 세그먼트 ↓ 3. 네트워크 계층 IP 패킷 ↓ 2. 데이터 링크 Ethernet 프레임 ↓ 1. 물리 계층 비트 신호 전송 ↓ 네트워크 ↓ [서버] 하위 계층부터 상위 계층으로 처리 ↓ HTTP 요청 수신 실제 프로토콜에서는 OSI 계층의 기능이 명확히 일대일로 분리되지 않을 수 있음. 추가로 알아둘 내용 Q. TCP와 IP는 각각 몇 계층인가요? TCP : 4계층(전송 계층) IP : 3계층(네트워크 계층) HTTP : 7계층(응용 계층) Q. 캡슐화(Encapsulation)란 무엇인가요? 상위 계층에서 전달받은 데이터에 각 계층이 필요한 헤더 등의 정보를 추가하여 하위 계층으로 전달하는 과정임. HTTP Data ↓ TCP Header + Data ↓ IP Header + TCP Segment ↓ Ethernet Header + IP Packet + Trailer 수신 측에서는 반대로 헤더를 해석하고 제거하는 역캡슐화(Decapsulation) 가 이루어짐. 데이터베이스 3. 정규화란 무엇이고, 왜 하나요? 반정규화는 언제 필요한가요? 답변 정규화(Normalization)는 데이터베이스의 중복을 줄이고 데이터의 무결성을 유지하기 위해 테이블 구조를 체계적으로 분리하는 과정 임. 하나의 테이블에 여러 종류의 정보가 중복 저장되면 데이터 수정 시 일부 정보만 변경되어 불일치가 발생할 수 있음. 이러한 문제를 이상 현상(Anomaly) 이라고 하며, 대표적으로 삽입 이상, 수정 이상, 삭제 이상이 있음. 정규화는 이러한 이상 현상을 줄이고 데이터 간의 종속 관계를 명확하게 관리하는 데 목적이 있음. 반면 반정규화(Denormalization)는 조회 성능 개선 등의 목적을 위해 의도적으로 데이터 중복을 허용하거나 테이블을 통합하는 방식 임. 따라서 일반적으로 정규화를 통해 데이터 구조를 설계한 뒤, 실제 성능 문제가 확인되면 조회 패턴과 유지보수 비용을 고려하여 반정규화를 검토함. 핵심 정리 구분 정규화 반정규화 목적 데이터 중복 및 이상 현상 감소 조회 성능 개선 데이터 중복 줄이는 방향 의도적으로 허용 가능 테이블 구조 종속 관계에 따라 분리 테이블 통합 또는 중복 컬럼 추가 장점 무결성 및 유지보수성 향상 JOIN 감소 등 조회 최적화 가능 단점 조회 시 JOIN이 증가할 수 있음 데이터 불일치 위험 증가 적용 시점 데이터 모델 설계 성능 분석 후 필요 시 정규화 단계 정규형 핵심 내용 제1정규형(1NF) 컬럼의 값이 원자값이 되도록 구성 제2정규형(2NF) 1NF를 만족하고 기본키의 일부에만 종속되는 비주요 속성 제거 제3정규형(3NF) 2NF를 만족하고 비주요 속성의 이행적 종속 제거 실무에서는 일반적으로 제3정규형까지의 개념을 기본적으로 이해하는 것이 중요함. 대표적인 예시 정규화 이전 주문ID 회원ID 회원이름 상품ID 상품명 1 100 김철수 10 키보드 2 100 김철수 20 마우스 3 200 이영희 10 키보드 회원 이름과 상품명이 주문마다 반복 저장되고 있음. 회원 이름이 변경되면 해당 회원의 모든 주문 데이터를 수정해야 하며, 일부만 수정되면 데이터 불일치가 발생할 수 있음. 정규화 이후 회원 테이블 - 회원ID (PK) - 회원이름 상품 테이블 - 상품ID (PK) - 상품명 주문 테이블 - 주문ID (PK) - 회원ID (FK) - 상품ID (FK) 회원 정보와 상품 정보를 별도 테이블로 분리하여 중복을 줄임. 추가로 알아둘 내용 Q. 이상 현상(Anomaly)의 종류는 무엇인가요? 삽입 이상 : 불필요한 다른 정보가 없으면 원하는 데이터를 삽입하기