FandPROG FandPROG

문제 설명몇칸이 비어있는 9x9 격자판이 주어졌을 때 해당 스도쿠를 채워 출력하는 문제.  이 문제는 백트래킹을 사용하여 빈칸을 채워 스도쿠 퍼즐을 해결 할 수 있다. 각 행(row), 각 열(column)에 대해 숫자가 사용되었는지를 체크해주다. 또, 각 3x3 서브그리드에 대해 숫자가 사용되었는지도 체크해주어야한다. 다음 3가지를 각각 체크하며 비어있는 칸을 백트래킹을 이용하여 풀면 된다.소스코드더보기#include #include #include using namespace std;int chs[10][10], chg[10][10];int chsq[10][10];int m_sq[10][10];int ch = 0;vector > emp;int sqnumjudge(int x, int y){ if (0 ..

문제 설명N-Queen 문제는 N × N 체스판 위에 N개의 퀸을 서로 공격하지 못하게 배치하는 방법의 수를 구하는 문제이다. (이때 1 ≤ N ≤ 15)  N-Queen문제는 N범위가 작기 때문에 충분히 백트래킹을 통해 풀 수 있다. 하지만 퀸을 놓을 때 마다 상, 하, 좌, 우, 대각선 2방향을 모두 검사하려면 시간이 방대하게 걸린다. 따라서 이를 한번에 체크를 통해 확인해주어야 한다. 간단하게 현재 탐색중인 행 또는 열을 재귀함수의 인자로 하고, 체크배열 3개를 통해 대각성, 열을 체크해가며 탐색하면된다.-기저 사례: 현재 탐색중인 행(row)이 N보다 크거나 같다면, 모든 퀸을 성공적으로 배치한 것이므로 cnt를 1 증가시킨다.-백트래킹 과정- 행(row) x에서 가능한 모든 열(column) i..

문제 설명2차원 좌표가 n개 주어졌을 때 이를 이용해만들 수 있는 직사각형의 개수를 구하는 문제.(이때 1 ≤ n ≤ 5,000) n범위가 5,000으로 작기 때문에 O(n * nlongn)의 방법으로도 풀 수 있다. 주어진 모든 점으로 만들 수 있는 모든 대각선에 대해 set자료구조를 통해 나머지 두 점의 존재유무를 확인하면 되는 간단한 문제이다.소스코드더보기#include #include #include #include using namespace std;int n;vector > vec;set > st;int main(){ int i, j; scanf("%d", &n); for(i=0;i

문제 설명  여러 회의의 시작시간과 끝나는 시간이 주어졌을 때, 최대 사용할 수 있는 회의의 최대 개수를 출력한다. (총 회의의 수 ≤ 100,000)  이 문제는 그리디 알고리즘을 이용하여 풀 수 있다. 회의들의 시작 시간과 종료 시간을 바탕으로 최대한 많은 회의를 진행할 수있게 하려면 끝나는 시간을 기준으로 정렬하는 것이 좋다. 이를 알기 위해서는 입출력 예를 수직선에 그려보는 것이 좋다. 입력 예111 43 50 65 73 85 96 108 118 122 1312 14를 수직선상에 나타내면더보기0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |----|   |----| |------|       |----|   |--------|       |------|         |------..

1. 탐욕 알고리즘(Greedy - 그리디) 그리디 알고리즘은 매번 항상 최적의 답안을 선택하여 적절한 해를 구해내는 알고리즘입니다. 탐욕 알고리즘은 과정이 직관적이기 때문에 일반적으로 시간 복잡도가 낮고, 구현이 단순하여 빠르게 동작합니다. 이때문에  이해하기 쉽고 구현하기 간단합니다. 하지만 그리디 알고리즘이 항상 최적해를 보장하지 않는 경우가 많습니다.2. 탐욕 알고리즘의 특성(1) 탐욕적인 선택조건(Greedy Choice Property) : 각 단계에서 내리는 최적의 선택이 결국 전체 문제에 대한 최적해로 이어질 수 있어야 합니다. (2) 최적 부분 구조(Optimal property) : 문제의 최적해가 부분 문제들의 최적해로 구성될 수 있어야 합니다. 3. 동전 문제를 통한 탐욕 알고리즘의..

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 효율적으로 찾는 알고리즘입니다. 배열의 중간 요소와 목표 값을 비교하여, 목표 값이 더 작으면 왼쪽 절반, 더 크면 오른쪽 절반을 선택하여 검색을 반복합니다. 최악의 경우 시간 복잡도는 O(log⁡n)입니다.「이진 탐색의 동작 과정」1. 분할 과정 (Divide)우선 알아야할점은 배열은 항상 정렬 되어있어야 한다는 것입니다. 첫번째 분할과정에서는 현재 배열의 중간 원소를 선택합니다. 그 후 중간 원소와 찾고자 하는 값을 비교합니다.-IF 찾고자 하는 값이 중간 요소보다 작으면 : 배열에서 중간 원소의 왼쪽 절반을 선택합니다.-IF 찾고자 하는 값이 중간 요소보다 크면 : 배열에서 중간 원소의 오른쪽 절반을 선택합니다.12345 위 배열에..

퀵 정렬(Quick Sort)은 분할 정복 알고리즘의 일종으로, 배열을 임의의 기준으로 두 부분으로 나눈 후 각각을 재귀적으로 정렬하는 방식입니다. 평균 시간 복잡도는 O(nlog⁡n)이며, 최악의 경우 O(n ² )이 될 수 있습니다. 일반적으로 빠른 수행 속도로 널리 사용되는 정렬입니다.「퀵 정렬의 동작 과정」1. 분할 과정 (Divide) 퀵 정렬의 첫번째 단계에서는 "피벗(pivot)"을 정해 이를 통해 구간을 나누는 과정입니. 피벗은 일반적으로 배열의 첫 번째 원소, 마지막 원소, 또는 중앙값을 선택합니다. 피벗을 정한뒤, 배열의 원소들을 피벗을 기준으로 두 부분으로 나눕니다. 피벗보다 작은 원소들은 피벗의 왼쪽에, 피벗보다 큰 원소들은 피벗의 오른쪽에 위치하도록 합니다. -처음 주어진 배열[3..

병합정렬(Merge-sort)은 퀵 정렬(Quick Sort)와 같이 분할정복 알고리즘을 이용한 정렬 알고리즘중 하나입니다. 선택정렬같은 O(N²)의 느린 정렬 알고리즘과 다르게 병합정렬은 시간복잡도 O(NlogN)의 빠른 정렬 알고리즘입니다.「병합 정렬의 동작 과정」1. 분할 과정 (Divide)  병합정렬의 첫 번째 단계인 분할과정에서는 배열을 가능한 한 작게 나눕니다. 이 단계에서는 배열을 중간을 기준으로 두 개의 하위 배열로 분할합니다. 이 과정을 배열에 원소가 하나가 될때까지 계속 반복하면 됩니다. -처음 주어진 배열 ↓ [38, 27, 43, 3, 9, 82, 10] -첫번째 분할 ↓ [38, 27, 43], [3, 9, 82, 10] -두번째 분할  [38, 27], [43],  [3, 9]..