전체 글

https://www.acmicpc.net/problem/1504 이 문제는 다익스트라 알고리즘을 활용한다. 다익스트라를 활용해서 무조건 거쳐야하는 정점까지의 최단 거리를 구한다.이후 그 정점에서 부터 N까지의 최단 거리를 구하면 해결할 수 있다.즉, 다익스트라 알고리즘을 3번 활용한다. 1번 정점에서부터 다익스트라 알고리즘을 활용하면1번 정점애서부터 모든 정점에대한 최단 거리를 구할 수 있다.따라서 1번 정점에서부터 u와 v정점까지의 최단 거리를 저장한다.dijk(1);int to_u = dist[u];int to_v = dist[v]; 1에서부터 u와 v정점까지의 최단 거리를 구했다면u에서 N와 v 정점간의 최단 거리와 v에서 N간 최단 거리를 구한다.v에서 u까지의 최단거리를 구하지 않는 이유는 양..

https://www.acmicpc.net/problem/11779 다익스트라 알고리즘을 활용하는 문제입력으로 시작점과 끝점을 알려준다.따라서 시작점에서 끝점까지의 최소 비용을 구하면 해결할 수 있다. 시작점에서 끝점까지의 최소 비용을 구하는 방법은 일반적인 다익스트라 알고리즘을 활용하면 구할 수 있다.하지만 최소 비용을 갖는 경로를 구해야하기 때문에 route배열을 따로 정의해야한다. 다익스트라 알고리즘의 경로는 now로 부터 next를 구하며dist[next]가 최소일때 다음 경로가 된다.따라서 dist[next]가 최소 일때 rout[next]에 now를 넣게 된다면끝점에서부터 시작점 까지의 경로를 저장할 수 있다. #include #include #include using namespace std..

https://www.acmicpc.net/problem/5639 문제에서 입력은 이진 탐색 트리의 전위 순회의 결과로 주어진다.이때 입력의 종료 조건은 트리의 순회 결과가 모두 들어올때 까지 이다.따라서 반복의 조건에 입력이 끝날때 까지 받도록 한다.while(cin>>input){ tree[idx++] = input;} 전위 순회의 결과를 보면 왼쪽 노드의 값은 루트보다 작으며, 오른쪽 노드의 값은 루트보다 큰 것을 알 수 있다.따라서 루트보다 작은 것은 왼쪽 노드이며, 루트보다 큰 것은 오른쪽 노드이다.위 정의는 부모 자식 노드간의 관계에도 성립한다.따라서 입력 배열의 현재 위치와 그 다음 인덱스의 값이 작으면 왼쪽 노드로 생각하고 크면 오른쪽 노드로 생각하면 된다.   #include..

https://www.acmicpc.net/problem/14502 이 문제는 BFS를 사용하면 해결할 수 있다. 연구소에는 벽 3개를 세울 수 있고, 벽에 따라 바이러스가 퍼지는 수는 상이하다. 따라서 벽을 3개 세우고, BFS를 통해 바이러스를 퍼지게 하면 된다.바이러스가 퍼지면 2가 배열을 채우게 되므로 새로운 배열이 필요하다.또한, 벽을 세우게되면 1이 배열을 채우게 되므로 새로운 배열이 필요하다.따라서 temp배열을 통해 벽을 세우고, spread 배열을 통해 바이러스를 퍼트린다. 벽을 세우는 과정은 제귀 형식으로 해결하였다.원본 배열을 순차적으로 순회하여 값이 0인 경우 먼저 temp 배열에 원본의 값을 복사시킨다. 이후, 복사된 배열에 벽을 세운다.(1로 값을 변경)1개의 벽에 대해 모든 경..

https://www.acmicpc.net/problem/12851 이 문제는 BFS를 사용하면 해결할 수 있다. 수빈이가 움직일 수 있는 경우의 수는 3가지다.뒤로 1칸, 앞으로 1칸, 2배 전진하는 경우이다.따라서 dir 배열 속에 {-1, 1, 0}을 넣고 0인 경우 2배 전진하도록 한다. 현재 위치가 동생의 위치인 경우 최소 시간과 현재 시간을 비교하여최소 시간이 더 큰 경우 동생을 찾을 수 있는 수를 1로 초기화 하고 최소 시간을 갱신한다.만약 최소 시간이 현재 시간과 같다면 동생을 찾을 수 있는 수를 1 증가시킨다. #include #include using namespace std;int N, K;int minTime = 987654321;int answer = 0;bool visited[1..

https://www.acmicpc.net/problem/2096 이 문제는 DP를 사용해서 해결할 수 있다. 문제에서 주어지는 가로의 길이는 항상 3이며, 세로의 길이는 N이다.따라서 최소 DP와 최대 DP 배열을 만들고 배열의 크기는 3으로 한다. 항상 이전의 기록을 이용하기 때문에 입력을 받기 위한 크기 3의 배열이 필요하다. #include using namespace std;int N;int score[3];int minDp[3];int maxDp[3];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>N; int temp0, temp1, temp2; for(int i = 0;i>..

https://www.acmicpc.net/problem/9935 처음 문제를 해결할 때 find 함수와 erase함수를 사용했다.하지만 find 함수에 필요한 시간과 erase함수에 필요한 시간 때문에최대 길이의 문자열일 경우 시간 초과가 발생하였다. 따라서 스택을 사용해서 문제를 해결하였다. 스택을 사용해 문자열을 폭발 시키는 과정은 다음과 같다.1. 스택에 문자열에 있는 문자를 순차적으로 삽입한다.2. 스택에 들어있는 문자의 개수가 폭발 문자열의 길이와 같거나 클 경우폭발 문자열의 길이만큼 스택에서 문자를 꺼낸다꺼낸 문자열과 폭발 문자열이 일치한 경우 스택에서 제거한다. #include #include #include using namespace std;string target;string bomb..

https://www.acmicpc.net/problem/10830 지수가 int 값 범위를 초과할 수 있으므로 거듭 제곱을 하는 과정에서 시간 초과가 발생할 수 있다. 이는 지수 법칙과 나머지 연산의 성질을 이용해서 해결할 수 있다.지수법칙a^(n + m) = a^n + a^m모듈러 성질(a x b) mod c = (a mod c x b mod c) mod c(a * b) % c = (a % c * b % c) % c 지수 법칙 이용 방법짝수인 경우a^8 = a^4 * a^4 = (a^2 * a^2) * (a^2 * a^2) = ((a^1 * a^1) * (a^1 * a^1)) * ((a^1 * a^1) * (a^1 * a^1)) 홀수인 경우a^9 = a^4 * a^4 * a = ..