24.07.30 알고리즘 복습 - BFS/DFS & 기술 면접 준비

 

거의 2-3주 동안 약속이 많았어서 제대로 놀아버렸다.. 갑자기 친해진 사람들과 매일 같이 만나서 놀다보니 공부는 뒷전이 되어버렸습니다.. 하하 그래도 코드트리는 매일(?) 조금씩 풀었지만 너무 나태해져버린 나를 발견하곤 급하게 공부 다시 시작이다!!!!!  (이러고 또 놀면 그냥 사람 아님 제발 공부 좀 하자 ㅠㅠ ) 

 

확실히 코드트리를 풀다 보니 배열에 대한 이해가 조금씩 채워지고 있다. 그리고 문제 푸는 재미가 조금 들려버렸다. 그래서 이젠 다시 백준으로 돌아가 알고리즘 복습을 하며 잔디를 심어나갈 생각이다.

 

---

 

 

오늘은 BFS/DFS 학습을 하였다. 내 블로그에 정리해놨던 이론을 한번 쭉 읽어보고 풀었었던 알고리즘 문제들을 다시 풀어보았다. 바이러스, DFS and BFS, 단지번호 붙이기, 유기농 배추, 알고리즘 수업 - 너비우선탐색 1 총 5문제를 풀었다. 

 

DFS and BFS

 

BFS는 너비 우선 탐색으로 인접한 노드를 먼저 탐색한다. 주로 최단 경로를 찾고 싶을 때 사용하고 큐를 이용하여 구현한다.

DFS는 깊이우선 탐색으로 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동하여 탐색한다. 모든 노드를 방문하고자 하는 경우에 사용하고 스택 또는 재귀함수로 구현한다.  BFS에 비해 간단하지만 검색 속도가 느리다.

import sys
from collections import deque
input = sys.stdin.readline

n, m, v = map(int,input().split())

graph = [[0] * (n+1) for _ in range(n+1)]
visited_bfs = [False] * (n+1)
visited_dfs = [False] * (n+1)

for i in range(m):
    n1, n2 = map(int,input().split())
    graph[n1][n2] = 1
    graph[n2][n1] = 1

def bfs(x):
    q = deque()
    q.append(x)
    visited_bfs[x] = True
    
    while q:
        a = q.popleft()
        print(a, end=" ")
        for i in range(1, n+1):
            if graph[a][i] == 1 and not visited_bfs[i]:
                q.append(i)
                visited_bfs[i]= True

def dfs(x):
    visited_dfs[x] = True
    print(x, end= " ")
    
    for i in range(1, n+1):
        if graph[x][i] == 1 and not visited_dfs[i]:
             dfs(i)
dfs(v)
print()
bfs(v)

 

알고리즘 수업 - 너비우선탐색1

 

처음에 그래프를 인접 행렬로 표현하여 코드를 작성하였나 메모리 초과가 발생하였다. 그래서 gpt에 물어보니 인접 행렬을 사용하면 메모리 사용량이 O(N^2)가 되어서, N이 큰 경우 메모리 초과가 발생할 수 있다고 한다. 그래서 인접 행렬 대신 인접 리스트로 표현하는 것이 효율적이다고 해서 바로 인접 리스트로 바꿔서 표현하였다.

• 인접 리스트 O(V+E)
• 인접 행렬 O(V^2)

 

그리고 문제를 잘 안읽어서.. 해당 정점들의 방문 순서를 출력하라는 것을 계속  정점들을 출력해서 틀렸습니다만 4번.. 그래서 결국 풀이를 봐버렸따..!  cnt에 방문 순서를 저장하여 해당 정점들에 방문 순서를 기록하고 증가시킨다.

import sys
from collections import deque
input = sys.stdin.readline

N,M,R = map(int,input().split())
graph = [[] for _ in range(N+1)]

visited_bfs = [0] * (N+1)
cnt = 1
for i in range(M):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(N+1):
    graph[i].sort()

def bfs(x):
    q = deque()
    q.append(x)
    global cnt
    visited_bfs[x] = cnt
    cnt += 1
    
    while q:
        x_ = q.popleft()
        for i in graph[x_]:
            if not visited_bfs[i]:
                q.append(i)
                visited_bfs[i] = cnt
                cnt+=1

bfs(R)
for i in visited_bfs[1:]:  
    print(i)

---

기술 면접 대비

앞으로 이 분이 정리하신 게임 개발자 면접 질문 정리를 보고 공부할 예정이다.

깃허브 링크 주소

https://github.com/Romanticism-GameDeveloper/GameDeveloper-Client-Interview?tab=readme-ov-file

GitHub - Romanticism-GameDeveloper/GameDeveloper-Client-Interview: 게임 클라이언트 개발자 면접 리스트 정리입

 

여기까진 기본적인 걸 정리해봤다. 

1. 객체란 무엇인가?

객체란 변수와 메서드로 구성되어 있는 프로그램에서 기능을 실행시키는 단위입니다. 

 

2. 자료구조가 무엇인가요?

데이터를 구성하고 저장하는 방법을 의미합니다. 배열/리스트/딕셔너리를 사용하여 데이터를 관리하고 저장할 수 있습니다. 배열은 같은 타입의 데이터를 연속적인 메모리 공간에 저장하며, 리스트는 동적으로 크기를 조정할 수 있고, 비연속적인 메모리 공간에 저장합니다. 또한 딕셔너리는 키-값 쌍으로 데이터를 저장하고 검색하는 데 주로 사용됩니다. 

 

3. 배열과 리스트의 차이점을 알려주세요.

배열은 크기가 고정되어 있고 연속적인 메모리 공간에 할당되지만, 리스트는 크기가 가변적이고 비연속적인 메모리 공간에 할당됩니다. 그래서 배열은 삽입과 삭제가 번거롭고 시간이 오래걸리지만, 리스트는 삽입과 삭제가 빠릅니다. 또한 배열은 인덱스를 통한 빠른 접근이 가능하지만 리스트는 순차적으로 접근해야 합니다.