CS 스터디 - 그래프, NAT, 배열, 분산락

✅ 그래프 탐색 알고리즘

1) 그래프 탐색 알고리즘에 대해 설명해 주세요.

그래프 탐색 알고리즘은 정점과 간선으로 이루어진 그래프에서 원하는 노드나 경로를 찾기 위해 사용하는 방법입니다.
대표적으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.
DFS는 한 경로를 끝까지 탐색한 뒤 다른 경로로 넘어가는 방식이고,
BFS는 시작 노드에서 가까운 노드부터 차례로 탐색하는 방식입니다.

2) DFS와 BFS의 차이점, 언제 어떤 걸 쓰는지 설명해 주세요.

깊이 우선 탐색은 Stack이나 재귀 기반으로 구현하고 너비 우선 탐색은 Queue를 기반으로 구현되는데
DFS는 최적의 값을 찾는 곳에 주로 사용되고 BFS는 과정은 크게 중요하지 않고 최단 경로를 찾을 때 주로 사용됩니다.

3) DFS와 BFS의 시간복잡도와 공간복잡도는 어떻게 되나요?

DFS와 BFS 모두 모든 정점과 간선을 한 번씩 방문하기 때문에 시간복잡도는 O(V+E)입니다.
공간복잡도는 DFS는 재귀 스택 또는 명시적 스택 때문에 O(V),
BFS는 큐에 최대 V개의 노드가 들어갈 수 있어서 O(V)입니다.
BFS는 그래프의 폭이 넓을 때 큐가 매우 커져 메모리를 많이 사용할 수 있고, DFS는 재귀 깊이가 깊으면 스택 오버플로우 위험이 있을 수 있습니다.

4) 위의 문제를 풀 때, 어떤 알고리즘을 사용해야 할까요? 

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

이 문제는 그래프에서 1번 노드로부터 모든 노드까지의 최단 거리를 구하고, 그 중 가장 큰 거리값을 갖는 노드들이 몇 개인지를 묻는 문제입니다.

DFS와 BFS 모두를 통해서 이를 해결할 수 있지만 저는 BFS를 사용할 것 같습니다.

어디를 지나가는 지는 중요하지 않고 몇 개를 지나가서 해당 노드가 위치해있는지가 더 중요하기 때문입니다.
BFS는 큐를 사용해 레벨 단위로 탐색하며, 방문한 깊이를 기록할 수 있기 때문입니다. 

수.. 숙제까지! (엄청나)

---

✅ NAT

1) NAT(Network Address Translation)란 무엇이며, 백엔드 시스템에서 어떤 영향을 줄 수 있나요?

NAT는 사설 IP와 공인 IP 간의 변환을 통해, 내부 네트워크에 있는 장치들이 외부 인터넷과 통신할 수 있도록 해주는 기술입니다.

- 백엔드 서버가 NAT 뒤에 있을 경우, 외부에서 직접 접근이 불가능
- Webhook, 콜백 수신, 실시간 통신(WebRTC) 등의 기능에 제약 발생
- 서버에서 외부로 나가는 통신(Outbound)은 가능하지만, 반대는 제한됨

2) NAT 환경에서 외부에서 서버에 접근하려면 어떻게 해야 하나요?

포트 포워딩: 라우터에서 특정 포트를 내부 IP로 연결 Reverse Proxy: Nginx 등 외부에 노출된 서버가 내부 요청을 전달 VPN/터널링: 사설망에 안전하게 접근할 수 있는 경로 생성 클라우드라면: 공인 IP + Security Group + 라우팅 테이블 설정

3) 클라우드에서 NAT Gateway와 Internet Gateway의 차이를 설명해 보세요.

둘 다 외부 통신을 위해 사용되지만, 통신 방향성과 사용 위치가 다릅니다. NAT Gateway는 사설 서브넷의 인스턴스가 외부 인터넷에 나갈 수 있도록 해주는 장치이며, Internet Gateway는 공인 IP가 할당된 인스턴스에 외부에서 접근이 가능하도록 해주는 장치입니다.

 

몰라서 일단 출제자가 준 모범 답안을 가져왔는데 따로 더 공부한 후에 나만의 답변으로 수정해 보도록 하겠다!
https://www.maeil-mail.kr/question/164

매일메일 - 기술 면접 질문 구독 서비스

 

---

✅ 정적 배열, 동적 배열

1) 정적배열과 동적배열이 각자 무엇인지와 차이점이 무엇인지도 적어주세요.

