개발자 데뷔!

탐색 알고리즘 본문

알고리즘 & 자료구조

탐색 알고리즘

물꼮이 2021. 8. 2. 09:31

 

 

1. 백트래킹 : 경우의수 다 찾아놓고 back(뒤로가기)하며 가지치기

2. 완전탐색 : 일일이 하나씩 다 찾아봄                                     : for문 + 재귀  모든 방법으로 다 시도해보는것 

3. DFS      : 그래프 탐색(그래프 가지 따라 탐색)

 

* 보통 배열 개수가 한정적일 때 → for문사용

   배열개수가 얼마가 될지 모를 때 → 재귀 사용 

 

--------------------------------------------------------------------------------------------------------------------------------

예제) 

 

주사위 7개로 합이 10 이하인 조합 모두 출력하기 

 

???   : 영상 강의 딱 2시간 째에 답 나옴

 

 

#include<iostream>
using namespace std;

int n = 3;						// 주사위 3개로 나올 수 있는 최소값
char vect[10];

void run(int lev, int sum)
{
    if (sum > 10) return;		// 합이 10 이상이면 그냥 중단 (백트래킹 중 하나)

	// 한 line 출력
    if (lev == n) {				// lev = 세주사위의합, 즉, 합이 n이 되는 경우
        int i = 0;
        for (i = 0; i < n - 1; i++) {
            cout << vect[i] << " + ";
        }
        cout << vect[i];
        cout << " = " << sum;
        cout << endl;
        return;
    }

    for (int i = 1; i <= 6; i++) {	// 주사위에 숫자종류 6개
        vect[lev] = '0' + i;		// 배열을 char로 선언했기 때문에, 숫자값 표현해주는 장치
        run(lev + 1, sum + i);		// 재귀 point!!!
    }

}

int main()
{
    run(0, 0);
    

    return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------예제2)

 

카드 5개중 4개 뽑아서 조합 다 만들기 

 

#include<iostream>
using namespace std;

int nums[5] = { 11, 5, 7, 4, 9 };
int path[10];

void run(int lev)
{
    if (lev >= 2 && path[lev - 2] + path[lev - 1] >= 15) return;		// 1.  백트래킹 하는 방법 1

    if (lev == 4) {
        for (int i = 0; i < lev; i++) {
            cout << path[i] << " ";
        }
        //cout << endl;
        cout << "\n";
        return;
    }

    for (int i = 0; i < 5; i++) {
        //if (lev >= 1 && path[lev - 1] + nums[i] >= 15) continue;		// // 2.  백트래킹 하는 방법 2
        path[lev] = nums[i];
        run(lev + 1);
        path[lev] = 0; //옵션
    }
}


int main()
{
    run(0);
    

    return 0;
}

 

7개 중 3개 뽑아서 조합 구현 _ no 재귀.ver )

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> v = { 4, 5, 1, 7, 9, 2, 6 };

int main()
{
    for (int a = 0; a < v.size(); a++) {
        for (int b = a + 1; b < v.size(); b++) {
            for (int c = b + 1; c < v.size(); c++) {
                cout << v[a] << v[b] << v[c] << endl;
            }
        }
    }

    return 0;
}

 

7개 중 3개 뽑아서 조합 구현 _ 재귀.ver )

 

#include <iostream>
#include <vector>
using namespace std;

vector<int> v = { 4, 5, 1, 7, 9, 2, 6 };
char path[10];

void run(int lev, int start)
{
    if (lev == 3) {
        cout << path << endl;
        return;
    }

    for (int i = start; i < v.size(); i++) {
        path[lev] = v[i] + '0';
        run(lev + 1, i + 1);
    }
}

int main()
{
    run(0, 0);

    return 0;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

 

설계 법)

 

PS(Problem Solving) :

 이해 → 설계 → 구현 → 디버깅

 

예제) 제일앞에 배열 한칸 추가 

 

??????? 이 아래 코드 답 확인 해보기 : 강의영상 3시간 3분 가량 !!! 

 

절차식 설계 ) 마치 like todo list

//연습문제
int main() {
	char arr[10] = { 0 };
	int cnt = 0;
	int add;
	cin >> arr - '0';

	//1
	while (arr[cnt] != '\0') {
		cnt++;
	}
	add = arr[0] + arr[cnt - 1];
	for (int i = cnt; i >= 0; i--) {
		arr[i] = arr[i - 1];
		if (i == 0)
			arr[i] = add;
	}
	for (int i = 0; i < 10; i++) {
		cout << arr[i];
	}
	return 0;
}
// 답 확인 ????

 

