알고리즘

문제 풀이 정렬, 스위핑 문제이다. 현재 긋고 있는 선의 시작을 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..

문제 풀이 구현, 시뮬레이션, 너비 우선 탐색, 그래프 탐색 문제이다. 터질 뿌요들을 탐색할 때, BFS를 이용한다. 상하좌우로 같은 색상의 뿌요들을 탐색했을 때, BFS 탐색의 횟수가 4이상이라면 터질 뿌요들이다. 이 것을 queue explode의 형태로 저장한다. explode 큐를 꺼내면서 뿌요를 터트린다. 터진 뿌요에 해당하는 필드는 '.'으로 값이 변한다. 밑에 빈 공간이 있는 뿌요들은 아래로 떨어져야 한다. 아랫줄부터 검사하면서 현재 검사하는 타일의 값이 '.'일 경우, 해당 타일 바로 위에 있는 뿌요 타일과 값을 바꾼다. 다시 explode 큐를 채우기 위해 BFS로 터질 뿌요들을 탐색하고, explode가 모두 비워질 때까지 반복한다. 코드 #include #include #include..

문제 풀이 구현, 시뮬레이션 문제이다. 파이어볼을 표현할 구조체를 하나 만든다. (fireball) 문제의 방을 vector room[51][51]의 형태로 만들어서 (x, y)의 방의 파이어볼의 데이터를 알 수 있도록 하였다. 각각의 방을 조사하며 파이어볼을 이동시킨다. 이동 시, 속도가 방의 크기보다 클 수 있기 때문에 mod연산을 사용하며 범위를 초과했다면 범위에 맞게 조절해준다. 이동 후의 방에 파이어볼이 합쳐졌다면, (x, y)에서의 vector를 이용해서 합친다. 코드 #include #include using namespace std; typedef struct { int mass; int speed; int direction; }fireball; // 이동 방향 8가지 int dx[8] =..

문제 풀이 누적 합과 이분 탐색을 사용한다. 피자 조각의 최대 개수는 1000개 이므로 O(N * N)으로 해도 시간초과가 발생하지 않는다. A와 B에서 얻을 수 있는 모든 피자 조각을 계산한다. 피자 조각은 끝과 처음이 연결될 수 있으므로 유의해서 더해야 한다. A에서 얻을 수 있는 피자 조각을 기준으로 P와의 차이만큼의 B의 피자 조각의 수를 이분 탐색으로 구한다. 코드 #include #include #include using namespace std; vector A; vector A_parts; vector B; vector B_parts; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int P; int m,..

문제 풀이 이분 탐색을 사용한다. 모두 탑승하는데 소모되는 최소 시간을 이분 탐색한다. 최소 시간은 0, 최대 시간은 (N X 최장 운행 시간)으로 설정했다. mid값을 이용해서 해당 시간 동안 몇 명이 탑승할 수 있는 확인한다. 여기서 주의할 점이 0초 때, 이미 기구에 탑승하고 있기 때문에 현재 탑승한 아이의 수를 미리 N으로 세팅해줘야 한다. 이분 탐색으로 얻은 최소시간은, 마지막 아이가 놀이기구에 탑승한 시점의 시간이다. (최소시간 - 1)분 때, 총 몇 명이 탈 수 있는지 확인한다. (최소시간 % 탑승시간 == 0)이라면 해당 놀이기구에는 최소시간 시점에 탑승할 수 있는 놀이기구이다. 인덱스가 작은 순으로 해당 검사를 하면서 총 탑승한 아이의 수가 N과 같을 때의 인덱스를 출력한다. 코드 #in..

문제 풀이 이분 탐색을 사용한다. 가장 긴 증가하는 부분 수열을 찾는 문제이다. 내가 알던 방법은 O(N * N)으로 전체 계산 수가 16억이 되어 시간 초과가 발생한다. 입력이 들어오면서 검사를 실시한다. 입력값이 현재 수열의 가장 끝에 있는 수를 초과한 경우 바로 수열에 추가된다. 이하일 경우엔 이분 탐색을 실시한다. 현재 수열에서 입력값 이하의 값 중, 최댓값을 입력값으로 교체한다. 이렇게 하면 시간 복잡도가 O(N * logN)으로 줄어든다. 코드 #include #include #include using namespace std; vector nums; // 기존에 입력된 nums에서 num 이하의 값중에서 // 최댓값을 num으로 교체한다. void binary_input(int num) { ..

문제 풀이 이분 탐색을 사용한다. 입력으로 주어지는 수가 상당히 크기 때문에 이분 탐색으로 해결해야 한다. 검사받는 총 시간(mid)을 이분 탐색한다. mid 시간에 심사할 수 있는 사람의 수와 M을 비교하여 범위를 조절한다. mid 시간에 각 심사대에서 심사가능한 사람의 수는 (mid / 소요시간)이다. 코드 #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, M; cin >> N >> M; for (int i = 0; i > temp; nums.push_..

문제 풀이 이분 탐색을 사용한다. 점프할 최소거리(mid)를 이분 탐색한다. 돌 사이의 거리가 mid 미만이라면 돌을 삭제한다. 삭제한 돌의 수와 m을 비교하여 start와 end를 조절한다. 코드 #include #include #include using namespace std; vector nums; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int d, n, m; cin >> d >> n >> m; for (int i = 0; i > temp; nums.push_back(temp); } // 시작 지점과 끝 지점을 추가 nums.push_back(0); nums..