[Coding Test] Coding Tips 1 : ABS(x) macro used in DFS

September 23, 2021

삼성B형을 위한 코딩 팁 시리즈

Python 개발자의 PRO 취득을 위한 C++ 공부 여정

DFS 설계 공식

두 가지 탐색 방법 중 DFS 를 설계하는 요소를 아래와 같이 정리해 볼 수 있겠다. 내가 문제를 풀며 느낀 기본 공식은 다음과 같다. dfs() 를 선언할 때, 기본적으로 결정할 사항은 다음과 같은 7가지다. 무조건 외운다고 생각하자.

(1)global 변수

(2)반환형 dfs(   (3)인자   ) {
    (4)종료 조건 {
        (5) 종료 동작
    }

    (5)Prunning

    (6)탐색

    (7)동작
}

이 기본적인 형태를 기억하고, 각 요소는 문제를 푸는 경험을 통해 작성하는 요령을 체득하자. 무작정 문제를 푸는 것보다 기본형을 되새기며 문제를 풀다보면 사고하는 프로세스가 정립될 것이다.

한 가지 예시로 아래와 같은 매크로 function 을 정의해 (5)Prunning 과정에 활용하여 탐색 범위를 줄일 수 있다. 최근 절대값을 노드 탐색 과정에 활용하는 문제 유형을 심심치 않게 경험했다. 꼭 익혀두도록 하자.

#define ABS(x) (x > 0 ? x : -x)

끝으로 탐색을 반복문을 통해 구현하는 과정에서 Queue를 사용하면 BFS, Stack을 사용하면 DFS 를 만들 수 있다.

return a + b + c + ... + → return a + dfs(next) 로 바꿀 수 있음
재귀 함수에 전달되는 파라미터를 Memoization 결정 요소로 사용할 수 있음
파라미터 설정 Trade off
- 전역변수화: 메모리 효율이 높아진다
- 파라미터 전달: 재귀 함수 앞 뒤로 전역변수를 초기화 할 필요가 없어진다
수식으로 표현하여 $\sum$ 이나 $f(n) = a f(n-1) + b (f(n-2) + …$ 등을 재귀로 표현한다