세부설계) 

// 설계 연습
int main() {
	int arr[4][6] = { {5,8,3,2,6,5},{1,0,0,0,0,0},{2,0,0,0,0,0},{6,0,0,0,0,0} };
	// 중괄호 안씌우고 그냥 숫자 쭉 나열해도 알아서 짜름
	int i = 1;
	int j = 1;
	for (i = 1; i < 4; i++) {
		for (j = 1; j < 6; j++) {
			if (arr[i - 1][j] < arr[i][j - 1])
				arr[i][j] = arr[i - 1][j] + 3;
			else
				arr[i][j] = arr[i][j - 1] + 3;
		}
	}
	cout << arr[i-1][j-1];
	return 0;
}

 

 

재귀호출 설계) 

* 설계 시 반드시 트리형태 ** 먼저 그리기  _ branch, level, 바닥조건, 가지치기 조건.... 먼저 전부 결정하고 그다음 구현 

 

 

???? 제발 다시 이해해보기 ㅠㅠ

#include<iostream>
using namespace std;

char path[10];
char ch;
int used[100];

int abs(int v)
{
    if (v < 0) return -v;
    return v;
}

void run(int lev)
{
    if (lev >= 2 && abs(path[lev - 2] - path[lev - 1]) <= 1) return;

    if (ch - 'A' + 1 == lev) {
        cout << path << endl;
        return;
    }

    for (char c = 'A'; c <= ch; c++) {
        if (used[c] == 1) continue;
        used[c] = 1;
        path[lev] = c;
        run(lev + 1);
        used[c] = 0;
    }
}

int main()
{
    cin >> ch;

    run(0);

    return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------

 

DAT) Direct Address Table

 

https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture9.pdf

DAT관련 해외 문헌 사이트 참고 **!!!!!

 

 

*  문자종류 별 개표 수 

#include <iostream>
using namespace std;
int main()
{
	char vect[] = "ABAAAABAAAA";
	int dat[100] = { 0 };
	for (int i = 0; vect[i]; i++) {			//vect[i]하면 배열값 모두 출력함 !!!!!
		int idx = vect[i];			//문자열의 값을 INDEX로 받아 사용하는 DAT
		dat[idx]++;
	}
	for (int i = 0; i < 100; i++) {
		if (dat[i] == 0) continue;
		cout << (char)(i) << " " << dat[i] << endl;
	}
	return 0;
}

 

 

---------------------------------------------------------------------------------------------------------------------------------

예제) 

 

문제)

[역량테스트]
제가 네 문제,
1번다짜시면 바로 2번으로 넘어가요, 빠르게 해서 4번까지 다 풀어주시면 됩니다.
제한시간
==========
* 문자열입력 (string 써도 무방), 대신 set, map, unorderd_map STL 금지!
* set, map, unordered_map은 나중에 배울건데, 미리 쓰지마세요 지금 사용 금지
[1] 입력받은 문자열에서 알파벳 별 몇개있는지 출력 (정답 안보고 다시 짜보기)
[2] 입력받은 문자열에서 가장 많이 등장하는 알파벳이 무엇이고, 몇개 등장했는지 출력
(단, 가장 많이 등장하는 문자열은 하나만 존재하게끔 입력이 주어짐)
[3] 네 문자열 입력받고, 전체에서 딱 3번 등장하는 알파벳들이 뭐 가 있는지
찾아서 출력하기
[4] 숫자 10개 입력받고, 가장 많이 등장하는 숫자부터 순서대로 출력하기
(같은 개수라면 큰수부터 출력한다)
ex) 1 4 1 1 1 1 5 8 9 5 ------->  1 5 9 8 4

 

풀이)    미완성!!!  3번 마무리 + 4번 풀기

//DAT 연습 

//1번
/*
int main() {
	string str;
	cin >> str;
	char max;
	int cnt[100] = { 0 };
	for (int i = 0; str[i]; i++) {	//문자열 처음부터 끝까지.
		int idx = str[i];
		cnt[idx]++;
	}

	//1번
	for (int i = 0; i < 100; i++) {
		if (cnt[i] == 0) continue;
		cout << char(i) << ":" <<cnt[i]<< "개" << endl;
	}
	//2번 가장 많이 등장한 알파벳
	max = char(0);
	for (int i = 0; i < 100; i++) {
		if (cnt[i] > cnt[max])
			max = i;
	}
	cout << "가장많이 등장한 알파벳=" << char(max) << ":" <<cnt[max]<< "번" << endl;

	return 0;
}*/

