유진's 공부로그

https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 문제 설명 정수배열 array의 i번째 수부터 j번째 수까지 잘라, sub-array를 만든다음 정렬하여 K번째 수를 출력하는 문제. i,j,K는 리스트 형태로 주어지며, commands 배열은 위의 리스트를 포함한 이중 리스트 형태로 주어진다. 문제 접근 및 풀이 여기서 주의할 점은 i번째 수라는 것은 배열의 인덱스 i를 얘기하는 것이 아니라는 점이다. 정말 몇 번째 수냐는 것을 의미하기 때문에 제로 베이스 인덱스인 경우에는 ..

https://programmers.co.kr/learn/courses/30/lessons/42584# 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr 문제 설명 스택을 사용해서 주식 가격이 떨어지지 않은 기간을 기록하는 문제. (자세한 설명은 프로그래머스 페이지 참고 바람) 문제 접근 및 풀이 이는 이전에 풀었던 리트 코드 문제와 매우 유사하다. 다만 리트 코드 문제에서는 증가점을 추적하는 것이라면 여기서는 감소점을 추적한다. 따라서 주식가격이 non-decreasi..

https://leetcode.com/problems/daily-temperatures/ 문제 설명 매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨가 될 때까지 며칠을 더 기다려야 하는지 리스트로 리턴하라. 문제 접근 및 풀이 [1st Try] - 투 포인터 1) 현재를 가리키는 포인터를 left, 미래를 가리키는 포인터를 right으로 설정. 2) 미래의 기온이 현재의 기온보다 높지 않다면 right 포인터를 한 칸 옮긴다. 3) 미래의 온도가 현재의 온도보다 높다면 결과가 되는 리스트에 right과 left의 차이를 append하고, left 포인터를 한 칸 이동, right 포인터를 left의 바로 다음 칸으로 이동시킨다. 4) left가 마지막에서 두번째 원소를 가리킬 때까지 반복한다...

https://leetcode.com/problems/remove-duplicate-letters/ 문제 설명 주어진 문자열에서 중복된 문자를 제외한 후 사전식 순서가 가장 작은 문자열을 리턴하라. (즉, 원래 문자열에서의 문자 순서를 완벽히 무시할 수는 없다는 뜻. 중복조합처럼 자리를 정해주는 식으로 생각하면 좀 더 수월할 듯하다) 문제 접근 및 풀이 [1st try] 1) 중복을 제거한다는 것은, 각 글자가 있을 자리를 정해준다는 것 → 원래 있던 자리를 무시하는 게 아님 2) 사전식 순서로 가장 작은 것을 리턴해야하는 것 → 쉽게 생각하면 가장 작은 글자 앞으로, 가장 큰 글자 뒤로 → 그러나 문제가 되는 점은 원래 문자열에서의 각 글자의 자리는 보존되어야 한다는 점 → 뚜렷한 자료구조는 생각나지 ..

https://leetcode.com/problems/valid-parentheses 문제 설명 괄호로 된 입력값이 올바른지 판별 (기본기 점검으로 좋은 문제) 문제 풀이 접근 1) 각 여는 괄호는 짝이 맞는 닫는 괄호가 있다 2) 닫는 괄호의 순서는 여는 괄호의 순서와 반대로 이루어져야 한다. 가장 마지막에 오는 여는 괄호는 가장 처음에 오는 닫는 괄호와 만나게 되고, 이런 패턴이 계속 반복된다. → 스택으로 접근 (LIFO) → 여는 괄호는 스택에 넣고, 닫는 괄호를 만나면 pop해서 짝이 맞는지 대조하는 방식 → 짝이 맞는지 대조하는 데에 편리한 자료구조는 딕셔너리 문제 풀이 class Solution: def isValid(self, s: str) -> bool: parentheses = { "(..

