코딩테스트
[실4] 10845 - 큐
#include #include #include using namespace std; queue q; string res; void Push(int x) { q.push(x); } void Pop() { if (q.empty()) res += to_string(-1) + '\n'; else { res += to_string(q.front()) + '\n'; q.pop(); } } void Size() { res += to_string(q.size()) + '\n'; } void Empty() { res += to_string(q.empty() ? 1 : 0) + '\n'; } void Front() { res += to_string(q.empty() ? -1 : q.front()) + '\n'; } vo..
[실4] 10816 - 숫자 카드 2
#include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; map data; for (int i = 0; i > val; data[val]++; } string s; int m; cin >> m; for (int i = 0; i > val; s += to_string(data[val]); if (i < m - 1) s += ' '; } cout
[C] 이진 탐색 (Binary Search) 알고리즘 개념과 예제
이진 탐색 이진 탐색은 오름차순으로 정렬되어있는 데이터에서 원하는 값(타겟 넘버)의 위치를 찾아내는 알고리즘이다. 여기서 이진(Binary)는 우리가 알고있는 그 이진 코드 (0101001...) 가 아니라 데이터를 반(2개)으로 나누어서 비교하고 찾는 방식이여서 이진 탐색이라고 한다. 이진 탐색의 알고리즘 진행방식은 아래와 같다. 정렬되어있는 데이터의 중간 값을 임의의 값 X로 정함 타겟 넘버의 값과 X를 비교 타겟 넘버의 값이 X보다 크다면, 타겟 넘버는 데이터에서 X보다 우측에 위치해 있으니 반으로 나눈 데이터의 우측에서 1번 과정부터 다시 시작 타겟 넘버의 값이 X보다 작다면, 타겟 넘버는 데이터에서 X보다 좌측에 위치해 있으니 반으로 나눈 데이터의 좌측에서 1번 과정부터 다시 시작 이진 탐색 예..
오목 AI 제작 - MIN_MAX 전략을 통한 필승 수 구현
탐색을 적용시킨 오목 AI를 구현해보고 싶어서 3일동안 AI 제작을 진행하게 됐습니다. 먼저 19*19 바둑판 맵을 다 탐색을 하여 돌의 연결상태를 확인한 후 각 돌의 연결 상황마다 가중치를 부여했습니다. 그 후 Search 함수를 통해 탐색 과정에서 AI끼리 각자 가지치기 방식으로 최적의 수를 두어나갑니다. 탐색 중 상대방이 이기는 경우가 발생 하면 return 하여 가지가 갈라지는 분기점으로 돌아가 재 탐색을 시작합니다. 그렇게 탐색하는 도중 자신의 AI가 이기는 상황이 발생하면 맨 처음 좌표값을 저장한 후 그 이후부터는 모든 상황에 대해 return하여 탐색을 종료시켜 제작하였습니다. 최대 깊이 탐색은 현재 시점으로부터 30수까지 설정해 놓았습니다. 그 이유는 웬만하면 승부가 나는 시점까지 도달하고..
[실4] 2003 - 수들의 합2
#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m, s = 0, e = 0; cin >> n >> m; int* arr = new int[n]; for (int i = 0; i > arr[i]; int sum = 0, res = 0; while (e m) sum -= arr[s++]; else { res++; sum += arr[e++]; } } cout
투 포인터 알고리즘(Two Pointers Algorithm)
1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘이다. 절대 답이 되지 않는 경우는 계산하지 않아 시간을 단축시켜준다. Q. 배열에서 부분 배열의 합이 M이 되는 경우의 수를 구하여라! A1. 가장 쉽고 단순한 방법으로는 이중 for문을 이용해서 모든 경우의 수를 구할 수 있다. 시간 복잡도 O(N^2) A2. 투 포인터 알고리즘을 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 주로 적용되는 문제 유형 - 연속된 수들의 합 - 부분 배열의 합 풀이 방법 1. 포인터 2개가 같은 방향으로 진행해 나아가는 것 2. 포인터 2개가 양끝에서 반대로 진행하는 것 대표 문제 풀이 1 - 백준 [2003] 수들의 합 2 www.acm..
[골4] 1197 - 최소 스패닝 트리
#include #include #include using namespace std; class Edge { public: int node[2]; int dist; Edge(int a, int b, int dist) { node[0] = a; node[1] = b; this->dist = dist; } bool operator> vertex >> edge; for (int i = 0; i > from >> to >> cost; v.push_back(Edge(from, to, cost)); } sort(v.begin(), v.end..
[실1] 2468 - 안전 영역
#include using namespace std; using IntPair = pair; #define MAX 100+1 #define y first #define x second IntPair dir[] { {1, 0}, // 상 {-1, 0}, // 하 {0, -1}, // 좌 {0, 1} // 우 }; int board[MAX][MAX]; bool vis[MAX][MAX]; int n, ans; void Reset() { for (int i = 0; i n) continue; if (!vis[ny][nx] && board[ny][nx] > rain) DFS(ny, nx, rain); } } void Input() { ios_base::sync_with_stdio(false); cin.tie(NU..
[골4] 2580 - 스도쿠
#include #define MAX 9 using namespace std; int map[MAX][MAX]; bool row[MAX][MAX]; bool col[MAX][MAX]; bool square[MAX][MAX]; void Input() { for (int i = 0; i > map[i][j]; auto val = map[i][j]; if (val != 0) { row[i][val] = col[j][val] = true; square[(i / 3) * 3 + (j / 3)][val] = true; } } } } void Print() { for (int i = 0; i < MAX; i++) { for (..
[2] JadenCase 문자열 만들기
#include #include using namespace std; string solution(string s) { string answer = ""; answer+=toupper(s[0]); for(int i=1;i