int main() {
	//3번
	string a, b, c, d;
	cin >> a >> b >> c >> d;
	int cnt[100] = { 0 };
	for (int i = 0; a[i]; i++) {
		int idx = a[i];
		cnt[idx] ++;
	}
	for (int i = 0; i < 100; i++) {
		if (cnt[i] == 3)
			cout<<char(i)<<endl;
	}
	return 0;
}

 

모범답안 )  ???몇번인지 모름

 

#include <iostream>
using namespace std;
int main()
{
	char vect[] = "ABAAAABAAAA";
	int dat[100] = { 0 };
	int maxi = 0;
	char ch = ' ';
	for (int i = 0; vect[i]; i++) {
		dat[vect[i]]++;
		if (dat[vect[i]] > maxi) {
			maxi = dat[vect[i]];
			ch = vect[i];
		}
	}
	cout << maxi;
	cout << ch;
	return 0;
}

 

 

-----------------------------------------------------------------------------------------------------------------------------------

 

Direct )

* 위, 아래, 왼쪽, 오른쪽  좌표 관련 !!! 

 

기본코드 )

#include <iostream>
using namespace std;
int main()
{
	int map[4][5] = {
		1, 0, 1, 2, 1,
		3, 1, 1, 1, 2,
		1, 1, 0, 1, 0,
		0, 0, 0, 0, 1,
	};
	//위, 아래, 왼쪽 , 오른쪽 합
	//조금 복잡한 방향					// {y좌표,x좌표}
	int directY[4] = { -1, 0, 1, 0 };   // 아래{-1,0} , 위{1,0}
	int directX[4] = { 0, 1, 0, -1 };	//오른쪽{0,1} ,왼쪽{0,-1} 
	
	int direct[4][2] = { -1, 0, 1, 0, 0, 1, 0, -1 };		//전부 다 한꺼번에 쓴 것 
	int y = 1;
	int x = 1;
	
	int sum = 0;
	for (int t = 0; t < 4; t++) {
		int ny = y + direct[t][0];			//열 0 으로 고정 즉, y축만 변화
		int nx = x + direct[t][1];			//열 1 로 고정 즉, x축만 변화
		if (ny < 0 || nx < 0 || ny >= 4 || nx >= 5) continue;	// 정해진 map벗어나면 실행 안함
		sum += map[ny][nx];									//사방의 합 구하기
	}
	cout << sum;
	return 0;
}

--------------------------------------------------------------------------------------------------------------------------------

 

문제)

장기말
0.03MB

1] 입력받은 좌표의 대각선의 곱 출력하기

2] 좌표 6개 입력받고 각 좌표를 기준으로 위아래 왼쪽 오른쪽의 합의 6개중, MAX값 출력하기

3] 입력받은 좌표의 장기'마' 의 방향으로 각 방향에 있는 숫자 값중 MAX값 찾아 출력하기

 

 

??????

정답)

 

 

 

 

 

 

 

 

 

 

 

 

Direct  복습)

 

문제)

#include <iostream>
using namespace std;

int map[5][6] = {
    1, 0, 2, 1, 2, 1,
    -1, 0, 1, 1, 2, 2,
    3, 3, 1, 2, 3, 4,
    5, 5, 5 ,3, 1, 2,
    1, 2, 3, 4, 0, 0
};

int main()
{
    //세 좌표를 입력받고
    //다섯 곳의 합을 구하는데
    //세 곳중 MAX값 출력


    return 0;
}

 

내풀이)        풀다맘 !!!!!!!!!!!!!!!! 정리 !!!!!!!!!!!!!!!!!!1 2중배열로 해서 괜히 더 헷갈림 

#include <iostream>
using namespace std;

int map[5][6] = {
	1, 0, 2, 1, 2, 1,
	-1, 0, 1, 1, 2, 2,
	3, 3, 1, 2, 3, 4,
	5, 5, 5 ,3, 1, 2,
	1, 2, 3, 4, 0, 0
};

