알고리즘

문제 풀이 다이나믹 프로그래밍, 누적 합 문제이다. 완전 탐색으로 해결하려고 하면 O(N * N)으로 시간 초과이다. 배열을 두 개를 사용하여 문제를 해결해야 한다. 첫 요소가 왼쪽인 배열. 왼쪽이 과반수인 배열. (left) 첫 요소가 오른쪽인 배열. 오른쪽이 과반수인 배열. (right) 전체 배열을 탐색하면서 돌상이 왼쪽인 경우에는, left 배열의 깨달음의 양이 1 증가하면서, right 배열의 깨달음의 양이 1 감소한다. 돌상이 오른쪽인 경우에는, left 배열의 깨달음의 양이 1 감소하면서, right 배열의 깨달음의 양이 1 증가한다. 현재 배열의 깨달음의 양이 0미만이라면 해당 배열을 버린다. 현재 배열 2개의 깨달음의 양의 최대값이 답이다. 코드 #include #include using..

문제 풀이 누적 합 문제이다. https://kantatatam.tistory.com/143 [백준][C++] 30508: 고인물이싫어 문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 kantatatam.tistory.com 2차원 배열에서의 누적 합을 구하는 문제로 위의 30508번 문제와 거의 동일하다. 코드 #include using namespace std; int nums[1001][1001]; int sum[1001][1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.t..

문제 풀이 그리디, 누적 합, 많은 조건 분기 문제이다. N의 최대가 10000이므로 O(N * N)으로는 100점이 불가능하다. 꿀을 가장 많이 채집할 수 있는 경우는 밑의 세 가지이다. 벌집이 가운데 어딘가에 있고, 벌이 가장 왼쪽, 오른쪽에 위치하는 경우 벌집이 가장 왼쪽에 있고, 한 벌은 가장 오른쪽, 한 벌은 가운데 어딘가에 위치하는 경우 벌집이 가장 오른쪽에 있고, 한 벌은 가장 왼쪽, 한 벌은 가운데 어딘가에 위치하는 경우 벌집이 가장 왼쪽 혹은 오른쪽에 위치하는 경우, 한 벌이 벌집과 가장 멀리있는 것이 꿀을 채집하는데 가장 유리하다(최선의 선택). 채집한 꿀을 계산할 때, 누적 합이 사용된다. 코드 #include using namespace std; int sum[100001]; int..

문제 풀이 누적 합 문제이다. O(N * N)이 되면 50점이다. O(N)의 시간복잡도로 해결해야한다. 문자열의 처음부터 시작하여 i번째까지 나온 알파벳마다 배열에 저장해둔다. i번째 문자열이 j일 경우, 이전 j가 등장한 횟수에서 + 1한 값을 배열에 저장한다. 그외에는 이전에 등장한 횟수로 저장한다. 코드 #include using namespace std; int alpha[26][200000]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); string S; cin >> S; // 문자열의 처음부터 시작하여 i번째까지 나온 알파벳을 배열에 저장 alpha[S[0] - 'a'][0]++; for (int i = 1..

문제 풀이 수학, 누적 합 문제이다. N이 1000,000이므로 완전 탐색시 O(N * N)으로 시간초과이다. (A - B) % n = ((A % n) - (B % n) + n) % n 배열의 i번째 수까지의 누적 합을 sum이라고 하자. 임의의 j번째에서 k번째 까지(j > N >> M; // 지금까지의 합인 sum // (sum - x) % M == 0인 경우에 답을 만족하므로, // ((sum % M) - (x % M) + M) % M == 0을 만족해야 한다. // 즉, sum % M == x % M인 x의 수가 answer에 추가된다. // sum % == 0인 경우에는 sum자체도 answer에 추가되야 한다. long long answer = 0; long long sum = 0; for (..

문제 풀이 정렬, 누적 합 문제이다. 각각의 컬러공의 크기 이하의 컬러공을 모두 탐색한다면 O(N * N)으로 시간초과이다. 컬러공을 한 번만 순회하여 문제를 해결해야 한다. 컬러공을 크기의 오름차순으로 정렬한다. 정렬한 컬러공을 처음부터 탐색하면서 현재 i까지의 크기의 합을 구한다. 그 합에서 지금까지 나온 공들 중에서 i번 공과 같은 색을 가진 공들을 뺀다. 그 합에서 지금까지 나온 공들 중에서 i번 공과 같은 무게를 가진 공들을 뺀다(크기 순으로 정렬되어 있으므로 i번 공보다 크기가 큰 공은 현재까지 합해지지 않았다). 이렇게 하면, i번 공과 색상과 크기가 모두 같은 공은 총 두 번 빠진다. 그러므로, 지금까지 나온 공들 중에서 i번 공과 같은 색과 같은 크기를 가진 공들은 한 번 더해줘야 올바른..

문제 풀이 그래프 탐색, 누적합 문제이다. 횡단보도의 칸 중에서 물이 빠질 칸을 BFS로 탐색한다. BFS의 시작은 하수구 칸에서 시작한다. 현재 탐색 중인 칸의 상하좌우 칸 중에서, 현재 칸의 높이 이상인 칸은 물이 빠진다. 신발을 딛을 수 있는 방법의 수는 2차원 배열의 누적합으로 구한다. 위의 그림에서 초록색 영역의 합을 구해보자. 파란색 영역을 모두 한번씩 더한다면 빨간색 영역은 두 번 더해진다. 그러므로, 파란색 영역을 한번 더하고, 빨간색 영역을 한번 빼면 초록색 영역의 합을 구할 수 있다. for (int i = 1; i N >> M; cin >> h >> w; for (int i = 1; i road[i][j]; } } memset(water, true, sizeof(water)); int..

문제 풀이 구현, 시뮬레이션 문제이다. 원판을 2차원 배열로 생각하고 처리한다. 원판을 회전시킬 때, 끝과 처음이 연결되어 있는걸 주의해야 한다. 원판과 인접한 수를 탐색할 때, BFS로 인접한 수가 현재 수와 같은 원판의 위치를 탐색한다. 탐색의 결과로 수를 지울지, 평균을 구할지를 결정한다. 코드 #include #include #include #include using namespace std; typedef struct { int x; int y; }type; queue bfs; int circles[51][51]; bool visited[51][51]; int move_x[4] = { 0, 0, 1, -1 }; int move_y[4] = { 1, -1, 0, 0 }; int main() { i..

문제 풀이 두 포인터, 문자열 문제이다. 두포인터와 재귀 함수로 해당 문자열이 팰린드롬인지 판별한다. 현재 start와 end에서의 문자가 맞지 않다면 start + 1과 end까지와 start부터 end - 1까지 문자열을 확인하도록 함수를 재귀한다. 이미 문자가 맞지 않은 상태에서, 다시 start와 end의 문자가 맞지 않다면 회문이나 유사회문이 아니다. 코드 #include #include #include using namespace std; // 투 포인터로 양 옆에서 접근하며 팰린드롬을 체크한다. int solution(string current, int start, int end, int in_diff_count) { int diff_count = in_diff_count; while (st..

보호되어 있는 글입니다.