오늘의 문제 알고리즘 문제를 풀다보면 영어로 수학 용어를 알 필요를 종종 느끼게 된다. Arithmetic subsequences 는 등차수열이다. 이 문제에서는 nums 라는 배열에서 부분 등차 수열의 개수를 찾아야 하는데, 등차 수열은 적어도 세 개의 요소를 가지고 있으며, 연속하는 두 요소 사이의 차이가 동일하다는 것을 의미한다. 각 요소에 대한 defaultdict 초기화 배열의 각 요소에 대해, 특정 공차로 끝나는 부분 수열의 개수를 저장할 defaultdict을 생성한다. subsequences = [defaultdict(int) for _ in nums] total_count = 0 * defaultdict 를 사용하는 이유 - 존재하지 않는 키 처리 이 문제를 풀 때에는 공차( diff =..
오늘의 문제 링크 오늘의 문제는 Job Scheduling 을 하면서, Maximum Profit 을 찾는 문제였다. 얼핏 봤을 때는 지난번에 풀었던 Interval Scheduling Algorithm 이 생각났다. Interval Scheduling Algorithm 은 일반적으로 각 간격과 관련된 이익을 고려하지 않고 겹치지 않는 간격(또는 작업)의 수를 최대화하는 것이었다. 하지만 이번 문제에서는 총 이익을 극대화해야 하므로 복잡도가 올라갔고, 다른 방법으로 접근해야 했다. 1. 종료 시간을 기준으로 정렬 Interval Scheduling Algorithm 이랑 비슷한 부분은 종료 시간을 기준으로 정렬하고 시작한다는 것 종료 시간을 기준으로 정렬하는 것은 현재 직업 이후에 선택할 수 있는 다음 ..
목적 - 주어진 시간 간격(인터벌)의 집합에서, 서로 겹치지 않는 최대 수의 인터벌을 선택하는 것 cf. 각 인터벌은 시작 시간과 종료 시간으로 정의된다 사용 - 효율적인 자원 배분과 일정 관리에 사용된다. - 서로 겹치지 않는 최대 수의 활동이나 작업을 스케줄링 하는데 유용하다. 예시 프로세스 및 자원 스케줄링 컴퓨터 시스템의 한정된 자원을 여러 프로세스들 사이에서 효율적을 분배 자원이 충돌 없이 사용되도록 하고 시스템 효율성을 최대화 회의실 또는 강의실 예약 시스템 한정된 공간을 여러 그룹이나 이벤트에 할당할 때 최대한 많은 이벤트를 수용할 수 있도록 항공편 스케줄링 제한된 게이트와 활주로를 가지고 최대한 많은 항공편을 운영할 수 있도록 def interval_scheduling(intervals :..
오늘 오랜만에 아메리카노를 마셨더니 잠이 안들어서 어쩔 수 없이 일어났다. 알고리즘을 풀면 졸려질까 싶은 생각에 리트 코드를 열었는데, 오히려 더 쌩쌩해졌다. 1. 문제 Given an integer x, return true if x is palindrome integer. An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not. 팰린드롬 수는 101, 121, 1221과 같이 뒤집어도 같은 수다. 처음에 문제를 보자마자 str로 변환하고, 뒤집은 값과 비교하면 되겠다고 생각했다. 그런데 문제의 예제를 끝까지 읽다보니 Follow up에 Follo..
이제까지는 글을 내가 공부한 걸 정리한다는 느낌으로 썼다. 하지만 면접을 보면서 다른 사람에게 설명하는 것에 미숙하다고 생각하게 됐고, 앞으로는 읽는 사람이 이해할 수 있게 글을 써야겠다고 생각했다. 1. 문제 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is wri..
링크 https://leetcode.com/problems/number-of-matching-subsequences/ Number of Matching Subsequences - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s. A subsequence of a string..
문제 1. Reverse String class Solution { public: void reverseString(vector& s) { reverse(s.begin(), s.end()); } }; vector에는 reverse(start, end) 함수가 있으니까 사용하면 된다. 문제 2. Reverse Integer class Solution { public: int reverse(int x) { string str_x = to_string(x); string rev_str_x; for (int i=str_x.size()-1; i>-1; i--) rev_str_x += str_x[i]; long long res = stoll(rev_str_x); if (x < 0) res *= -1; return ..
생각보다 문제가 빨리 풀려서 카테고리 별로 포스팅을 올리는게 나을 것 같다. 풀리긴 풀리는데 계속 아쉬운 마음이 든다. 파이썬처럼 C++도 C++만의 장점을 살릴 수 있는 방법이 있을 텐데, 파이썬 코드를 C++로 바꾼 것처럼 풀고 있다. 심지어 파이썬이 아니니 파이썬의 장점도 죽는다😂. 근데 풀다보니 C++도 파이썬만큼은 아니지만 꽤 편한 것 같다. 문제 5. Single Number class Solution { public: int singleNumber(vector& nums) { int answer = 0; sort(nums.begin(), nums.end()); for (int i=0; i
문제: https://leetcode.com/problems/contains-duplicate/ Contains Duplicate - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 앞에서 풀었던 문제(정렬된 벡터에서 중복 제거하기)와 유사해서 금방 풀었다. 🔽풀이 1 class Solution { public: bool containsDuplicate(vector& nums) { int before = nums.size(); sort(nums.begin(), n..
저번 글에서 언어는 도구일 뿐이라고 했는데 언어가 도구인 것은 맞다. 하지만 전기톱으로 나무를 베는 것은 쉽지만 커터 칼로 자르면 어려운 것처럼... 파이썬으로 문제를 풀다가 C++로 문제를 푸는게 어려운 건 당연한게 아닐까...? C++이 성능이 더 좋다해도.. vi도 커맨드를 알면 정말 누구보다 편하게 쓸 수 있지만.. 기능을 익히는데 시간이 오래 걸리니까 말이다..(=실력 부족) 문제: https://leetcode.com/problems/rotate-array/ Rotate Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get p..
뭔가 이 문제를 풀어보니까 알고리즘을 푸는데 언어는 문제가 아닌거 같기도 하고... 일단 언어는 문제를 풀기 위한 도구일뿐이고 결국에 핵심 로직은 똑같으니까..🙄? class Solution { public: int maxProfit(vector& prices) { int profit = 0; for (int i = 1; i < prices.size(); i++){ profit += max(prices[i]-prices[i-1], 0); } return profit; } }; 한 번의 거래로 낼 수 있는 최대 이익을 찾는 문제인데 예를 들어서 [7, 1, 5, 3, 6, 4]인 경우, 1일 때 사서 6일 때 팔면 최대 이익을 산출 할 수 있다. 브루트 포스로 하면 c++은 런타임 에러가 나지 않을 수도 ..
C++에서 손을 떼고 Python만 한지 4년차... C++로 코딩테스트를 보게 됐다. 기본 문법만이라도 익숙해져보려고 하지만, 입출력에서 부터 오류가 나고 계속 틀린다😥.. 그래도 할 수 있는 한 계속해서 노력해보겠지만... 떨어지면 명백하게 내 실력 부족인거니까 미련을 갖진 않으려 한다.. 미련 갖고 후회 하기보단 계속 공부를 해야지.. 코딩 테스트에서 자주 나오는 문제를 풀되, 기본 문법에 익숙해져야 하니까 뭘 풀까 고민하다가 LeetCode Top Interview Questions 를 풀기로 했다. 첫번째 문제는 정렬된 배열에서 중복을 제거하는 문제였다. 파이썬으로 풀 때는 정말 보자마자 바로 풀었는데, C++로 풀어보니 레퍼런스도 참고하고 문법을 찾아보다가 한시간이 걸렸다.. class Sol..
