Jun Jun

DFS(Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. DFS 탐색 과정 이 그래프를 노드 1을 시작으로 DFS를 사용해 탐색이 진행되는 과정을 살펴보도록 하겠다. [Step 1] 시작 노드인 '1'을 스택에 삽입하고 방문 처리 한다 [Step 2] 스택의 최상단 노드인 '1'에..

구현 코딩 테스트에서 구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' 이다. 즉 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제이다. 여기서 구현하기 여려운 문제들의 예시를 들어보자면 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 대체로 사소한 조건 설정이 많은 문제일수록 코드로 구현하기가 까다롭다. 여기서 다룰 구현 유형은 두 가지이다. 모든 경우의 수를 주저 없이 다 계사하는 해결 방법을 의미하는 완전 탐색 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 시뮬레이..

그리디 알고리즘 그리디 알고리즘은 그대로 직역하여 국내에서는 "탐욕 법"으로 소개된다. 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 "현재 상황에서 가장 좋은 것만 고르는 방법"이다. 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 예시로 알아보자. 거스름 돈 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하라.단, 거슬러 줘야 할 돈 N은 항상 10의 배수다. 그리디 알고리즘 문제의 대표 유형으로 가장 간단한 ..