https://www.acmicpc.net/problem/1197 이 문제는 스패닝 트리를 생성할 때 가중치의 합을 구하면 된다. 스패닝 트리는 크루스칼 알고리즘을 사용해 구현하였다.union - find를 사용해 스패닝 트리를 생성할 수 있었다. 부모가 같지 않다는 것은 스패닝 트리를 만들 수 있는 조건에 해당하기 때문에answer에 가중치를 누적하면 된다. 부모가 같지 않는지 확인하는 것은 find함수를 사용한다. #include #include #include using namespace std;int V, E;int parent[10001];vector>> costs;int answer = 0;int find(int x) { if (parent[x] == x)return x; else return..
Baekjoon Review
https://www.acmicpc.net/problem/1786 이 문제는 KMP 알고리즘을 사용해서 중복 문자열을 찾는 것이다. KMP알고리즘은 아래 참고https://hanseongbugi2study.tistory.com/310 [Algorithm] KMP 알고리즘Knuth-Morris-Pratt(KMP) 알고리즘패턴을 문장안에서 좌에서 우로 비교하는 것완전 탐색과 다르게 효율적으로 패턴을 찾을 수 있다.패턴과 문장의 불일치가 발생하였을 때 중복 연산을 최대한 피하면hanseongbugi2study.tistory.com 실패함수는 아래 코드와 같다.void Failure(){ int j = 0; for(int i = 1;i0 && P[i] != P[j]) j = tab..
https://www.acmicpc.net/problem/1305 어느 순간 전광판을 바라보았을 때의 문자열에 가능한 광고 문자열의 길이를 찾아내는 것이 핵심이다.따라서 실제 광고의 길이가 어떤지는 중요한 점이 아니다.입력으로 주어진 문자열에서 가능한 광고의 길이를 찾아내는 것. "aabaaa" 라는 문자열에서 가능한 광고 길이 중 가장 짧은 것을 알아내 보자광고판의 길이가 6인 점은 입력을 통해 할 수 있다.따라서 어느 순간 광고판을 바라보았을 때의 문자열의 접미사는 곧 광고의 접두사여야 한다.왜냐하면 광고판의 문자열은 한칸씩 옆으로 이동하기 때문이다. "aabaaa"의 접미사 "aa"는 광고 "aaba"의 접두사인 "aa"가 된다.즉, (광고 + 광고의 접미사) 형태로 전광판의 남은 부분을 광고의 접..
https://www.acmicpc.net/problem/2504 이 문제는 괄호 검사의 응용 버전이다. 괄호를 검사할 때는 스택을 사용한다.스택의 top과 현재 배열에 있는 요소가 쌍이 맞지 않는다면옳은 괄호가 되지 않는다. 문제에서는 ()인 경우 2의 값으로 대응되도록 하고, []인 경우 3의 값으로 대응되도록 한다.또한 [x]인 경우 x * 3으로 연산 하며, [x y]인 경우 x * 3 + y * 3으로 연산한다. 따라서 괄호가 닫히면 x값을 결정하도록 하면 된다.이를 위해 temp변수를 지정하였다.temp변수에 여는 괄호를 만나게 된다면 괄호에 대응되는 값을 곱한다.그러면 (())인 경우 temp에는 4가 저장될 것이다.if(str[i] == '('){ temp *= 2; s.pu..
https://www.acmicpc.net/problem/2493 이 문제는 오큰수 문제와 유사한 방식으로 해결하였다.스택을 사용해서 문제를 접근하였다. 오큰수는 뒤에서부터 스택에 값을 넣고스택의 top이 현재 검색할 값보다 클때까지 스택을 pop한다.이후, 스택의 top을 오큰수로 지정한 것을 알 수 있다. 위 방식을 반대로 생각하면배열의 앞에서부터 스택의 요소로 집어 넣으면배열의 가장 앞에 있는 요소는 스택이 비어 있으므로 0이 될 것이다.이후 스택에 가장 앞에 있는 요소를 넣고, 그 다음 배열의 요소를 통해 스택의 top과 비교해 스택의 top이 작으면 스택에서 pop한다. #include #include using namespace std;int N;int tops[500001];stack> s;..
https://www.acmicpc.net/problem/17298 문제에서 오큰수는 오른쪽에 있는 가장 인접한 큰 수라고 나와있다.따라서 기본적으로 오큰수를 찾는 방법은2중 배열을 사용해서 구하면 된다. 하지만 위 방식은 O(N^2)이기 때문에 시간 초과가 발생한다. 따라서 스택을 사용한 방식을 사용해야한다.스택을 사용해 오큰수를 구하는 방식은 아래와 같다.1. 맨 뒤에 있는 수 부터 순차적으로 탐색한다.2. 스택에 top에 있는 값이 현재 알아볼 값보다 작거나 같으면 스택에서 제거3. 스택이 비어있다면 -1을 오큰수로 지정하거나, 스택의 top을 오큰수로 지정4. 스택에 현재 탐색할 값을 삽입 위 방식을 사용하면 [3, 5, 2, 7]인 경우 아래와 같이 흘러가게 된다.1. S : {}A : 7NGE..
https://www.acmicpc.net/problem/14503 이 문제는 BFS와 유사한 방식으로 해결하였다. 우선, 로봇 청소기는 주변의 4개의 칸에 대해 움직일 수 있으면 시계 반대 방향으로 회전한다.하지만 로봇 청소기의 현재 방향을 가리키는 변수 d의 값은 시계 방향으로 흘러간다.따라서 dy, dx 배열에 시계 반대 방향으로 이동 방향을 결정해준다.int r, c, d; // 0 : 북, 1 : 동, 2 : 남, 3 : 서int dy[4] = {-1, 0, 1, 0}; // 북, 서, 남, 동int dx[4] = {0, 1, 0, -1}; 방에 있는 로봇 청소기의 현재 위치가 벽일 경우 이동을 멈추게 구현하였다.문제에는 로봇 청소기가 뒤로 이동할 수 없는 경우 이동을 멈추라고 나와있지만로봇 청..
https://www.acmicpc.net/problem/9466 DFS를 사용해 순환하는 그래프인지 확인하는 것이다. 입력을 통해 다음 노드를 알 수 있고처음 DFS함수를 호출한 값으로 돌아가야 circle 형태가 된다. 따라서 next 값이 방문하지 않은 node인 경우 DFS를 수행하게 된다. 이미 이전에 방문한 노드인 경우사이클을 형성하였는지 확인해야한다. 사이클 형성을 확인하는 방법은 done배열을 사용한다.done값이 아직 false인 경우 사이클 확인 여부를 검사하지 않은 것이다.따라서 자기 자신을 포함해 이동할 수 있는 모든 노드의 개수를 구하면 사이클인 노드의 개수를 구할 수 있다. 방문한 노드들은 done 배열에 true로 체크하여 사이클 여부를 확인하지 않도록 한다. 따라서 1번노드에..
