전체 글
-
CTCI | 교집합Algorithm/Linked List 2024. 4. 4. 17:38
두 Linked List의 교집합이 되는 첫번째 노드를 찾아라 두 Linked List가 주어졌을 때, 값이 같은게 아닌, 주소가 같은 노드를 찾아내는 문제이다. 우선 이 LinkedList가 교집합이 없을수도 있고, 두 LinkedList의 길이는 물론 다를것이다. 제일 먼저 떠오르는 방법은, 포인터를 2개 이용하는 방법인데, 첫 리스트의 노드를 outter loop같이 늦게 하나씩 비교하고, 다른 리스트의 노드들을 계속 돌면서 비교하는 방법이다. 하지만, 이 방법은 시간이 많이 쓰인다. N의 노드를 N번 비교해야하기 때문에, O(N^2)만큼의 Time Complexity가 발생한다. Space는 따로 사용하지 않기때문에 O(1) 이다. 우선, 이 breadth force algorithm을 이용해 로..
-
Python BasicMachine Learning/ML Math with Python 2024. 4. 3. 22:59
Basic Operations Python의 Basic한 것들을 다시 상기해보자. Python에서는 변수(Variable)에 정수, 소수, 문자열 등 다양한 값을 넣을 수 있다. # 정수 123 a = 123 # 소수 b = 123.456 # 문자열 c = "hello world!" print()를 사용해 그 값을 콘솔에 표시할 수 있다. a = 123 print(a) 123 print를 할 때, 쉼표를 이용해서 값을 한꺼번에 프린트 할 수 있다. print(a, b, c) 이번엔 연산자를 사용해 여러 연산을 해보자. a = 3 b = 4 # 더하기 c = a + b print("+ :", c) # 빼기 d = a - b print("- :", d) # 곱하기 e = a * b print("* :", e..
-
지도학습 | 결정트리 (Decision Tree)Machine Learning/ML with Python Library 2024. 4. 3. 22:30
Decision Tree 만들기 결정트리(Decision Tree)는 분류와 회귀 문제에 널리 사용하는 모델이다. 기본적으로 결정 트리는 결정까지 Yes/No 질문을 이어 나가면서 학습한다. 마치 스무고개와 같다. 만약 포켓몬을 맞추는 문제라고 해보자. 뮤, 아르세우스, 피카츄, 파이리 중 두가지 질문을 통해 정답을 맞출 수 있다. 이런 방법을 이용해서 지도 학습 방식으로 데이터로부터 학습할 수 있다. Decision Tree를 만들어보자. 2차원 데이터셋을 분류하는 Tree이다. 이 데이터셋은 각 클래스에 데이터 포인트가 50개씩 있고, 반달 두개가 포개진 것 같은 모양을 하고 있다. 결정 트리를 학습한다는 것은 정답에 가장 빨리 도달하는 Yes/No질문 목록을 학습하는 것이다. ML에서는 이런 질문을..
-
지도학습 | 나이브 베이즈 분류기 (Naive Bayes Classification)Machine Learning/ML with Python Library 2024. 4. 3. 22:05
Naive Bayes Classification는 Linear Model과 매우 유사하다. Logistic Regression이나 LinearSVC같은 Linear Classification보다 훈련 속도가 바른 편이지만, 대신 일반화(Generalization) 성능이 조금 뒤진다. 일반화(Generalization)는 모델이 훈련 데이터에 대해서뿐만 아니라, 본 적 없는 새로운 데이터에 대해 얼마나 잘 예측하는지를 나타내는 성능의 척도이다. 나이브 베이즈 분류기는 각 특성을 개별로 취급해서 파라미터를 학습 시키고, 클래스별 통계를 단순하게 취합한다. scikit-learn에서는 GaussianNB, BernoulliNB, MultinomialNB 이렇게 세가지다. GaussianNB는 연속적인 어떤 ..
-
CTCI | Palindrome(회문)Algorithm/Linked List 2024. 4. 3. 21:17
Cracking the Coding Interview LinkedList가 Palindrome인지 검사하는 함수를 작성하라. 먼저, Palindrome이 무엇인지 알아보자. 이효리의 유행어(?)중, 내이름은 이효리~ 거꾸로 해도 이효리~ 하는 노래가 있다. 물론 technically 따져보면 Palindrome은 아니지만, 앞으로 읽어도 뒤로 읽어도 똑같은 문장을 Palindrome이라고 한다. 한방향으로만 흐르는 LinkedList에서 Palindrome인지 어떻게 효율적으로 검사할 수 있을까? 제일 간단한 방법은, 인풋 LinkedList를 역방향으로 하나 만든 후, 그 두 Linked List가 동일한지 보는 방법이 있다. 그렇게 되면 2N의 시간이 쓰여지고, copy 버전의 Linked List를..
-
CTCI | 리스트의 합Algorithm/Linked List 2024. 4. 3. 18:13
Cracking the Coding Interview Linked List로 각 자릿수 하나씩 표현했다고 하고, 역순으로 배열 되어 있다면, 두 Linked List를 더해서 그 합을 Linked List로 반환해라 이 문제의 예시를 보면 다음과 같다. 두 Linked List가 있다고 하자. 7 -> 1 -> 6 -> null 6 -> 5 -> 9 -> 9 -> null 이 Linked Lists들은 아래 두 숫자를 나타낸다. 역순으로 저장되어있다. 617 9956 두 숫자를 더하면 어떻게 될까? 아래와 같이 계산할 수 있다. 617 + 9956 = 10573 이 수식 계산을 위해, 맨 앞 노드부터 더하고, 만약 둘중 한 List가 길이가 짧다면, null에 도달한 list의 노드 값은 0으로 계산해야..
-
CTCI | 분할(Partition)Algorithm/Linked List 2024. 4. 3. 17:53
값 x가 주어졌을 때 x보다 작은 노드들을 앞에, 크거나 같은 노드들을 뒤에 오게하는 코드를 작성하라 Linked List에서 약간의 Sorting을 해야하는 문제다. 복잡해 보이지만, 생각보다 단순하다. LinkedList 두개를 생성해서, x보다 작은것은 첫번째 리스트에, 큰것은 두번째 리스트에 추가하고, 나중에 그 두 리스트를 연결만 하면 된다. 여기서, 난이도가 쉬운 이유는, 오른쪽 노드 조합에서 x가 꼭 앞에 오지 않아도 되기도 하고, 각각의 Linked List가 Sorting되지 않아도 되기 때문이다. 그림으로 한번 나타내보자. 작은 숫자들 리스트의 첫 노드가 될 dummy node와 큰 노드들의 리스트를 만들 dummy node를 만들어서, 해당하는 숫자를 그 뒤에 쭉 붙인 후, 원래 li..
-
CTCI | 중간 노드 삭제Algorithm/Linked List 2024. 4. 2. 23:18
Cracking the Coding Interview Linked List에서 중간 노드 하나를 삭제해라 중간노드를 삭제하는 방법은 여러가지가 있다. 먼저 중간값을 구해야 하는데, 어떻게 중간 노드를 파악할 수 있을까? 먼저, 가장 간단한 로직은, 처음부터 끝까지 한번 travel을 한 후, 노드 갯수를 count해서 2로 나누는 것이다. 그런데 그렇게 되면 다시한번 반절을 가서, 1.5N의 여행을 해야한다는 단점이 있다. 여기서 우리는, 이전 문제에서 사용했던 two pointer를 사용하게 되면, 조금 더 효율적으로 풀어볼 수 있다. slower pointer와 faster pointer를 사용해서, 한 포인터는 한칸씩, 한 포인터는 두칸씩 가게 되면, 빠른 걸음을 걷는 포인터가 맨 끝, null에 ..