신입부터의 기록

https://leetcode.com/problems/longest-common-prefix/ Longest Common Prefix - 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. 문자열 중 가장 짧은 길이를 찾는다. 2. 모든 문자열을 문자 순서대로 탐색한다. 3. 탐색하며 모든 문자열이 같으면 누적하고, 다르면 바로 리턴한다. 1. 모든 문자열을..

https://leetcode.com/problems/pascals-triangle/ Pascal's Triangle - 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 1 1 1 2 1 1 3 3 1 1 4 6 4 1 2는 윗 줄 2개의 1+1로, 3은 윗 줄 1+2, 2+1로, 4는 윗 ..

https://leetcode.com/problems/two-sum/ Two Sum - 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 정수 목록이 주어졌을 때, 목록 내 두 정수의 합이 목표 값이 되는 경우 그 목록의 인덱스를 반환하는 문제다. [C++] class Solution { public: vector twoSum(vector& nums, int target) { unordered_map cache; for (int i = 0; i < nums.size..

https://leetcode.com/problems/powx-n/ Pow(x, n) - 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 실수d 와 제곱수n 를 받았을 때 pow(d,n)을 구하는 문제다. 단순히 d를 n번 곱셈하는게 제일 쉽겠지만, 그 안에서 반복되는 횟수를 줄여야 한다. 10번 처리할거 5번으로 줄이는 방식으로 2를 나누어 2배수로 처리한다. 더 큰 배수로 처리해도 되지만 예외처리가 그만큼 늘어날 수 있다. 제곱수n은 정수이므로 2로 나누었을 ..

https://leetcode.com/problems/group-anagrams/ Group Anagrams - 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 문자열의 목록이 주어졌을 때, Anagram(원본 문자를 한번 사용으로 재배열해 만든 문자)을 그룹화 해 반환하는 문제다. 주어진 문자열들을 각각 정렬하고 동일한 문자들끼리 모아둔다. (정렬된 문자열을 key로 unordered_map 사용) 그 후에 모아둔 문자열을 2중 벡터에 담아 반환한다. class..

https://leetcode.com/problems/maximum-subarray/ Maximum Subarray - 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 이지인데 난 왜 헤메나;; 정수 목록이 주어졌을 때 합이 최대가 되는 부분 목록의 합을 구하는 문제다. 누적된 합보다 인수가 클 때 다시 누적을 시작한다. 금요일인데 억지로 하고 있어서 그런가... 방법과 로직은 이해가 되는데 서로 연결이 안된다.. 왜 max 함수 내용으로 그것이 구현되는가... ..

https://leetcode.com/problems/search-insert-position/ Search Insert Position - 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 금요일이 고단해 easy 두 문제로 간다. 정렬된 목록과 목표 숫자가 있을 때, 목록에 있다면 index를, 없다면 순서대로 삽입될 index를 리턴한다. class Solution { public: int searchInsert(vector& nums, int target) ..

https://leetcode.com/problems/3sum-closest 3Sum Closest - 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 임의의 정수(-10^3 ~ 10^3) 목록이 주어졌을 때, 3개의 숫자를 더해 주어진 목표 값과 가장 가까운 합을 구하는 문제다. 15. 3Sum 직전에 풀었던 문제(15. 3Sum)는 case를 구하는 문제였으므로 중복을 제거해 연산 수를 줄였지만, 이 문제는 동일한 숫자도 덧셈에 활용될 수 있어 중복 수는 제거..

https://leetcode.com/problems/3sum/ 3Sum - 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 정수의 목록이 주어졌을 때, 3개의 정수를 더했을 경우 0이 되는 목록을 2차원 배열에 담아 반환하는 문제다. 단순히 생각하면 O(N^3)이지만 O(N^2)로 낮추는게 핵심인것 같다. 일단 받은 정수의 목록을 오름차순으로 정렬해놓고, 첫번째 숫자부터 끝까지 반복하며 나머지 목록을 검사한다. case를 반환하는 문제기 때문에 중복들은 전부 건..

https://leetcode.com/problems/climbing-stairs/ Climbing Stairs - 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 정수로 주어진 n개의 계단을 1계단 또는 2계단씩 올라가려고 한다. 몇 가지 방법으로 올라갈 수 있는지 구하는 문제다. 먼저 n개의 계단을 올라갈 수 있는 방법은 2가지가 있다. 첫번째, 1개의 계단을 오르고 N-1계단을 올라가는 방법 두번째, 2개의 계단을 오르고 N-2계단을 올라가는 방법 T(n) ..