정적 배열은 크기가 정해져있는 배열, 동적 배열은 크기가 가변적인 배열을 말합니다.
정적 배열은 기본 타입과 객체 모두 저장 가능하지만 동적 배열은 객체만 저장 가능하고,
정적 배열은 삽입/삭제가 어렵지만, 동적 배열은 쉽다는 차이가 있습니다.

2) 동적배열과 연결리스트의 차이점은 무엇인가요?

동적 배열은 연속적인 메모리 공간이지만, 연결 리스트는 다음 노드의 포인터를 가지는 불연속적 공간입니다.
따라서, 알고자하는 데이터의 위치를 모르는 경우 head부터 탐색을 시작해야하기 때문에 배열보다 조회에 오래 걸리고
다음 노드를 알아야 하기 때문에 메모리도 더 많이 사용한다는 차이가 있습니다.

3) 대용량 데이터를 처리할 때 ArrayList와 LinkedList 중 어떤 것을 선택하시겠습니까? 그 이유는?

조회가 빠른 ArrayList를 사용할 것입니다.
다만, 추가/삭제가 빈번하다면 LinkedList를 고려할 수 있을 것 같습니다.
제가 알기로 평균적인 crud사이트에서 read에 비율이 90% cud가 10%정도로 알고 있습니다.
그래서 평균적으로는 ArrayList가 유리하기 때문에 ArrayList를 사용할 것 같습니다.

 

4) Vector와 ArrayList를 각각 설명해 주세요

Vector는 자바 초기 버전부터 존재한 레거시 클래스입니다. 모든 메서드에 동기화(synchronized) 처리가 되어 있어, 멀티 스레드 환경에서 안전하게 사용할 수 있습니다.
ArrayList는 배열을 기반으로 한 컬렉션으로 배열은 제네릭을 사용할 수 없지만 arrayList는 가능하다는 장점이 있습니다. 여러 스레드에서 동시 접근이 가능하므로, 단일 스레드 환경에 적합합니다.

5) 멀티 스레드 환경에서 ArrayList를 사용하고 싶다면 어떻게 해야 될까요?

Collections.synchronizedList(), CopyOnWriteArrayList를 통해 동기화 기능이 적용된 ArrayList를 사용할 수 있습니다.

6) ArrayList에서 순차 검색보다 조건 검색이 많아지면 어떻게 처리하실 거예요?

정렬이 되어있는 배열이라면 이진 탐색을 사용할 것 같습니다. 이진 탐색은 O(log n)의 시간복잡도로 O(n)의 순차탐색보다
빠르기 때문입니다.
만약 정렬되지 않았거나 하지 못하는 상황이라면 HashMap을 고려할 것 같습니다.

---

✅ 분산락

1) 데드락이 무엇이고 발생 조건은 무엇인가요?

둘 이상의 프로세스가 다른 프로세스가 점유 중인 자원을 기다릴 때, 무한 대기에 빠지는 교착 상태를 말합니다.
상호 배제, 점유 대기, 비선점, 순환 대기인 경우 데드락이 발생할 수 있고
이를 예방하기 위해서는 4가지 중 하나라도 발생하지 않도록 해야 합니다.

2) 단일 서버가 아니라 여러 서버에서 동시에 자원에 접근하려 하면 어떤 문제가 생기나요?

서버 A에서 락을 걸어도 서버 B에서는 그 사실을 모르기 때문에 Race Condition으로 인해
중복 처리, 데이터 불일치 문제가 발생할 수 있습니다.
이를 해결하기 위해서는 여러 서버가 공유 데이터를 제어하기 위한 기술인 분산락을 사용해야 합니다.

3) 분산락을 구현할 때 Redis를 많이 사용하는데, 그 이유가 무엇인가요?

분산락 구현 방법에는 Zookeeper, MySQL, Redis가 있는데 그 중 Redis는
인메모리 DB이기 때문에 락 획득 및 해제가 빠르게 처리되고 다른 방법 들에 비해 설정 및 운영이 간단하며,
Pub/Sub이나 Lua 스크립트 같은 기능들도 사용이 가능하다는 장점이 있기 때문에 Redis를 많이 사용합니다.

4) 분산 환경에서의 데드락은 어떻게 방지 또는 회피하나요?

애플리케이션이 요청한 자원이 안전 상태를 유지하면서만 할당될 수 있도록 설계하고,
타임아웃을 통해 일정 시간 후 락이 자동 해제되도록 설정하거나
모든 서버가 동일한 순서로 자원을 요청하도록 자원 획득 순서를 설정해야합니다.