Algorithm

그래프 탐색 기법인 DFS와 BFS에 대해 알아보았다. 깊이 우선 탐색그래프의 깊이 방향으로 먼저 탐색쉽게 말하면 하나의 branch를 모두 탐색한 뒤에 다음 branch 탐색그래프를 완전히 탐색할 때 주로 사용스택이나 재귀함수를 사용노드 방문 여부를 체크하지 않으면

그래프 알고리즘에서 최소 비용을 구하는 문제에서 사용하는 대표적인 알고리즘이다. 두 노드 사이의 비용을 구하는 문제에 유용하게 사용된다.시작 노드와 직접적으로 연결된 정점들의 비용을 업데이트해준다.시작 노드를 방문한 노드로 체크하면 이후로는 방문한 노드의 최소비용을 업

KMP 알고리즘은 문자열 안에서 주어진 문자열을 찾는 알고리즘으로 O(nm)을 O(n+m)으로 개선시킬 수 있다.apple로 예를 들어 본다.prefix는 a, ap, app, appl, apple가 된다.suffix는 e, le, ple, pple, apple가 된다

1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘이다. 투 포인터 알고리즘을 통해 결과를 구하게 되면 시간복잡도를 O(n^2)에서 O(n)으로 단축시킬 수 있다. 투 포인터 알고리즘을 크게 2개로 나누면 두 포인터가 모두 같은 방향으로 움직이는 알

다이나믹 프로그래밍은 하나의 문제는 단 한 번만 풀도록 하여 계산 수를 줄이는 효율적인 알고리즘이다. 다이나믹 프로그래밍을 얼핏 봤을 때는 분할 정복과 다를게 없어보인다. 하지만 분할 정복의 계산을 여러번 해야 하는 점을 본다면 이는 다이나믹 프로그래밍과 다른 것을 알