알고리즘 레콩키스타

문제 접근 기본 BFS에서 평범한 좌표 이동 대신에 수식 계산을 대입한 문제로 생각하자. 기본적인 BFS 문제는 주변 좌표의 값을 탐색하는 문제다. 이번 문제는 좌표 탐색 대신에 수식이 주어졌기 때문에, 수를 vertex로, 수식 계산을 하나의 edge로 생각하며 문제를 풀었다. https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 문제 코드 #include #include #include #include using namespace s..

문제 접근 조건을 잘 확인하자. 문제 자체는 BFS로 최단 거리를 구하는 간단한 문제다. 시작 칸과 도착 칸도 최단 거리에 포함되는지, 입력은 어떤 방식으로 되는지 등의 조건을 잘 확인하기만 하자. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 코드 #include #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); c..

문제 접근 tuple을 쓰자. 3차원 공간 정보를 저장해야 된다. 구조체를 써도 되기는 하지만, 그냥 속 편하게 튜플을 썼다. 익은 토마토를 방문한 토마토로 생각하자. 별도로 visited 배열을 만들지 않고, 익은 토마토를 방문한 토마토로 생각했다. 배열을 굳이 동적 할당하려고 하지 말자. 기본 입력 값과 메모리 제한이 넉넉하다면, 그냥 최대 크기로 만들고, 일부만 사용하고자 했다. https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmic..

문제 접근 정직한 제목, 정직한 풀이 DFS와 BFS 구현하는 문제다. 그래프를 알면 그냥 풀면 된다. https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 코드 #include #include #include #include using namespace std; vector graph; vector visited; void print_DFS(int current_vertex) { visited[curren..

문제 접근 입력을 굳이 2차원 배열로 받을 필요가 없다고 생각했다. 높이 데이터만 갖고, 답을 찾을 수 있기 때문에 입력으로 높이 값만 받았다. 범위를 지정하고, 무조건 성립하는 개념을 찾았다. 우선 가장 낮은 높이와 가장 높은 높이라는 정답이 나올 수 있는 범위를 지정했다. 그 뒤 일단 가장 낮은 높이까지 인벤토리에 넣은 뒤에 한 칸씩 기준을 올렸을 때, 시간 변화량이 양수가 되면 바로 전 높이가 최단 시간, 최대 높이라는 걸 알 수 있었다. 그 이유는 간단하다. 문제의 조건 중 하나가 '집터 아래에 빈 공간이 존재하지 않는다.'이기에, 바로 위 높이의 블록 개수는 지금보다 많을 수 없다. 따라서 현재 높이의 블록 개수만큼 '넣기'를 취소하고, 빈 공간만큼 '꺼내기'를 했을 때의 시간 변화량이 양수라면..

문제 접근 나무들을 정렬한 다음에 가장 높은 나무를 기준으로 자를 높이를 점점 낮춰가자고 생각했다. 나무를 정렬한 뒤, 가장 높은 나무부터 현재 확인하고 있는 나무와 그다음 나무의 높이 차이를 height, 그리고 현재 확인하고 있는 나무가 몇 번째로 높은 나무인지는 width로 두고 M과 비교해 가며 높이를 낮춰갔다. 최악의 케이스를 상정해 봤다. 최대 나무 개수가 100만이고, 하나씩 확인하는 시간 복잡도는 O(n)이니 제한 시간 안에 충분히 동작 가능하다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000..

문제 접근 문제 설명에 나온 개념을 정리했다. 문제에서 말하는 생성자란 무엇인지, 분해합이란 무엇인지, 내 나름대로 간단하게 정리했다. 최악의 케이스를 상정해 봤다. 1부터 최대 입력 값인 100만까지 하나하나 확인해 본다고 하면 시간 복잡도는 O(n)이다. 최악의 경우, 입력이 100만이라고 하더라도 제한 시간 안에 가능하다. 그래도 시간을 더 줄일 수 있는 방법이 있나 생각해 봤다. 최대 입력 값은 100만이다. 각 자릿수의 합이 가질 수 있는 최댓값은 N이 999,999일 때 각 자릿수의 합인 54이다. 따라서 N이 55 이상일 때, N-54 미만의 자연수가 만드는 분해합은 절대 N이 될 수 없다고 판단했다. 최종적으로는 N1과 N-54 중에 큰 값부터 N까지만 확인하도록 해서 시간을 조금이나마 아..

문제 접근 소수의 정의와 에라토스테네스의 체라는 개념이 떠올랐다. 소수의 정의는 1과 자기 자신을 약수로 갖는 수. 에라토스테네스의 체란 작은 수부터 하나씩 확인하며 소수가 아닌 수를 소거해 가며 소수를 찾는 방법. 일단은 에라토스테네스의 체를 찾아보지 않고 구현해보려고 함. 최악의 케이스를 상정해봤다. 수 하나하나에 대해서 소수인지 아닌지 판별하려면 O(n^2)이 걸린다. 입력의 최댓값이 100만이기에, 최악의 경우, 1조 번 연산하게 되기에 단순하게는 풀지 못한다. 결국 에라토스테네스의 체처럼 소수를 찾으려 하지 않고, 소수가 아닌 걸 거르는 방식으로 해결하고자 했다. Just do it! https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M..