오늘의 문제 알고리즘 문제를 풀다보면 영어로 수학 용어를 알 필요를 종종 느끼게 된다. Arithmetic subsequences 는 등차수열이다. 이 문제에서는 nums 라는 배열에서 부분 등차 수열의 개수를 찾아야 하는데, 등차 수열은 적어도 세 개의 요소를 가지고 있으며, 연속하는 두 요소 사이의 차이가 동일하다는 것을 의미한다. 각 요소에 대한 defaultdict 초기화 배열의 각 요소에 대해, 특정 공차로 끝나는 부분 수열의 개수를 저장할 defaultdict을 생성한다. subsequences = [defaultdict(int) for _ in nums] total_count = 0 * defaultdict 를 사용하는 이유 - 존재하지 않는 키 처리 이 문제를 풀 때에는 공차( diff =..
오늘 오랜만에 아메리카노를 마셨더니 잠이 안들어서 어쩔 수 없이 일어났다. 알고리즘을 풀면 졸려질까 싶은 생각에 리트 코드를 열었는데, 오히려 더 쌩쌩해졌다. 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++은 런타임 에러가 나지 않을 수도 ..
링크: https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제: 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는..
💬 문제 (leetcode.com/problems/cheapest-flights-within-k-stops/) There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w. Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1. 💬 코드 class Solution:..
💬 문제 (leetcode.com/problems/employee-importance/) You are given a data structure of employee information, which includes the employee's unique id, their importance value and their direct subordinates' id. For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like..
