완전탐색이란?
모든 경우의 수를 탐색하는 방법이다.
1) 브루트포스 (brute force)
단순히 조건문/반복문등을 사용해 모든 경우의수를 계산하여 답을 구하는 방법, N이 커지는 사용할수 없다.
2) DFS/BFS
완전 탐색의 경우의 DFS/BFS.가 많이 사용된다. 가령 길찾기/ 최단거리 탐색/ 가능한 조합 중 최적의조합을 모든 경우를 탐색하여 찾아내는 경우가 있다.
완전탐색의 경우는 데이터의 개수(N)이 작거나, 또는 임의 답 하나를 선택하거나, 역추적이 가능한경우에 주로 사용된다.
백 트래킹이란?
답을 찾는 도중에 답이 될 수 없다고 판단하면, 되돌아가서 다시 찾아가는 기법
DFS 탐색을 하면 모든경로를 다 탐색한다.
모든 경루를 탐색하기 때문에 불필요한 것같은 경로를 사전에 차단하지 않는다. 그래서 경우수가 줄어들지 않는다.
백트래킹은 완전탐색하는 도중에 탐색에 들어가지 않고 제한조건을 걸어서 특정 조건을 위배가 되는지 안되는지 판단한후에 외배가 되는 경우는 제한하고 탐색한다.
다만 백트래킹 문제를 풀때는 백트래킹인지 DFS 인지 분석해가면서 풀면 시간에 촉박하다. 일단 DFS 먼저 구현을 한 후에 제외시켜야할 조건이 있다면 추가시켜서 백트래킹 문제가 자연스럽게 구현이 되는 것이다.
백트래킹은 당연하게도 DFS/BFS 둘다 구현이 가능하다.
다만 이전 수행으로 돌아가야 하기 떄문에 BFS보다는 DFS가 구현이 더펴한경우가 많아서 주로 DFS를 이용해서 문제를 해결한다.
백트래킹 예시
3x3 행렬 선택 게임으로 예시를 들겠다.
규칙 : 아래와 같은 행렬이 존재 할떄 3개의 수자를 선택하는데, 단 선택한 숫자들과 행과 열은 모두 중복이 되면 안된다.(즉 뽑아내는 숫자의 행과 열이 모두 달라야한다.)
트리로 표현해보면
#include <iostream>
int matrix[3][3] =
{
{2,4,3},
{1,3,7},
{6,5,6}
};
bool check[3] = {};
void dfs(int row, int score)
{
if (row == 3)
{
std::cout << score << std::endl;
return;
}
for (int i = 0; i < 3; i++)
{
if (check[i] == false)
{
check[i] = true;
dfs(row + 1, score + matrix[row][i]);
check[i] = false;
}
}
}
int main()
{
dfs(0, 0);
return 0;
}
JavaScript
복사
Flood Fill (플루드필)
주어진 시작점으로 부터 연결된 영역들을 찾는 알고리즘
다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘
예를 들어 그림판의 채우기 기능, 지뢰찾기에서 특정 셀을 클릭시 주변에 지뢰가 없는 모든 셀을 찾아주는 기능
#include <iostream>
//flood fill
char map[9][10] =
{
"#########",
"#...#...#",
"#...#...#",
"#..#....#",
"###...###",
"#....#..#",
"#...#...#",
"#...#...#",
"#########"
};
void printMap()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
std::cout << map[i][j];
}
std::cout << std::endl;
}
}
void FloodFill(int x, int y)
{
if (map[y][x] == '.')
{
map[y][x] = '@';
FloodFill(x, y + 1);
FloodFill(x - 1, y);
FloodFill(x, y - 1);
FloodFill(x + 1, y);
}
}
int main()
{
printMap();
std::cout << "==========================" << std::endl;
FloodFill(4, 4);
printMap();
return 0;
}
JavaScript
복사
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고,
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,
•
질문할 곳도 없고,
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.
문제는 ‘연습’이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기 또는 카카오톡 상담방: 얌얌코딩 상담방