본문 바로가기

전체 글384

14502 백준 c++ -[PlusUltraCode] [필자 사고] 전형적인 2차원 그래프 탐색문제다 이 문제의 특이한 점은 벽을 세운다라는 점이다. 바이러스가 감염되어 다른 배열에 영향을 끼치는 문제는 수도 없이 풀어 봤을 것이다. 문제의 막히는 주요 원인은 어떻게 벽을 세워 BFS탐색을 수행하는 지다. 필자는 다음과 같이 벽을 세우는 방식을 사용했다. 1. space 배열에 0이 들어간 index를 모두 넣어주었다. 2. vis라는 배열에는 bool값을 넣어주었다. 재귀 함수를 이용하여 space 배열내에 있는 모든 x와 y의 값을 Copy_Arr 에 넣어주어 하나 하나 BFS탐색을 진행시켰다. [소스 코드] #include #include #include using namespace std; vector Arr; vector visited; vecto.. 2024. 2. 23.
백준 11660 c++ -[PlusUltraCode] https://cocoon1787.tistory.com/377 그림 출처 [필자 사고] 전형적인 구간 합 알고리즘을 사용하는 문제이다. 2차원 평면에서 구간합 알고리즘을 사용하기 위해서는 위의 그림을 통해 이해 해야 된다. 기본적으로 S라는 구간합을 만드는 배열이든 그 배열에서 범위 내 합을 구하든 똑같은 원리가 적용된다. 1. 1번 그림에서 2번과 3번 그림을 빼고 4번그림은 두번 빼진거므로 한번 더해주면된다. 2. S[i][k]= 2번 빼고 3번빼고 4번 더한다. [소스 코드] #include #include #include #include using namespace std; int N, M; vector Arr; vector S; void Input() { cin >> N >> M; Arr.res.. 2024. 2. 22.
백준 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.

티스토리툴바