[CS기술면접] 자료구조 및 알고리즘

자료구조

• stack : 데이터를 쌓아 올리는 형태(LIFO: 후입선출)의 선형 자료구조로, 마지막에 저장한 데이터를 가장 먼저 꺼내는 구조입니다. 한쪽 끝(Top)에서만 삽입(push)과 삭제(pop)가 이루어지며, 주로 메서드 호출 처리, 뒤로 가기 기능 등에 사용
• queue : 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(FIFO, First-In-First-Out) 방식의 선형 자료구조. 줄 서기와 같이 데이터가 입력된 순서대로 처리되어야 하는 대기열(은행 업무, 프린터 인쇄 대기 등)이나, 서로 다른 스레드/프로세스 간 데이터 교환 시 주로 사용
  

알고리즘

• BFS (Breadth-First Search, 너비 우선 탐색)
  - 특징: 시작점에서 가까운 노드부터 방문하며, 가중치가 없는 그래프에서 최단 거리를 보장한다.
  - Java 구현: Queue<Integer> queue = new LinkedList<>(); 사용.
  - 적합한 문제: 미로 찾기 최단 거리, 네트워크의 연결 상태, 단계별 탐색.
• DFS (Depth-First Search, 깊이 우선 탐색)
  - 특징: 한 노드에서 시작하여 자식 노드를 방문하고, 그 자식의 자식을 끝까지 파고든 후 백트래킹한다.
  - Java 구현: 재귀 호출(스택 메모리 사용) 또는 Stack 사용.
  - 적합한 문제: 백트래킹(모든 경우의 수), 사이클 탐지, 그래프 연결 컴포넌트 찾기
• BFS vs DFS 주요 차이점
  - 방식: BFS는 레벨 단위(너비)로 탐색, DFS는 한 방향으로 끝까지(깊이) 탐색.
  - 자료구조: BFS는 Queue (FIFO), DFS는 Stack 또는 재귀 호출 사용.
  - 핵심 용도: 최단 경로(BFS) vs 모든 경우의 수/경로 존재 여부(DFS).