프로그래밍 면접 이렇게 준비한다 (9)[책리뷰 & Book review]

 

프로그래밍 면접 이렇게 준비한다 (9)

[책리뷰 & Book review]

 

 

DFS와 BFS 차이점과 장단점은 무엇인가?

DFS와 BFS의 차이점과 장단점

DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프를 탐색하는 두 가지 기본적인 알고리즘입니다.

DFS는 현재 노드의 자식 노드를 모두 방문하고 그 후에 형제 노드를 방문하는 방식으로 그래프를 탐색합니다. 즉, 가능한 한 깊이 들어가서 탐색을 진행합니다. DFS는 재귀적인 논리를 가지고 있으며, 이는 구현이 비교적 간단하다는 장점을 제공합니다. 그러나 모든 노드를 방문하는 데 필요한 시간이 오래 걸릴 수 있다는 단점도 있습니다.

반면에 BFS는 현재 노드의 모든 형제 노드를 먼저 방문하고 그 후에 자식 노드를 방문하는 방식으로 그래프를 탐색합니다. 즉, 가능한 한 넓게 탐색을 진행합니다. BFS는 큐를 사용하여 구현되며, 최단 경로를 찾는 데 유용하다는 장점이 있습니다. 그러나 메모리 사용량이 크다는 단점도 있습니다.

* **DFS(Depth-First Search)**

    * 깊이 우선 검색은 그래프 또는 트리를 검색하는 알고리즘 중 하나이다.
    * 한 노드에서 출발하여 그 노드의 모든 인접 노드를 방문한 후, 그중 하나의 인접 노드를 선택하여 다시 그 노드의 모든 인접 노드를 방문하는 방식으로 진행한다.
    * 장점: 특정 노드를 찾는 데 효율적이다.
    * 단점: 모든 노드를 방문하지 않을 수 있다.

* **BFS(Breadth-First Search)**

    * 너비 우선 검색은 그래프 또는 트리를 검색하는 알고리즘 중 하나이다.
    * 한 노드에서 출발하여 그 노드의 모든 인접 노드를 방문한 후, 그 중 하나의 인접 노드를 선택하여 다시 그 노드의 모든 인접 노드를 방문하는 방식으로 진행한다.
    * 장점: 모든 노드를 방문한다.
    * 단점: 특정 노드를 찾는 데 비효율적일 수 있다.

 

 

 

케빈 베이컨 게임은 무엇인가?

케빈 베이컨 게임이란?

케빈 베이컨 게임은 "6단계의 케빈 베이컨"이라는 이론에 기반한 게임입니다. 이 이론은 어떤 배우든지 케빈 베이컨을 포함한 영화를 통해 최대 6단계 이내로 연결될 수 있다는 가설입니다. 이 게임에서는 주어진 배우가 케빈 베이컨과 얼마나 '가까운' 관계에 있는지를 찾는 것이 목표입니다. 이를 찾기 위해 BFS를 적용할 수 있습니다.

케빈 베이컨 게임에 대한 BFS 알고리즘

BFS 알고리즘을 케빈 베이컨 게임에 적용하면 다음과 같습니다:

* 모든 영화 배우는 케빈 베이컨과 몇 단계로 연결되어 있다.
* 영화 배우영화배우 A와 영화배우 B가 같은 영화에 출연하면, 영화배우 A와 영화배우 B는 1단계로 연결되어 있다.
* 영화 배우 A와 영화배우 B가 1단계로 연결되어 있고, 영화배우 B와 영화배우 C가 1단계로 연결되어 있으면, 영화배우 A와 영화 배우 C는 2단계로 연결되어 있다.

예를 들어, 케빈 베이컨과 톰 행크스는 "아폴로 13"이라는 영화에 함께 출연했기 때문에 1단계로 연결되어 있다. 톰 행크스와 메릴 스트립은 "필라델피아"라는 영화에 함께 출연했기 때문에 1단계로 연결되어 있다. 따라서 케빈 베이컨과 메릴 스트립은 2단계로 연결되어 있다.

 

 

 

 

큐를 만들고 시작 노드로 초기화
큐가 비어 있지 않은 동안
첫 번째 노드를 큐에서 꺼낼
타깃 노드면 베이컨 수를 리턴
현재 노드에 인접한 각 노드에 대하여
그 노드를 방문한 적이 없으면 (베이컨 수가1)
베이컨 수를 현재 노드의 베이컨 수에 1을 더한 값으로 설정
그 인접 노드를 큐 맨 뒤에 추가
타깃을 찾지 못한 상태로 순환문이 끝났으므로 실패했다는 결과를 리턴

큐를 만들고 시작 노드로 초기화합니다.
큐가 비어 있지 않은 동안 다음을 반복합니다:
큐에서 첫 번째 노드를 꺼냅니다.
그것이 타깃 노드라면 현재의 베이컨 수를 리턴합니다.
현재 노드에 인접한 각 노드에 대해, 그 노드를 방문한 적이 없다면 (베이컨 수가 없다면), 베이컨 수를 현재 노드의 베이컨 수에 1을 더한 값으로 설정하고 그 인접 노드를 큐 맨 뒤에 추가합니다.
타깃을 찾지 못한 상태로 순환문이 끝나면 실패했다는 결과를 리턴합니다.
.

 

 

 

 

 

 

배열은 어떤 메모리 블록에 연속적으로 나열된 같은 유형의 변수 모음이다

 

배열은 같은 유형의 변수들이 연속적으로 나열된 자료구조입니다. 배열은 메모리에서 연속된 블록을 차지하며, 각 요소는 인덱스를 통해 접근할 수 있습니다. 배열은 동적인 자료구조가 아니라 고정된 크기를 가집니다. 즉, 배열이 생성된 후에는 그 크기를 변경할 수 없습니다. 이는 배열의 단점 중 하나로, 배열의 크기를 동적으로 변경해야 하는 상황에서는 다른 자료구조를 사용해야 할 수 있습니다

 

배열은 같은 유형의 데이터를 저장하는 데이터 구조이다. 배열은 연속된 메모리 블록에 저장되므로 데이터에 대한 접근이 빠르다는 장점이 있다. 하지만 배열의 크기는 고정되어 있으므로 데이터를 추가하거나 삭제할 때 비효율적일 수 있다.

 

 

 

 

배열은 연속된 메모리 블록이다?

 

 

배열은 연속된 메모리 블록이다. 

따라서 배열의 원소에 접근할 때는 인덱스를 사용하여 접근할 수 있다.

 

 

 

 

 

배열은 동적인 자료구조가 아니고 유한하고 고정된 수의 원소로 이뤄진다

 

배열은 동적인 자료구조가 아니고 유한하고 고정된 수의 원소로 이루어진다.

따라서 배열의 크기를 변경하려면 새로운 배열을 만들어야 한다.