백준 문제풀이93 [백준][bfs] 2468 안전 영역 c++ 구현 목차 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 문제 구현 방향 물에 잠기지 않는 영역을 세어주는 방식으로 구현했다. bfs를 여러번 돌리면 쉽게 풀리는 문제이다. 문제 구현시 주의점 빗물 높이가 0인 경우도 있다는 점을 주의해야 한다. 코드 구현 #include #include #include #include using namespace std; int dx[4] = { 0, 0, -1, 1 }; int dy[4] = { 1, -1, 0,.. 2024. 4. 2. [백준][스택] 9935 문자열 폭발 c++구현 목차 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 문제 구현 시 주의점 문자 길이가 매우 길기 때문에 시간복잡고다 O(N^2) 나오게 되면 시간초과가 되므로 주의해야 한다. 하지만 비교 문자열의 크기는 36으로 매우 작으므로 스택을 통해 검사하면서 넣어 주게 되면 O(N)시간 복잡도를 가질 수 있다. 문제 풀이 비교 문자열이 12ab라면 b인 끝 문자열과 같지 않다면 그냥 스택에 넣어준다. 끝 문자열과 같다면 기존 스택에.. 2024. 4. 1. [백준][분할 정복] 1629 곱셈 c++구현 목차 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 문제 풀이 시 신경써야 할 점 시간 복잡도 -> 범위가 굉장히 넓기 때문에 for문을 쓸 경우 시간초과가 난다. 따라서 분할 정복을 통해 시간 복잡도는 O(logN)을 만들어 주어야 한다. int형 범위 -> int형 보다 훨씬 크기 때문에 long long int를 써주어야 한다 (a+b) % c = a%c + b%c (axb) % c = a%c x b%c 수학적 원리를 잘 이용해 초과를 막아야한다. 코드 구현 #include #include #in.. 2024. 3. 30. [백준][스택] 3986 좋은 단어 c++구현 목차 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제 문제 풀이 스택이 비어있다 -> 문자를 넣어준다. 스택이 비어있지 않다 -> 1.스택의 top값과 들어갈 값이 같으면 스택에서 pop해준다. 2.스택의 top값과 들어갈 값이 다르면 그냥 넣어준다. 문자열을 다 순회한후 스택이 비어있다면 1, 비어있지 않다면 0을 리턴해 준다. 코드 구현 #include #include #include using namespace std; int check(str.. 2024. 3. 30. 이전 1 ··· 12 13 14 15 16 17 18 ··· 24 다음 728x90