이진 탐색 (Binary Search) 이진탐색은 배열의 중앙값(median)을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 대략 반으로 줄여가며 재귀적으로 진행하는 알고리즘이다(물론 반복으로도 구현 가능하다). 정렬된 배열에서의 탐색에 적합한 알고리즘이다(연결리스트에서는 부적합함. 가운데 지점을 빠르게 찾을 수 없기 때문이다). 시간복잡도는 $O(\log_2{n})$ 으로 빠른 수행시간을 보여준다. 이진 탐색 알고리즘 1) 재귀 구현 2) 반복 구현 투 포인터를 어떻게 활용하느냐의 차이로 투 포인터의 응용이라고 볼 수도 있을 듯하다. 이진 탐색 in Python bisect 모듈에 구현이 되어 있으며, bisect_left를 사용하면 된다. 원래는 정렬된 ..

경사하강법을 얘기하기 전에 최적화란 개념에 대해 먼저 짚고 넘어갈 필요가 있다. 최적화는 간단하게 말해서 고등학교때 배우는 함수의 극대 극소지점을 찾는 것이다 (그래서 우리가 그렇게 미친 듯이 미분해서 0이 되는 지점을 찾는 문제를 풀었던 것). 즉 함수를 최소화 하거나 최대화하는 것을 의미한다. 이때의 함수를 우리는 목적함수라고 부른다. 머신러닝/딥러닝에서는 이 목적함수를 최적화시킴으로써 학습을 진행하게 된다. 그러니, 어떤 목적함수를 지정할지, 어떤 방식으로 최소화 혹은 최대화되는 지점을 찾을 것인지가 매우 중요할 것이다. Ex) A가 B사의 블루투스 헤드폰을 사려고 하는 경우 이때 A는 블루투스 헤드폰을 비싼 돈을 주고 사고싶어하진 않을 것이다. 배송비를 아끼려고 용산 전자상가까지 걸어간다든지, 혹..

https://leetcode.com/problems/sort-list Sort List - 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 - task: 연결리스트 sort - 제약조건: 시간복잡도 O(nlogn), 공간복잡도 O(1) - 고려해야할 사항: 연결리스트로 주어진다는 점, 시간복잡도가 O(nlogn)이라는 점 - 접근방법 1) 제약조건을 고려했을 때 안정적으로 O(nlogn)의 시간을 보장하는 병합정렬을 활용하자. 2) 병합정렬은 중간 지점을 파악하..

삽입정렬 삽입정렬이란 정렬되어 있는 앞 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복하며 정렬하는 알고리즘이다. 1) 삽입정렬 과정 초기 상태는 첫번째 원소를 정렬이 되어있다고 가정하고 시작함. 이후, 정렬된 부분 바로 뒷원소(a)와 정렬된 부분의 모든 원소를 비교하며 a의 제자리를 찾아 넣어줌. 예를 들어, 아래 그림에서의 2를 보면 1,3,5,8의 정렬된 부분 리스트와 비교를 시작하여 1보다 크고 3보다 작으므로 1과 3 사이에 삽입해주고, 탐색을 마친다. 2) 삽입정렬 알고리즘 이중 반복문 구조를 가진 알고리즘 1. 배열의 길이만큼 반복 2. key = 삽입할 원소 3. j는 배열의 오른쪽에서 왼쪽으로 이동한다. 4. 삽입할 원소를 정렬된 부분의 원소와 하나씩 비교하면서 한 칸씩 밀어냄..

앙상블 앙상블은 쉽게 말하면 여러 분류기의 결과를 하나의 결과로 합치는 것이다. 대부분의 경우 앙상블의 결과가 단일 모델보다 예측 결과가 우수하지만, 항상 그렇다고 보장하지는 않는다. 캐글이나 데이콘에서 정형 데이터 챌린지의 경우 대부분 XGBoost, LGBM과 같은 부스팅 알고리즘을 쓰는데, 이 또한 앙상블 기법 중 하나이다. 앙상블의 종류로는 크게 Voting, Bagging, Boosting이 있고, Stacking 또한 종종 사용된다. 보팅(Voting) 보팅은 일반적으로 서로 다른 알고리즘 기반의 모델을 (예를 들면, knn과 logistic regression, decision tree와 같은 식으로 말이다) 같은 트레인 셋으로 학습시킨 결과를 결합한다. 보팅은 크게 하드 보팅(hard vo..