본문 바로가기

백준189

백준 2468 c++ - [PlusUltraCode] [필자 사고] 이 문제는 전형적인 2차원 배열 탐색문제이다 특이한 점은 물에 잠겨있는 안정 지역의 최댓값을 구해야 한다. 좀 더 효율적인 방법이 있나 생각을 해봤지만 떠오르지 않았고 입력되는 N의 최댓값이 100이므로 시간복잡도 측면에서 문제가 되지 않아 전체 경우의 수를 다 고려해주기로 했다. 물의 높이를 0부터 최대까지 다 고려해 BFS알고리즘을 수행했다. [소스 코드] #include #include #include using namespace std; int dy[4] = { 0,1,0,-1 }; int dx[4] = { 1,0,-1,0 }; vector Arr; vector visited; int N; int maxNum = -1; int ResultCnt = -1; bool Inside(int.. 2024. 2. 23.
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.

티스토리툴바