본문 바로가기

전체 글394

백준 9251 c++ -[PlusUltraCode] [필자 사고] 문제를 해석해보면 LCS 알고리즘을 사용해야 한다. LCS 알고리즘은 공부해두면 쉽게 풀 수 있는 문제이다. 1. 각 글자들을 비교한다. 2. 만약 각 단어가 다르다면 왼쪽 or 위쪽 중 큰 값을 저장한다.. 3. 만약 각 단어가 같다면 왼쪽 대각선의 값에서 +1을 더한다 [소스 코드] #include #include #include #include using namespace std; string str1, str2; int Arr[1001][1001] = { 0 }; void Input() { cin >> str1 >> str2; for (int i = 0; i < str1.size(); i++) { for (int k = 0; k < str2.size(); k++) { if (str1.. 2024. 2. 22.
백준 1865 c++ -[PlusUltraCode] [필자 사고] 문제를 해석해 보니 다음과 같은 결론을 내렸다. 1. 출발해서 다시 원점으로 돌아와야 된다. => 사이클이 있다. 2. 웜홀을 통해 내가 쓴 시간보다 더 적은 시간을 사용해야 된다 => 음수 사이클이 있다. 이를 통해 음수 사이클을 대표적으로 판단할 수 있는 벨만포드 알고리즘이 떠올랐다. 벨만포드 알고리즘을 간단하게 설명하겠다. 모든 간선들의 조사를 N-2번 조사한다. 그 후 마지막 한번도 모든 간선들을 조사 했을 때 Distance의 값중 하나가 바뀌게 된다면 음수 사이클이 존재한다는 것을 판별 할 수 있게 된다. [소스 코드] #include #include using namespace std; typedef struct Node { int start; int end; int weigh.. 2024. 2. 22.
백준 1238 c++ - [PlusUltraCode] [필자 사고] 문제를 분석해 보면 X라는 지점에 간 거리와 X에서 부터 본래의 자기 집으로 간 거리의 합이 가장 긴 값을 구하는 문제이다. 다익스트라 알고리즘을 사용하면 쉽게 풀 수 있는 문제이다. 1. 각 지점에서 다익스트라 알고리즘을 사용하고 X까지의 거리를 임의이 배열에 저장해 놓는다. 2. 다음으로 X에서 다익스트라 알고리즘을 사용하여 임의의 배열에 더하여 저장해 놓는다. 3. 임의이 배열에서 가장 큰 값이 정답이다. [소스 코드] #include #include #include #include #include using namespace std; int N, M, X; typedef pair Node; vector Arr; vector visited; vector pathLoad; vector .. 2024. 2. 20.
백준 1967 c++ -[PlusUltraCode] [필자 사고] 트리의 지름문제이다. 처음보면 당황할 수 있지만 한번만 이해하면 쉽게 풀 수 있는 문제이다. 트리의 지름이란 임의의 두점을 선택했을때 가장 거리가 긴 노드간의 길이를 말한다. 지름을 구하기 위해서는 다음과 같다. 1. 임의의 노드 하나를 선택하여 가장 거리가 먼 노드를 구한다. 2. 가장 거리가 먼 노드에서 다시 시작하여 가장 거리가 먼 노드를 또 구한다. 3. 2번째로 구한 가장 거리가 먼 노드의 길이가 지름의 길이이다. 문제를 해결하는 알고리즘은 dfs 다익스트라 등등 많이 있고 필자는 다익스트라를 이용하여 해결했다. [소스 코드] #include #include #include #include using namespace std; typedef pair Node; vector Arr;.. 2024. 2. 20.

티스토리툴바