int main()
{	
	int direct[5][2] = { {0,0},{1,-1},{1,1},{-1,1},{-1,-1} };
	int input[3][2];
	int sum;
	//세 좌표를 입력받고
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 2; j++) {
			cin >> input[i][j];
		}
	}
	//다섯 곳의 합을 구하는데
	for (int i = 0; i < 3; i++) {
		int y = input[i][0];
		int x = input[i][1];
		for (int t = 0; t < 5; t++) {
			int yy = direct[t][0];
			int xx = direct[t][1];
			map[x+xx][xx]
			map[i][]direct[t][0];	//y좌표
			direct[t][1];	//x좌표
		}
	}
	//세 곳중 MAX값 출력


	return 0;
}

 

정답코드)

#include <iostream>
using namespace std;

int map[5][6] = {
    1, 0, 2, 1, 2, 1,
    -1, 0, 1, 1, 2, 2,
    3, 3, 1, 2, 3, 4,
    5, 5, 5 ,3, 1, 2,
    1, 2, 3, 4, 0, 0
};

int directY[5] = { -1, -1, 1, 1, 0 };
int directX[5] = { -1, 1, -1, 1, 0 };

int getNum(int y, int x)
{
    int sum = 0;
    for (int t = 0; t < 5; t++) {
        int ny = y + directY[t];
        int nx = x + directX[t];
        if (ny < 0 || nx < 0 || ny >= 5 || nx >= 6) continue;
        sum += map[ny][nx];
    }
    return sum;
}

int main()
{
    //세 좌표를 입력받고
    //다섯 곳의 합을 구하는데
    //세 곳중 MAX값 출력

    int maxi = -21e8; //-21억
    for (int t = 0; t<3; t++) {
        int y, x;
        cin >> y >> x;

        int ret = getNum(y, x);        
        if (maxi < ret) maxi = ret;

    }
    cout << maxi;

    return 0;
}

 

 

 

___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

 

 

응용 문제 재귀 + Direct)

문제)

#include <iostream>
using namespace std;

int map[3][4] = {
    1, 2, 3, 4,
    5,4, -1, -2,
    -3, 0, 1, 2
};

int n = 3;

int main()
{
    //n 곳을 선택
    //같은 좌표 중복 선택 불가
    //3배, 2배, 1배 가중치 값 존재
    //합의 최댓값과 최솟값 둘다 출력하기


    return 0;
}

 

내풀이)

 

 

정답코드)

#include <iostream>
using namespace std;

int map[3][4] = {
    1, 2, 3, 4,
    5,4, -1, -2,
    -3, 0, 1, 2
};

int n = 3;
int used[3][4];

int maxi = -21e8;
int mini = 21e8;

void run(int lev, int sum)
{
    if (lev == n) {

        if (sum > maxi) maxi = sum;
        if (sum < mini) mini = sum;

        return;
    }

    for (int y = 0; y < 3; y++) {
        for (int x = 0; x < 4; x++) {
            if (used[y][x] == 1) continue;
            used[y][x] = 1;
            run(lev + 1, sum + (n - lev) * map[y][x]);
            used[y][x] = 0;
        }
    }

}

int main()
{
    //n 곳을 선택
    //같은 좌표 중복 선택 불가
    //3배, 2배, 1배 가중치 값 존재
    //합의 최댓값과 최솟값 둘다 출력하기

    run(0, 0);

    cout << maxi << endl;
    cout << mini << endl;

    return 0;
}

 

 

---------------------------------------------------------------------------------------------------------------------------------

문제)

 

정답)

#include <iostream>
using namespace std;

int w;
int h;
int map[10][10];
int mini = 21e8;
int used[10];

void run(int lev, int sum)
{
    if (lev == h) {
        if (sum < mini) mini = sum;

        if (sum == -9) {
            int d = 1;
        }
        return;
    }

    for (int i = 0; i < w; i++) {
        if (used[i] == 1) continue;
        used[i] = 1;
        run(lev + 1, sum + map[lev][i]);
        used[i] = 0;
    }

}

int main()
{
    freopen_s(new FILE *, "Text.txt", "r", stdin);
    cin >> h >> w;

    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            cin >> map[y][x];
        }
    }
    run(0, 0);
    cout << mini;

    return 0;
}

'알고리즘 & 자료구조' 카테고리의 다른 글

재귀  (0) 2021.08.08
'알고리즘 & 자료구조' Related Articles more