[코딩 테스트] 탐색

다음은 코딩 테스트에 빈출되는 탐색의 빈출 유형과 대비 방법이다.

용어 정리

그래프: 여러 개체들이 연결되어 있는 자료구조
탐색: 특정 개체를 찾기 위한 알고리즘
그래프 탐색 알고리즘: 여러 개체들이 연결되어있는 구조에서 특정 개체를 찾는 알고리즘

 

대표적 문제 유형

밑 3가지의 case가 대표적인 탐색의 문제 유형이며, 2개가 섞여 출제 되는 문제도 있다.

 

1. 경로탐색 유형(최단거리, 시간)
2. 네트워크 유형(연결): 여러 개체들이 주어진 상태에서 연결되어 있는 개체의 그룹 개수 구하기, 연결 여부 확인하기
3. 조합 유형(모든 조합 만들기): 순열, 조합 방식

 

구현 방법

DFS: 재귀 함수 => 탈출 조건을 만족 할 때까지 재귀함수를 구현하고, 이후 파라미터 값을 바꾸어가며 정답을 끝까지 
도출
ex. 프로그래머스 타겟 넘버

BFS: queue/linkedList => 여러가지 방향을 병렬적으로 시행, 순서가 보장되어야 함
1. 가정 먼저 queue에 넣었던 것을 꺼내어
2. 연결된 점을 queue에 넣고
3. queue가 빌 때까지 반복
ex. 프로그래머스 여행경로

 

DFS vs BFS

1. 둘 다 탐색을 위한 알고리즘
2. DFS 가 동작 검증을 하기 편리. 하나씩 조합을 끝까지 만들어 보기 때문
3. DFS는 시간 복잡도가 높음. 운이 좋으면 한번에 최적의 값을 찾지만 최악의 경우 모든 경우의 수를 다 해봄.
4. BFS는 시간 복잡도가 낮다. 직관적이지는 않지만, 시간 초과 날 확률이 적음
5. 보통의 코딩 테스트에서는 시간 복잡도가 매우 높은 testCase 존재 => ex. 프로그래머스 효율성 TC

 

전략:  쉬운 앞쪽에서 탐색 문제 나오면 DFS, 뒤 쪽에서 나오거나 시간 초과 여지 있으면 BFS로 접근

 

예시 코드

다음은 DFS, BFS의 기본 코드이다. 원리와 코드를 암기한 후 문제마다 변형하여 적용한다.

입력 자료형 정의

# 그래프를 인접 리스트로 표현
# 파이썬 자료형에서 출발 노드를 키로, 도착 노드를 값으로 표현
graph = {
	1: [2,3,4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7]
    6: [],
    7: [3],
}

DFS (재귀)

def recursive_dfs(v,discovered = [])
	discovered.append(v)
    for w in graph[v]:
    	if w not in discovered:
        	discovered = recursive_dfs(w,discovered)
    return discovered

DFS (stack)

# 재귀보다 실행 속도 빠름
def iterative_dfs(start_v):
	discovered = []
    stack = [start_v]
    while stack:
    v = stack.pop()
    if v not in discovered:
    	discovered.append(v)
        for w in graph[v]:
        	stack.append(w)
    return discovered

BFS (queue)


+ 삼성 역테 참고

https://eine.tistory.com/entry/%EC%82%BC%EC%84%B1-SW-%EC%97%AD%EB%9F%89%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%B0%8F-A%ED%98%95-%EC%8B%9C%ED%97%98-%EC%A4%80%EB%B9%84%ED%95%98%EA%B8%B0

자주 나오는 case

1. 2차원 배열 => BFS
2. DFS + 조합
3. DFS + 순열

 

백준 문제 링크(해결한 문제는 링크)

코테를 준비하기전 기본으로 풀면 좋은 문제들

BFS

1697 12851 13549 13913 2178 2206 5014 3055 9376 9328 1857 14226 1261

 

DFS

10974 10971 9095 1759 9663 1987 1182 14391 13460 12100