코딩테스트2 알고리즘 문제 풀이에 접근하는 방법 문제 접근 방법에 대해서 알고리즘에서 10의 8승 (10^8)이란? 일반적으로 연산을 10^8번하면 1초 정도로 생각합니다. 이것만으로 코테문제의 알고리즘을 추론할 수 있습니다. 시간 복잡도의 중요성 1부터 n까지 더하는 알고리즘이 있다고 가정하겠습니다. 1 + 2 + 3 + ... + n = ? 코드로 구현 한다면 forloop를 돌며 1부터 n까지 더하면 됩니다. def sum(n): answer = 0 for i in range(n+1): answer += i return answer 하지만 n이 크다면 ? 1 + 2 + 3 + ... + 10^8 = ? 위 코드는 n이 클 경우에는 시간이 매우 오래걸리기 때문에 수학적 공식을 구해서 계산해야 합니다. def sum(n): return n * (n .. 2023. 8. 30. DFS(Depth First Search)란? DFS(Depth First Search) 아래 글들은 이것이 코딩 테스트다의 강의를 기반으로 개인의 이해를 돕기 위해 정리한 글입니다. DFS 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조 혹은 재귀함수를 이용한다. 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 동작 과정 이해 하기 시작 노드인 ‘1’을 스택에 삽입하고 방문 처리를 합니다 스택의 최상단 노드인 ‘1’에 방문하지 않은 인접 노드 ‘2’, ‘3’, ‘8.. 2023. 6. 11. 이전 1 다음
