코딩 테스트/알고리즘 (3) 썸네일형 리스트형 [알고리즘] DFS 및 BFS - Python 그래프를 탐색하는 방법으로 DFS와 BFS가 많이 언급된다. 실제로 코딩 테스트 문제로 자주 출제되며, 경험상 해당 문제들을 이러한 알고리즘 기법 도구들을 사용하지 않고 다가가면 아주 어려웠다. 그러나 DFS와 BFS라는 도구를 익힌다면 엄청 어려워 보이던 최단 거리 구하기 같은 문제들에 자신감이 생기게 된다. 알기 전과 후의 차이가 극명한 알고리즘으로 이번 기회에 정리를 해두면 도움이 될 것 같다. (엘리스 sw트랙 스터디 활동으로 [이것이 취업을 위한 코딩 테스트]다의 DFS 및 BFS 강의를 기반으로 작성한다.) 깊이 우선 탐색 (DFS : Depth First Search) 우선 DFS라고 불리는 깊이 우선 탐색을 먼저 살펴본다. 트리나 그래프 구조에서 각 노드를 검사하는 방법으로 다음 branc.. [알고리즘] 구현 알고리즘 - 시뮬레이션 및 완전 탐색 구현이란? 알고리즘을 공부하는데 구현은 뭐지? 그런 생각이 들었다. 구현이란 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정을 말한다고 한다. 알고리즘 문제를 푸는 입장에서 당연한 것이 아닌가 싶었지만, 풀이를 떠올리기 쉽지만 구현(소스 코드로 옮기기) 이 어려운 문제들을 구현 문제라 부른다고 한다. 다음과 같은 구현 문제에 대한 특징들이 있다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 생각해낸 풀이 방법을 코드로 구현함에 있어서 실수 연산, 문자열 처리, 복잡한 로직 등의 장애물을 돌파하는 것이 관건인 유형이라 볼 수 있다. .. [알고리즘] 그리디 알고리즘(탐욕법) 그리디 알고리즘이란? 알고리즘 중에서 그리디 알고리즘(Greedy Algorithm)은 탐욕법이라고도 불린다. 탐욕이라는 단어는 해당 알고리즘을 가장 잘 표현하지 않았나 싶다. 특정 상황에서 사용되는 방법으로 매 선택 순간마다 묻지도 따지지도 않고 가장 최적의 선택을 반복하여 해답을 구해나가는 방식이다. 선택하는 시점 이후의 상황(최종적인 상황)은 고려하지 않는 방식이라서 그리디 알고리즘을 적용할 수 있는 문제인지 파악하는 것이 관건이다. 그리디를 적용할 수 있는 상황을 다시 말하자면, 지역적인 최적의 선택이 곧 전역적 최적의 선택일 때 사용할 수 있다. 좀 더 확실하게 알아보기 위하여 그리디 알고리즘에 대한 구글링을 통해 자세히 정리된 자료를 가져왔다. 그리디 알고리즘을 적용하기 위한 조건을 다음과 같.. 이전 1 다음
