백준 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. ...
LeetCode 86. Partition List 🗓️ Daily LeetCoding Challenge August, Day 15 Linked List Linked List 문제는 처음 풀어본다. 간접적으로 array을 이용해서 비슷하게는 풀어봤지만, linked list 자체를 사용해본건 이번이 처음. 문제에서 떡하니 ListNode가 정의되어 있어서 많이 당황했다. 어떻게 값을 불러오는지조차 망설이게 되었다. 예제를 이용해서 실제 linked list을 그리면서 풀어보니까 이해가 잘 되었다. 나의 풀이 Linked List는 목걸이처럼 각 Node가 꼬리에 꼬리를 무는 형태의 자료구조이다. array와는 다르게 index가 정해지지 않고 각 Node는 val 데이터 필드와 다음 Node를 가리키는 *next 링크 필드를 가진다. 비엔나소시지처럼 줄줄이 엮어내면 linked list가 완성된다. index 고려를 크게 하지 않아도 돼서 비교적 간단하게 풀어낼 수 있다. ...