무더운 여름이 지나고 선선한 날씨의 가을도 벌써 절반이 지나갔다. 이제 곧 중국발 미세먼지가 한반도 하늘에 뿌려질 것이다. 어렸을 때는 공기가 안 좋아서 마스크를 쓰고 다닐 것이라고 상상도 못했지만 최근 몇 해부터는 어느덧 일상이 되어버렸다. 미세먼지에 대한 전 국민의 관심이 높다 보니 이맘때쯤 되면 공기 청정기나 필터가 불티나듯이 팔린다. 나 역시 2년 전 모 회사의 차량용 공기 청정기를 구입해서 달고 다닌 적이 있었다. 공기 청정기에는 오염도에 따라 적색과 녹색으로 표시하는 기능이 있었는데 1년 전 구입한 미세먼지 측정기로 테스트한 결과 1도 효과가 없었음을 알게 되었다. 광고에서는 초미세먼지를 10분 안에 정화한다고 시험 성적서까지 올리며 입 아프게 광고했으나, 뉴스나 여러 사용 후기에서도 나오듯이..

완전 탐색에는 순열, 부분 집합, 조합이 있으며, 이번 문제는 9개의 숫자중 7개의 숫자를 선택해서 모두 더한 값이 100이 되는 경우의 수를 찾는 문제다. 입력값은 아래와 같다. 20 7 23 19 10 15 25 8 13 이번 문제는 재귀 함수를 이용하여 모든 경우의 수를 찾는 기본 문제로, 순열을 이용하면 쉽게 풀 수 있다. 순열이란, n개의 아이템 중에서 r개를 선택하여 순서대로 나열하는 것으로 완전 탐색 기법에 해당한다. #include int finish = 0; int minimum[9]; void show (int number) { int total = 0; insertsort(); for (int i = 0; i < number; i++) { printf("%d\n", minimum[i]..

별것 아닌거 가지고 상당히 오랜시간 삽질했다. 이번 문제는 다익스트라 알고리즘 기본 문제이며, 입력 값에 신경을 써야 하는 문제다. 이 문제의 입력값은 아래와 같다. 5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5 코드를 보며 이번 문제에 대해 분석해보자. #include #define MAX 1001 #define INFI 999999999 // 출발지서 각 도시간 최소 비용 int D[MAX]; // 방문기록 int Visited[MAX]; int Map[MAX][MAX]; void Dijkstra (int maxV, int startV, int destV) { // 최소 거리를 INFI로 초기화 for (int i = 1; i w) { Map[s..

DFS 심화 문제로 쉽게 풀 수 있다. 테스트에 사용된 입력값은 아래와 같다. 2 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 5 9 5 7 6 8 6 9 6 10 10 1 5 5 워낙 쉬운 문제라 딱히 주의해야 할 점은 없다. 테스트 케이스가 있으므로 케이스마다 결과 값을 저장하는 변수를 0으로 초기화하고 맵을 초기화하면 된다. #include #define MAX 50 int Map[MAX][MAX]; void DFS(int x, int y, int maxX, int maxY) { // 방문 표시 Map[y][x] = 0; // 왼, 오, 위, 아 체크 int dirX[] = {-1, 1, 0, 0}; int dirY[] = {0, 0, -1..

이번 문제는 BFS를 응용한 길찾기 문제에 대해 알아보자. 보통 미로 찾기 문제를 풀 때 BFS를 사용하는 이유는 DFS의 경우 도착지에 도달하지 못하는 경우, 무한 루프에 빠지지만 BFS는 큐의 아이템이 모두 빠져나가면 루프를 종료하기 때문에 도착 여부를 체크 할 수 있기 때문이다. #include #define MAX 101 #define INFI 999999 int Map[MAX][MAX]; typedef struct Queue { int x; int y; int s; } Queue; Queue Q[INFI]; int front = -1, rear = -1; void DFS (int maxY, int maxX) { // 왼, 오, 위, 아 int directX[] = {-1, 1, 0, 0}; in..

5년 전 회사에 입사한지 1년째 되는 날 그동안 모은 돈으로 쉐보레 대리점에 가서 일시불로 현금 박치기 (??) 한 아베오 수동 해치백. 차에 대해 1도 몰랐던 초짜가 조금씩 차덕후가 되는 과정을 블로그에 정리해보려고 한다. 첫 게시글로 어떤 게 좋을까 하다가 이제는 취미가 되어버린 셀프 세차 과정에 대해 적어보려고 한다. 1. 용인 워시홀릭 세차장 소개 수도권 지역의 셀프 세차 마니아들이라면 한 번쯤은 들어봤을 그곳. 용인 워시홀릭 세차장은 동네에 흔하디흔한 셀프 세차장과는 거리가 좀 멀다. 일단 입구에 들어서면 폼건 및 하부 세차가 가능한 11개의 세차 베이와 수십대가 한꺼번에 드라잉과 왁싱을 할 수 있으며 마치 클럽을 연상하는 미러볼과 신나는 음악이 나오는 대형 드라잉 존, 다양한 디테일링 물품과 ..

바로 이어서 BFS로 풀어보자. BFS로 쉽게 풀 수 있었다. 코드는 아래와 같다. #include #define MAX 25 #define INFI 999999 int Map[MAX][MAX]; int SizeStorage[MAX * MAX]; typedef struct Queue { int x; int y; } Queue; Queue Q[INFI]; int front = -1, rear = -1; int BFS (int x, int y, int limit) { // 왼, 오, 위, 아 방향 계산 int sumSize = 1; int directX[] = {-1, 1, 0, 0}; int directY[] = {0, 0, -1, 1}; // 시작 지점 추가 rear++; Q[rear].x = x; Q[..

이번에는 DFS / BFS 심화 문제를 풀어보도록 하자. 이 문제는 DFS와 BFS 두 가지 방법 모두 가능하며 이번 글에서는 DFS로 풀어보았다. 다음 글에서 동일한 문제를 BFS로 풀어보도록 하겠다. 이번 문제는 2차원 배열에서 이동 가능한 경로를 찾기 위해 상, 하, 좌, 우 모든 방향을 살펴 보는것이 핵심이다. 코드를 살펴보자. #include #define MAX 25 int Map[MAX][MAX]; int SizeStorage[MAX * MAX]; int DFS (int x, int y, int limit, int size) { // 왼, 오, 위, 아 방향 계산 int sumSize = size; int directX[] = {-1, 1, 0, 0}; int directY[] = {0, 0..