코딩테스트 관련 내용 정리 (1)

그리디 ; 현재 가장 좋아 보이는 것만을 선택하는 알고리즘

---

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음

- 문제에서 '가장 큰 순서대로','가장 작은 순서대로' 등등 표현이 나오면 그리디로 풀 수 있는지 생각해보기

- 그리디와 정렬문제는 짝을 이뤄 출제되기도 함

 

구현 ; 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기

---

- 일반적으로 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적

ex) dx=[-1,0,1,0]  dy=[0,-1,0,1]

 

 

DFS/BFS ; 그래프를 탐색하기 위한 방법

---

▶ DFS (Depth-First Search, 깊이 우선 탐색)

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 스택사용 (파이썬에서는 리스트)

(1) 탐색 노드를 스택에 삽입하고 방문처리

(2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리 

      방문하지 않은 인접노트가 없으면 스택에서 최상단 노드를 꺼낸다(3) (2)번 과정을 더 이상 수행할 수 없을 때까지 반복한다.tip) 인접한 노드 중에서 방문하지 않은 노드가 여러개라면 번호가 낮은 순서대로 진행한다.

 

DFS 예제코드

DFS/BFS 예제 그래프

# DFS
def dfs(graph, v, visited):
    visited[v] = True  # 현재노드 방문처리
    print(v, end=' ')
    # 재귀적으로 방문
    for node in graph[v]:
        if not visited[node]:  # 방문 안했으면
            dfs(graph, node, visited)

graph = [
    [],
    [2, 3, 4],  # 1번노드와 연결된 노드
    [5, 6],
    [1],
    [1, 7],
    [2],
    [2],
    [4]
]

visited = [False] * 8
# 함수 호출
dfs(graph, 1, visited)

# 출력결과
1 2 5 6 3 4 7

 

▶ BFS (Breadth-First Search, 너비 우선 탐색)

- 가까운 노드부터 탐색하는 알고리즘 

- 큐 자료구조 이용 (파이썬에서는 deque 사용)

- 문제에서 모든 간선의 비용이 1, 모든 간선의 비용이 동일하다는 조건이 나온 경우 BFS를 사용

(1) 탐색 시작 노드를 큐에 삽입하고 방문처리

(2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

(3) (2) 번의 과정을 수행할 수 없을 때까지 반복

 

BFS 예제 코드

# BFS
from collections import deque #deque 사용해서 구현

def bfs(graph, start, visited):
  queue=deque([start])
  # 현재노드 방문처리
  visited[start] = True
  # 큐가 빌때까지 반복
  while queue:
    # 원소를 하나 뽑기
    v=queue.popleft() 
    print(v, end=' ') # 뒤에 빈칸 붙여서 출력
    # 해당 원소와 연결된 노드들 중 아직 방문하지 않은 노드들을
    # 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True

graph = [
    [],
    [2, 3, 4],  # 1번노드와 연결된 노드
    [5, 6],
    [1],
    [1, 7],
    [2],
    [2],
    [4]
]

visited = [False] * 8
# 함수 호출
bfs(graph, 1, visited)

 

Deque(Double-Enabled Queue, 덱)

---

- 스택과 큐의 장점을 모두 갖고 있음

- 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단

- 파이썬으로 큐를 구현할 때 사용 (collections 모듈에서 제공함)

- from collections import deque

- 삭제 : popleft() / 삽입 : append(item)

 

 

 

 

 

참고문헌 및 출처 | 나동빈. 2020. 이것이 취준을 위한 코딩 테스트다 with 파이썬. 한빛미디어