알고리즘/백준

문제 풀이 누적 합 문제이다. 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..

보호되어 있는 글입니다.

문제 풀이 정렬, 스위핑 문제이다. 현재 긋고 있는 선의 시작을 start, 끝을 end라고 하자. 선을 긋고 있을 때, 어떤 상황에서 다음 선을 한번에 그을 수 있을까? 만약 다음으로 그을 선의 시작이 end보다 작다면 그 선분은 한번에 그을 수 있다. 그리고 해당 선분의 끝이 end보다 크다면 해당 선분의 끝까지 한번에 그을 수 있다. 다음으로 그을 선의 시작이 end보다 크다면 그 선분은 한번에 그을 수 없으므로, 끊어서 그려야 한다. 선을 끊었다면, 다음으로 그을 선이 새로운 start와 end를 가진다. 코드 #include #include #include using namespace std; vector lines; int main() { ios_base::sync_with_stdio(0); ..

문제 풀이 백트래킹을 이용한, 구현, 시뮬레이션, 완전 탐색 문제이다. 궁수 3명을 배치하는데는 백트래킹을 사용한다. 배치를 완료하면 게임을 시작한다. 턴마다 적이 아래로 이동하는 것 보다, 궁수가 위로 이동하는 것이 더 간단하다. 각 궁수가 공격할 3명의 적을 탐색한다. 판을 하나하나 검사하면서 적일 경우 현재 궁수와의 거리를 측정한다. 현재까지 검색한 궁수와의 최소 거리보다 현재 측정한 거리가 더 가깝다면 타겟을 변경한다. 같다면 타겟들의 y값을 비교하여 더 작은 y값을 가진 타겟을 선택한다. 선택된 적은 중복되면 안 되므로 set에 저장된다. 선택된 타겟들을 공격하고 현재까지 처치한 적을 갱신한다. 궁수줄을 한 칸 위로 이동한다. 코드 #include #include #include #include..

문제 풀이 구현 문제다. 경사로를 놓을 수 없는 경우는 다음과 같다. 이전 칸과의 높이차가 2 이상인 경우 경사로를 놓을 칸의 높이가 서로 일치하지 않는 경우 경사로를 놓을 칸에 이미 경사로가 설치된 경우 경사로를 놓았을 때, 길의 범위를 벗어난 경우 문제의 답의 최댓값은 2 * N이다. 현재 검사하는 행 또는 열이 위의 4가지중 하나의 경우라면 답을 1차감한다. 코드 #include #include #include #include using namespace std; int nums1[101][101]; int nums2[101][101]; bool block[101][101]; int N, L; int answer; void solution(int nums[][101]) { for (int x = 0..