전체 탐색 알고리즘 소개

전체 탐색 알고리즘이란?

모든 패턴을 조사하거나 그러한 것을 필요로 하는 문제

예시

친구가 i 명 있습니다. 각 i번째의 친구는 first[i], second[i] 이렇게 두 가지 흥미로운 주제를 가지고 있습니다.

각 친구들은 흥미로운 주제가 같아야만 이야기를 합니다.

친구들이 가장 많이 즐기기 위해서는 어떻게 해야 하는가?

이럴 경우 방법은 두 가지가 있습니다.

첫 번째로는 모든 i번째의 친구들의 취미를 하나씩 비교해서 패턴을 찾고 

최대로 흥미를 가지게 만드는 것입니다.

---

int ans = 0;

for(int i=0;i<first.length;i++){

int f_cnt = 0; // 처음 비교할 대상의 first[i]와 같은 경우

int s_cnt = 0; // 처음 비교할 대상의 second[i]와 같은 경우 

for(int j=0;j<first.length;j++){

if(first[i].equals(first[j])) f_cnt++;

if(first[i].equals(second[j])) f_cnt++;

if(second[i].equals(first[j])) s_cnt++;

if(second[i].equals(second[j])) s_cnt++;

}

// 비교해서 큰 값은 출력할 대상입니다. >> 취미가 가장 많이 겹치는 것임

ans = Math.max(ans,f_cnt);

ans = Math.max(ans,s_cnt);

}

return ans;

---

이 중 for문을 사용하지 않고 연관배열을 사용해서 작업할 수 있습니다.

0번째 사람이 갖는 0번째 취미1(first[0]) , 0번째 취미2 (second[0])을 초기화하면서 이를 그 값을 증가시켜 정리하면 됩니다.

구조는 다음과 같습니다.

---

public class 전체_탐색1 {

public static void main(String[] args) {

// TODO Auto-generated method stub

String[] hobby1 = { "축구", "축구", "헬스", "야구" };

String[] hobby2 = { "농구", "야구", "농구", "축구" };

int wholeAnswer = wholeEntityCheck(hobby1, hobby2);

System.out.println(wholeAnswer);

}

public static int wholeEntityCheck(String[] first, String[] second) {

int f_cnt = 0;

int s_cnt = 0;

HashMap<String, Integer> map = new HashMap<String, Integer>();

// first[i] 관심 영역 모두 0으로 초기화

// second[i] 관심 영역 모두 0으로 초기화

for (int i = 0; i < first.length; i++) {

map.put(first[i], 0);

map.put(second[i], 0);

}

// 관심사가 하나 씩은 있으니까 가져와서 1씩 증가시킴

// 만약에 second[j]와 first[j]가 같을 경우 (같은 관심사) 관심사가 +1

for (int j = 0; j < first.length; j++) {

map.put(first[j], map.get(first[j]) + 1);

map.put(second[j], map.get(second[j]) + 1);

}

int ans = 0;

for (String key : map.keySet()) {

ans = Math.max(ans, map.get(key));

}

return ans;

}

}

---

이러한 구조입니다.

HashMap에서 first[i] , second[i] (흥미 있는 주제)를 Key로하고 처음에는 모두 0으로 초기화합니다.

---

for (int i = 0; i < first.length; i++) {

map.put(first[i], 0);

map.put(second[i], 0);

}

---

그리고 i번째 사람마다 first[i] , second[i]는 하나씩 증가시켜야 하므로 (기본적으로 한 개씩 총 두 개의 흥미주제를 가지고 있음) 

아래와 같이 코드를 작성해준다.

---

for (int j = 0; j < first.length; j++) {

map.put(first[j], map.get(first[j]) + 1);

map.put(second[j], map.get(second[j]) + 1);

}

---

여기서 중요한 것은 Key를 취미로 가졌기 때문에 취미가 같을 경우 해당 취미를 갖는 Key의 value가 증가하는 것입니다.

따라서 좋아하는 취미가 많을 수록 Key가 중첩되어 해당 Value가 계속해서 증가할 것입니다. 

마지막으로 HashMap의 Key중 가장 많이 투표된 취미를 뽑아야하므로 다음과 같이 코드를 정리합니다.

---

int ans = 0;

for (String key : map.keySet()) {

ans = Math.max(ans, map.get(key));

}

return ans;

---

HashMap.keySet()에서 (취미 생활들) Key로 접근하여 HashMap내의 Key에 대한 Value를 가지고 온다.

가지고 온 값은 ans와 계속해서 비교하면서 최대 값을 찾아 냅니다.

이렇게 하면 최종 결과로 가장 취미 생활로 많은 값이 나오게 됩니다.

감사합니다.