https://leetcode.com/problems/median-of-two-sorted-arrays/두 개의 정렬된 List 합쳤을 때 중앙값을 구하는 문제이다. 단, 문제에서 O(log(m+n)) 시간 내에 풀이하라고 주어졌다. 1. Merge Sort 알고리즘처럼 하나씩 대소비교를 하여 정렬하는 풀이 시간복잡도 : O(m+n)Runtime : 90 msMemory : 16.8MBclass Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: n = len(nums1) m = len(nums2) t = (n+m) # length of the merge..
Algorithm (PS)
https://leetcode.com/problems/sort-list 말그대로 배열을 정렬하는 문제이다. 그런데 이제 배열이 링크드 리스트 자료구조로 만들어 져 있는 상태인 ! 버블 소트같은거 밖에 생각못하다가 mergesort 로 풀어야 문제에서 조건으로 준 O(1) 공간 복잡도에 O(nlogn) 시간복잡도로 풀 수 있다. 기본 merge sort 라면 공간 복잡도가 2n 이 되었겠지만, 여기서는 링크드리스트의 특성을 이용하여 O(1) 으로 풀 수 있다. (대박..) LinkedList에서 중간 값(node) 를 구하는 로직이다. 낮은 값은 항상 한칸, 하나 더 큰 값은 항상 두칸씩 이동하다가 null 값을 만나면 순회를 멈추게 된다. 이렇게 하면서 중간값을 구하게 된다. LinkedList 문제에서..
https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이 (1차 시도)from collections import deque def solution(bridge_length, weight, truck_weights): answer = 0 queue = deque([0] * bridge_length) while queue and truck_weights: # popleft 시도 queue..
https://leetcode.com/problems/all-possible-full-binary-trees/모든 가능한 이진 트리의 경우의 수를 구하는 문제이다. 이진 트리의 노드 수가 N이라고 주어 질때 N=1, N=3, N=5 의 경우를 그림으로 표현하면 아래와 같다. 그림에서 파악할 수 있듯이, N=5 의 경우 N=3이 root.left 와 root.right 에서 반복이 되고 있다. 즉, N=5에서는 N=3, N=1 에서 구한 값을 재활용하여 사용할 수 있다. N=7 또한 N=1, N=3, N=5의 값을 다시 활용하여 모든 경우의 수를 구할 수 있다. 또한 이진 트리는 root가 반드시 0, 그리고 자식 노드들이 항상 둘다 0 이거나 null 이므로, 노드의 개수는 항상 홀수라는 특성이 있다. ..
https://leetcode.com/problems/top-k-frequent-words/Given an array of strings words and an integer k, return the k most frequent strings.Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.Example 1:Input: words = ["i","love","leetcode","i","love","coding"], k = 2Output: ["i","love"]Explanation: "i" and "love" are..
class Solution: def climbStairs(self, n: int) -> int: dp = [0] * (n+3) dp[1] = 1 dp[2] = 2 dp[3] = 3 if n
https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr def rotate(arr): m = len(arr) result = [[0] * m for _ in range(m)] # 회전 결과 담기 for i in range(m): for j in range(m): result[j][m - i -1] = arr[i][j] return result def check(n, arr): fo..
기업 코딩테스트 준비를 위해 코드트리 플랫폼에서 2달동안 공부해봤습니다. 퇴근 후, 혹은 주말 시간을 이용하여 한주에 2~3문제 정도를 풀이하는 것을 목표로 하였습니다. 단계별 커리큘럼 학습 지난 달에 이어서 꾸준히 '알고리즘 입문' 레벨을 풀이하였습니다. Simulation / Backtracking / DFS / BFS 위주로 공부했습니다. 프로그래머스의 구현 문제들 보다 조금 더 실제 기업 코딩테스트에 나올만한 수준으로 대비가 가능한 것 같아서 좋았습니다. 꾸준히 풀이한 결과 프로그래머스의 구현 LV2정도는 무난하게 풀 수 있게 되었습니다. 기업별 기출문제 제가 개인적으로 목표하는 기업의 기출문제가 코드트리에 있어서 유용했습니다. 코드트리 유저들의 응시후기도 볼 수 있어서 준비에 도움이 되는 것 같..
