히더

알고리즘 풀이 시 가장 기본 방법이다. 완전 탐색, 브루트 포스라고도 불리며 이름 그대로 모든 경우를 다 탐색하는 방법이다. 기초 알고리즘 문제나 쉬운 시뮬레이션에서 완전 탐색을 통해 최적 값을 구하는 경우가 많다.그러나 시간이 최대로 돌아간다. 그러하여 난이도가 조금만 올라가도 시간 초과가 걸리는 경우가 대다수이다. 문제마다 다르지만 기본적으로 2중 for문을 통해 모든 경우를 다 체크하는 경우가 많다. 또는 재귀를 통해 모든 경우를 체크한다.2중 for문이면 시간복잡도는 O(N^2)이 되며 N이 100000정도가 되면 시간이 매우 오래 걸린다. 이때, 조건문을 통해 시간을 조금 줄일 수 있지만 좋은 방법은 아니다. 완전 탐색이 무조건 안 좋은 방법은 아니다. 문제에 따라 모든 탐색을 해야하는 경우가 ..

BOJ :: 백준 :: 1103 :: 게임 출처 : https://www.acmicpc.net/problem/1103 #include #include using namespace std; int N, M;int map[51][51], dp[51][51];bool visited[51][51];int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; inline bool check(int i, int j) { return ((i >= 0 && j >= 0 && i < N && j < M) ? true : false); } int dfs(int i, int j) {if (!check(i, j) || map[i][j] == 999) return 0;if (visited[i][j]) {..

BOJ :: 백준 :: 1937 :: 욕심쟁이 판다 출처 : https://www.acmicpc.net/problem/1937 #include #include using namespace std; int N, ans;int map[501][501], dp[501][501];int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; inline bool check(int i, int j) { return ((i >= 0 && j >= 0 && i < N && j < N) ? true : false); } int dfs(int i, int j) {if (dp[i][j]) return dp[i][j];dp[i][j] = 1;for (int d = 0; d < 4; d++) {int n..

BOJ::15683::감시 출처 : https://www.acmicpc.net/problem/15683 #include using namespace std; int N, M, vs, a[8][8], ans,dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, nc[6] = { 0,1,2,2,3,4 }, cc[6][4] = { {},{0},{0,2},{0,1},{0,1,3},{0,1,2,3} };vector v; int cal(int vi, int res) {if (vi == vs) return res;int ta[8][8], tmp = 65; memcpy(ta, a, sizeof(a));auto tp = v[vi];for(int i=0;i= 0 && nx < M&&a[ny][nx] ..

문제를 풀 때 조건 N이 10억이상이 되는 경우가 많다. 이럴 때 그냥 코드를 짜면 시간제한에 걸리거나 메모리 제한으로 틀리는 경우가 많았다. 아직은 공부를 하는 단계라 이러한 경우 명확한 해답을 내지는 못했다. 그러나 이런 경우 배열보다는 다른 자료구조를 사용해서 풀면 좀 더 효율적이었다. vector, list, queue 등 자료구조들의 특징을 좀 더 공부해서 문제의 특성에 맞는 효율적인 자료구조를 짜는 것이문제해결로 가는 지름길인 것 같다. 이러한 자료구조는 프로그램의 시간, 메모리 등을 좌우하는 굉장히 중요한 요소라는 것을 다시 한번 깨달았다. 작성자 : 히더

알고리즘 문제를 풀다 보면 몇가지 케이스에 대해 틀리는 경우가 있다. 이러한 경우 대부분 전반적인 논리가 틀리지 않았으면특별한 케이스, 조건의 최대 값일 때, 최소 값일 때, 범위 제한 등을 고려해야한다. 대부분의 문제에서 예제 케이스로 주는 경우는 이러한 최악의 경우를 주지는 않는다. 그래서 최악의 경우를 대비해 시간, 메모리 등을 고려해야한다. 이때, 직접 최대 케이스를 만들어서 돌려보는 것이 좋다. 예제 케이스가 맞다고 제출하는 것이 아니라 최악의 경우의 케이스를 직접 만들어 돌려본다. input값을 넣기 힘든 숫자의 경우이면 코드로서 케이스를 만들어 돌려보면 된다. 작성자 : 히더

알고리즘을 공부하면서 문제를 읽고 논리를 정리해보는 것이 도움이 되었다. 알고리즘 문제를 푸는 솔루션이 이러한 논리를 코딩화 시킨 것이다. 그래서 문제를 풀 때 프로그램이 돌아가는 순서 즉, 논리의 순서, 단계를 상세히 정리하고 코드를 짜는 것이복잡한 문제일수록 좀 더 빠르게 문제 해결을 할 수 있었다. 특히 복잡하거나 꼬이는 부분의 경우 예제 케이스를 통해 직접 머리로 돌려보면서 검증을 하는 것이 도움이 되었다. 작성자 : 히더

SWEA::2382::미생물 격리 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl #include #include #include using namespace std; struct me {int ii, jj, num, d,ttmp;}; int N, M, K;int dir[5][2] = { {0,0}, {-1,0},{1,0},{0,-1},{0,1} };vector m; int cal(int time, int me_n) {while (time--) {for (int i = 0; i < m.size(); i++) { // movem[i].ii += dir[m[i].d][0];..

SWEA::2383::점심 식사시간 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl #include using namespace std; struct P { int y, x; };int T, t = 1, N, a[10][10], c[10], s[2], ans, pn, ps=0;vector vp,vs[2]; vector q[2]; int cal(int r) {q[0].clear(); q[1].clear();for (int i = 0; i < pn; i++) q[c[i]].push_back(vs[c[i]][i].y);sort(q[0].begin(), q[0].end()); ..

SWEA::1244::최대 상금 출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD #include #include #include using namespace std; int N, K, ans;char tmp[256];string s; void cal(int cnt, int now) {if (cnt == K) {ans = max(ans, stoi(s));return;} for (int i = now; i < s.size(); i++) {for (int j = i; j < s.size(); j++) {if (i == j)continue;if (s[i]