Bruteforce

백준 1837번 문제 바로가기 간만에 풀어보기로 한 몸풀기 문제! 그런데 너무 오랜만에 코딩했더니 감이 다 떨어졌다ㅜㅜㅋㅋ 4트만에 성공했다. 허허 다음학기 파이썬 강의 하나 듣는데, 꾸준히 풀어가는 습관 들여야겠90000 KEY IDEA 조건 처리에 대한 센스가 돋보이는 문제였다. 특히 pq 전체를 다 돌지 않고, k까지만 돌린다는게 핵심! 나머지 경우에 대해서는 “GOOD” 판정만 내리면 되니까 굳이 소수를 찾이 않아도 된다. (=탐색 시간을 아낄 수 있다.) Solution 일단 모두 탐색하는 방법을 사용해서 통과할 수 있는지 확인해보았다. Python 같은 경우 big integer에 대해서 걱정할 필요도 없어서 C++과 달리 mod 함수를 따로 만들 필요는 없다. ...

백준 20529번 문제 바로가기 문제 상황 이해 한때 핫했던 MBTI를 활용한 재밌는 문제. MBTI 글자 하나가 다를때마다 거리를 1로 잡고 그 거리의 총합을 구하는 문제다. Keypoint 비둘기집의 원리을 활용해서 if문 작성해주기 MBTI의 총 가짓수가 2^4=16종류이기 때문에 33명 이상이면 반드시 3명은 같은 MBTI를 가진다 def distance(case): temp = 0 for i in range(3): for j in range(4): if case[i%3][j] != case[(i+1)%3][j]: temp += 1 return temp n_test = int(input()) for i in range(n_test): n_friend = int(input()) mbti = input().split() if n_friend >= 33: print(0) else: min_distance = 20 for x in range(n_friend-2): for y in range(x+1, n_friend-1): for z in range(y+1, n_friend): d = distance([mbti[x], mbti[y], mbti[z]]) if d < min_distance: min_distance = d print(min_distance) #include <iostream> #include <string> using namespace std; int distance(string a, string b, string c){ int temp = 0; for (int i=0; i<4; i++){ if (a[i] != b[i]){ temp++; } if (b[i] != c[i]){ temp++; } if (c[i] != a[i]){ temp++; } } return temp; } int main() { int n_test, n_friend; string name; string mbti[100000]; cin >> n_test; for (int i=0; i<n_test; i++){ int d, min_distance = 20; cin >> n_friend; for (int j=0; j<n_friend; j++){ cin >> name; mbti[j] = name; } if (n_friend >= 33){ cout << 0 << endl; } else { for (int x=0; x<n_friend-2; x++){ for (int y=x+1; y<n_friend-1; y++){ for (int z=y+1; z<n_friend; z++){ d = distance(mbti[x], mbti[y], mbti[z]); if (d < min_distance){ min_distance = d; } } } } cout << min_distance << endl; } } }

백준 1759번 문제 바로가기 문제에 대한 첫 인상 단순히 모든 조합을 구하라고 했으면 실버 문제에 해당하겠지만, 자음/모음 갯수를 고려해주는 것이 은근 까다로워서 골드 등급을 부여해준 듯 하다. 문제를 읽고 나서 두 가지 방법이 생각났다. 1) permutation 라이브러리를 사용한다. 2) DFS로 풀어낸다. 두 경우 모두 모든 경우를 커버해야하기 때문에 결국엔 bruteforce로 풀어내야 한다. 라이브러리의 사용법을 이미 알고 있어서 간단히 이용할 수 있는 permutation 라이브러리를 이용했다. Python 풀이 import itertools # input l,c=map(int, input().split()) chars=list(map(str, input().split())) # examples words=itertools.combinations(sorted(chars), l) # 조건 확인 def check(word): vowels = ['a','e','i','o','u'] n = 0 # 모음 갯수 m = 0 # 자음 갯수 for w in word: if w in vowels: n += 1 else: m += 1 return (n, m) answer = [] for word in words: nm = check(word) if nm[0]>=1 and nm[1]>=2: answer.append(''.join(word)) # output for ans in sorted(answer): print(ans) C++ 풀이 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { // input int l, c; cin >> l >> c; vector<string> chars(c); for (int i=0; i<c; i++){ cin >> chars[i]; } sort(chars.begin(), chars.end()); vector<string> answer; // permutation vector<bool> vec(chars.size()-l, false); vec.insert(vec.end(), l, true); string vowels = "aeiou"; do { string temp = ""; int n=0, m=0; // n 모음갯수, m 자음갯수 for (int i=0; i<chars.size(); i++){ if (vec[i]){ temp += chars[i]; if (vowels.find(chars[i]) != string::npos){ n++; } else{ m++; } } } if (n>=1 && m>=2){ answer.push_back(temp); } } while (next_permutation(vec.begin(), vec.end())); // output sort(answer.begin(), answer.end()); for (string ans: answer){ cout << ans << endl; } return 0; } 풀어내고 보니까 Python이 확실히 코드가 깔끔하긴 하다. 그렇지만 메모리 사용량과 시간을 보면 C++의 압승 ...

백준 1251번 문제 바로가기 bruteforce 간단한 길이 가장 쉬운 길이라고, 이래저래 고민해보았지만 결국 bruteforce가 가장 간단한 방법이었다. 문자열을 나누는 기준점을 i j 기준으로 하여 이중 for문을 돌려 새로운 문자열을 만들어낼 수 있다. 알파벳 순서로 앞서는지는 < comparison operator을 통해서 간단하게 확인할 수 있다. 다만 주의할 점은 reverse(begin, end) 함수는 begin ‘다음’ 위치부터 end ‘포함’ 위치까지 index을 뒤집는다. 즉, $ begin < index <= end $ 가 되는 셈! 따라서 이를 고려해서 index에 1을 더해주어 맞춰주어야 한다. ...

LeetCode 1. Two Sum bruteforce Easiest way to solve this problem is bruteforcing. For each pair of integers, check whether their sum equals to target. If so, return their indexes. Time Complexity = $ O(n^2) $ class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> ans; for (int i=0; i<nums.size(); i++){ for (int j=i+1; j<nums.size(); j++){ if ((nums[i] + nums[j]) == target){ ans = {i, j}; } } } return ans; } }; hash In order to reduce Runtime, implementing hash table will work. Searching in hash table is much faster than doing in array. ...