알고리즘

문제 풀이 백트래킹을 사용한다. 행별로 입력된 숫자, 열별로 입력된 숫자, 블럭 별로 입력된 숫자에 해당하는 배열을 생성하고 관리한다. 스도쿠 칸의 0번째 부터 시작한다. 현재 검사하는 칸을 1씩 증가시켜서 검사한다. 현재 검사하는 칸의 행은 (current / 9)이며, 검사하는 칸의 열은 (current % 9)이다. 검사하는 칸이 0이라면 1부터 9까지의 숫자 중 현재 배열에 입력되지 않은 값으로 설정하고, 다음 칸으로 넘어간다. 검사하는 칸이 0이 아니라면 다음 칸으로 넘어간다. 현재 칸의 검사를 마치면 백트래킹을 실시한다. 코드 #include using namespace std; int ground[9][9]; bool num_vertical[10][9]; // 행 숫자 입력된 것 bool n..

문제 풀이 2중 for문을 사용하면 시간초과가 발생한다. 두 포인터 알고리즘을 사용한다. start에서 end 까지의 합이 S미만이라면 end를 증가한다. 수열의 길이를 늘린다. S이상이라면 start를 증가시켜서 수열의 길이를 줄인다. 코드 #include #include using namespace std; int num[100'002]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(nullptr); int N, S; int sum = 0; int answer = INT_MAX; cin >> N >> S; for (int i = 1; i > num[i]; } int start = 0; int end = 0; while (start

문제 풀이 최소 스패닝 트리 문제로 크루스칼 알고리즘으로 해결하였다. 최소 스패닝 트리는 총 간선의 수가 (정점의 수 - 1)로 이루어져 있다. 문제에서 마을은 2개로 분할하기 때문에 총 간선의 수가 (정점의 수 - 2)로 이루어진다. 그러므로 간선을 선택할 때, 선택한 간선의 수가 (정점의수 - 2)라면 알고리즘을 종료하면 된다. 단, 집이 전체 2개일 경우에는 연결할 필요가 없으니 바로 0을 출력하면 된다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2; int dist; }edge; int parent[100001]; bool compare(const edge e1, const edge e2) { ..

문제 풀이 크루스칼 알고리즘을 이용하였다. 가중치가 작은 순서대로 검사할 수 있도록 간선을 가중치의 오름차순으로 정렬한다. 검사하는 간선이 사이클을 만들지 않다면 간선을 선택한다. 간선이 선택되면 선택된 간선의 노드를 같은 부모로 설정한다. 모든 간선을 검사하거나, 간선이 (총 노드의 수 - 1)만큼 선택되었다면 종료된다. 코드 #include #include #include using namespace std; typedef struct { int v1; int v2; int dist; }edge; int parent[10001]; bool compare(const edge edge1, const edge edge2) { return edge1.dist < edge2.dist; } // v의 최상위 부..

문제 풀이 들어온 수를 하나하나 모두 나누면서 접근하면 시간초과이다. 1000000길이의 bool 배열에 입력으로 들어온 인덱스에 해당하는 배열의 값을 true로 세팅한다. 검사할 값의 배수가 입력으로 들어왔는지 확인한다. 배수가 들어왔다면 answer에 현재 검사하는 값에 해당하는 배열의 값을 1증가시키고, 배수의 값은 1 감소시킨다. 코드 #include #include using namespace std; const int MAX = 1000001; bool num[MAX]; int answer[MAX]; vector num_v; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int N; int maxi = 0; cin >> N; for (int ..

문제 풀이 2중 for문을 돌려서 정답을 찾으면 시간 초과가 발생한다. 두 포인터 알고리즘을 이용한다. 용액의 입력값이 오름차순으로 입력된다. 용액 vector의 양쪽에서 부터 start와 end로 시작하여 검사한다. start가 end의 값을 넘을 때까지 검사하며, start와 end의 합의 절댓값이 현재 answer보다 작다면 갱신한다. start와 end의 합의 부호에 따라 start와 end의 값을 증가하거나 감소시킨다. 코드 #include #include #include using namespace std; int main() { int N; vector v; vector answer; cin >> N; v.resize(N); answer.resize(2); for (int i = 0; i <..

문제 풀이 다각형의 넓이를 구하는 공식으로 대각성분끼리 곱하고 더하면 구할 수 있다. 코드 #include #include #include using namespace std; int main() { int N; long double answer = 0; cin >> N; vector coordinate; coordinate.resize(N); for (int i = 0; i > x >> y; coordinate[i] = make_pair(x, y); } for (int i = 1; i

문제 풀이 위의 식을 구하는 것이 문제의 답이다. 페르마의 소정리에 의해 밑의 식이 성립한다. 즉 b^(-1) (mod X)는 b^(X - 2)이므로, 이 b^(X - 2)만 구하면 답을 구할 수 있다. 문제에서 X가 1,000,000,007의 큰 수 이므로 일반적인 제곱을 하면 범위 초과가 발생하므로 mod연산과 분할 정복을 이용하여 제곱값을 구한다. 코드 #include const int MOD = 1'000'000'007; using namespace std; // a를 b번 곱하고 c로 나눈 값 long long power(long long a, long long b, long long c) { if (b == 0) { return 1; } if (b == 1) { return a % c; } l..

문제 풀이 전체 별이 그려질 공간을 보면 [3100][6200] 정도가 된다. 받은 N값에 따라 별이 그려질 공간을 분할한다. 이 구조의 별을 해당 위치에 그리는 방법으로 해결한다. 코드 #include using namespace std; int N; char ground[3100][6200]; char star[3][6] = { " * ", " * * ", "*****" }; void insertStar(int n, int x, int y) { // 계속 쪼개서 n이 1이라면 별을 입력 if (n == 1) { for (int i = 0; i < 3; ++i) { for (int j = 0; j < 5; ++j) { ground[x + i][y + j] = star[i][j]; } } return; ..

문제 풀이 다익스트라 알고리즘에 경로 추적을 추가한 문제이다. 다익스트라 알고리즘 도중 최단 경로가 갱신되면 노드의 부모 노드를 교체한 방식으로 진행한다. next_node에 최단 경로로 도달하기 위해서는 current_node에서 와야 한다. 코드 #include #include #include #include using namespace std; int n, m; int start_node, end_node; vector graph; int dist[1001][1001]; int parent[1001]; vector path; void dijkstra(int n) { dist[n][n] = 0; parent[n] = n; priority_queue pq; pq.push(make_pair(0, n));..