![]()
오늘 기업 코테를 보았다. 누적합에 대해 2문제씩이나 출제가 되었다. 문제를 다 풀긴 했지만 효율성에서 어떻게 될지 모르겠다. 오늘 코테 풀이에 아쉬움이 남아서 누적합에 대해 다시 돌아보는 시간을 가져보자. 코테의 첫 번째 누적 합의 문제는 연속된 k개의 값들의 합 중에서 가장 큰 값을 출력하는 문제였다. 나는 해당 문제를 슬라이딩 윈도우 알고리즘으로 해결하였다. 슬라이딩 윈도우 알고리즘(Sliding Window Algorihtm)은 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다. 예르 들어 정수로 이루어진 배열 {1, 4, 2, 5, 1}에서 길이가 2인 서브 배열의 합계가 가장 큰 서브 배열을 구할 때, 해당 알고리즘을 이용해서 해결한다. 슬라이딩 윈도우는 크기가..
![]()
깊이 우선 탐색 너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색(DFS, depth, first search)은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다. 시간 복잡도 : O(V+E) DFS는 대체로 시작 정점에서 멀이 있는 정점을 찾을 때 적합하다. DFS는 최단 경로를 보장하지 않는다. DFS에 의해 생성된 검색 트리는 길고 좁은 편이며, 상대적으로 적은 메모리를 필요로 한다. 깊이 우선 탐색 관련 문제 [프로그래머스] [level2] 타..
![]()
너비 우선 탐색 너비 우선 탐색(BFS, Breadth, First Search)은 시작 정점을 경계에 추가하는 것으로 시작한다. 경계는 이전에 방문했던 정점들에 의해 구성된다. 그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다. 다음에 나오는 그림을 보면서 BFS 동작에 대해 짐작하면 좋다. 시간 복잡도 : O(V+E) BFS는 시작 정점에서 가까운 정점을 찾는데 적합하다. BFS에서 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장한다. BFS는 현재 경계에 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며 많은 메모리를 필요로 합니다. 너비 우선 탐색 관련 문제 [프로그래머스] 2021.08.10 - [컴도리돌이 전공 공부/C++] ..
