백준 1064번 문제 바로가기 내 풀이 삼각형의 각 변의 길이를 구하고, 이를 통해서 만들어낸 평행사변형의 둘레의 (최댓값-최솟값)을 구하는 문제. 예제를 이상없이 모두 통과했지만, 실제로 제출해보니 틀렸습니다 에러가 발생해서 많이 당황했다. 크게 바꾼 부분은 다음 두가지다. 세 점이 한 직선상에 있는지 파악하기 세 점이 한 직선상에 있다면 평행사변형을 만들지 못하므로 -1을 출력해야 한다. 제2코사인 법칙을 이용해도 되고, CCW을 이용해서 풀어도 된다. 계산의 정확도 소숫점 자릿수를 고려해줘야하는 문제였다. 오차 범위가 $ < 10^{-9} $ 이므로 double을 사용하고 cout으로 출력하기 전에 cout.precision(20)와 같이 정확도를 우선 지정해주어야 한다. 자꾸만 틀렸던 이유가 바로 여기에 있었다… #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { double a1, a2, b1, b2, c1, c2; cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2; double x, y, z; x = sqrt(pow(b2-a2, 2) + pow(b1-a1, 2)); y = sqrt(pow(c2-b2, 2) + pow(c1-b1, 2)); z = sqrt(pow(a2-c2, 2) + pow(a1-c1, 2)); vector<double> vec = {2*(x+y), 2*(y+z), 2*(z+x)}; // using CCW if three dots are on a single line if ((b1-a1)*(c2-a2) == (c1-a1)*(b2-a2)){ cout << -1; return 0; } double ans; ans = *max_element(vec.begin(), vec.end()) - *min_element(vec.begin(), vec.end()); cout.precision(20); cout << ans; return 0; }

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

백준 18110번 문제 바로가기 solved.ac 실제 solved.ac에 있는 문제들의 난이도 반영 알고리즘을 따와서 만든 문제. 절사평균이라는 개념은 처음 들었는데 통계학적으로 outlier들을 제거할 수 있는 유용한 방법인 것 같다. 문제는 주어진 조건대로만 구현하면 쉽게 풀렸는데, 다만 index 범위의 설정과, (n=0)같은 예외처리에 신경써야했던 문제다. 내 풀이 #include <iostream> #include <vector> #include <cmath> #include <algorithm> using namespace std; int main() { int n, rate; vector<int> rates; cin >> n; // 난이도 의견의 수 if (n == 0){ cout << 0; return 0; } for (int i=0; i<n; i++){ cin >> rate; rates.push_back(rate); } sort(rates.begin(), rates.end()); int cut = round(n*0.15); float average = 0; for (int i=cut; i<n-cut; i++){ average += rates[i]; } average /= (n - 2*cut); cout << round(average); return 0; }

프로그래머스 덧칠하기 문제 바로가기 문제에 대한 첫인상 처음 이 문제를 접했을 때 많이 당황했다. 최적의 경우를 어떻게 구하라는 건지… 특히 n과 m에 따른 관계를 파악하는게 어려워서 횟수를 기준으로 bruteforce해봐야하는지도 고민해보았다. 그런데 여러 예시들을 스스로 만들어보면서 n 변수는 솔직히 필요 없는 정보라는 점을 알게 되었다. 문제를 쉽게 바꾸면 section을 m길이 천막으로 모두 가리기 위한 천막의 갯수 정도로 생각해볼 수 있다. 따라서 section의 각 요소에 대해서 m 길이로 페인트를 칠하고, 칠해진 마지막 index을 업데이트 해나가는 논리를 따르면 greedy 방식으로 문제를 해결할 수 있다. ...

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. ...