Study with book/Algorithms
[백준]DFS와 BFS2
백준저지 [DFS와 BFS]https://www.acmicpc.net/problem/1260 DFS와 BFS는 총 3번에 걸쳐서 포스팅을 하려고 한다. 이번 포스팅에서는 BFS에 대한 설명을 위주로 하려고 한다. 전체 소스는http://vvshinevv.tistory.com/12 를 참고하자. • 본문에 들어가기에 앞서 DFS와 BFS를 구현하기 위해서는 그래프 자료구조를 구현할 수 있어야 한다. • 필자는 그래프 표현 방법 인접 행렬과 인접리스트 중 인접리스트를 이용하였다. • 아래 예시는 백준저지에서 예시로 제공한 것을 사용한다. • BFS(Breath First Search) - 너비 우선 탐색으로 시작 정점으로부터 가장 가까운 정점을 먼저 전부 방문을 하고 멀리 떨어져 있는 정점을 제일 나중에 방..
[백준]DFS와 BFS1
백준저지 [DFS와 BFS]https://www.acmicpc.net/problem/1260 DFS와 BFS는 총 3번에 걸쳐서 포스팅을 하려고 한다. 이번 포스팅에서는 DFS에 대한 설명을 위주로 하려고 한다. 전체 소스는http://vvshinevv.tistory.com/12 를 참고하자. • 본문에 들어가기에 앞서 DFS와 BFS를 구현하기 위해서는 그래프 자료구조를 구현할 수 있어야 한다. • 필자는 그래프 표현 방법 인접 행렬과 인접리스트 중 인접리스트를 이용하였다. • 아래 예시는 백준저지에서 예시로 제공한 것을 사용한다. • DFS(Depth First Search) - 깊이 우선 탐색으로 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아..
[백준]광고
백준저지 [광고]https://www.acmicpc.net/problem/1305 • kmp 알고리즘에 대한 정확한 이해가 되어야 풀 수 있는 문제이다. • kmp 알고리즘은 이전 포스팅에 자세히 설명을 해놨으니 참고 바란다! • 현재 보이는 문자열 길이에서 “접두사와 접미사가 같은 최대 길이를 빼면” 정답이다. #include #include using namespace std; int * getPi(string p) { int * pi = new int[(int)p.size()]; pi[0] = 0; int j = 0; for (int i = 1; i < (int)p.size(); i++) { while (p[i] != p[j]) { if (j == 0) { pi[i] = j; break; } j =..
KMP 알고리즘
KMP알고리즘 백준저지 [찾기] https://www.acmicpc.net/problem/1786 본 문제를 해결하기 위해서는 KMP알고리즘에 대해 학습이 되어야한다. (참고로 전 이 알고리즘을 이해하는데 2주가 걸렸다는... T^T...) 먼저 이 알고리즘은 '찾기' 흔히 [CTRL] + [F]를 눌러 문자열 검색을 하는 기능에 필수적으로 들어가는 알고리즘이다. KMP는 Knuth, Morris, Prett의 사람 이름 앞자를 따서 만든 이름이다. 흔히 찾기 알고리즘을 구현하라고 하면 아래와 같은 방식으로 구현을 할 수 있을것이다. "ABCDEF"란 Text에서 "CD"란 Pattern을 찾는다고 한다면, 012345TextABCDEF 01 PatternCDText[0]과 Text[1]이 Pattern..