분류 전체보기
-
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에 ..
-
CTCI | 뒤에서 k번째 원소Algorithm/Linked List 2024. 4. 2. 22:58
Cracking the Coding Interview LinkedList에서 뒤에서 k번째 노드의 값을 찾는 알고리즘을 구현해라. Linked List에서 뒤에서 k번째 노드를 찾는 알고리즘! 가장 간단한 방법은 무엇일까? 만약 10개의 노드가 있는데 k=3이라면? 8번째 노드가 뒤에서 세번째가 된다. 즉, 노드의 총 갯수를 구하고, 그것을 size 라고 했을 때, size - k 번 head에서 next한 노드의 값을 리턴하면 된다. 이 방법으로 하면, N개의 노드를 가진 LinkedList에서 O(N)의 Time Complexity로 계산할 수 있다. 코드로 한번 구현해보자. int findKthNodeValue(Node head, int k){ int count = 0; Node curr = hea..
-
지도학습 | 선형모델의 장단점과 매개변수Machine Learning/ML with Python Library 2024. 4. 2. 22:26
선형 모델의 주 매개변수는 Regression 모델에서는 alpha였고, Classification Model이었던 LinearSVC와 LogisticRegression에서는 C였다. alpha값이 클수록, C값이 작을수록 모델은 단순해진다. 특히, Regression 모델에서 이 매개변수를 조정하는 일은 매우 중요하다. 또한 규제를 L1, L2중 어떤것을 사용할지 정해햐아하는데, 중요한 특성이 많이 없을땐 L1을, 그렇지 않으면 L2를 사용한다. L1은 몇가지 특성만 사용하기 때문에, 해당 모델에 중요한 특성과 효과를 이해하기 쉽다. Linear 모델은 학습 속도도 예측도 빠르다. 또한, 예측이 어떻게 만들어 지는지 비교적 쉽게 이해할 수 있다. Linear 모델은 특성이 많을 때 잘 작동하는데, 다른..
-
지도학습 | 다중클래스 분류용 선형 모델 (MultiClass Classification Linear Model)Machine Learning/ML with Python Library 2024. 4. 2. 22:18
Logistic Regression을 제외한 많은 Linear Classification 모델은 Binary Classification만을 지원한다. 즉, multiclass를 지원하지 않는다. 이 binary알고리즘을 multiclass로 확장하기 위해서는 가장 보편적인 기법, one vs rest, 즉 일대다 방식을 사용하면 된다. 각 클래스를 다른 모든 클래스와 구분하도록 binary classification 모델을 학습시키는것인데, 결국 클래스 수만큼 binary classification 모델이 만들어진다. 모든 결과값 중, 가장 높은 점수를 내는 classification의 클래스를 예측값으로 선택하면 된다. 세개의 클래스를 가진 간단한 데이터셋에, 이 일대다 방식을 적용해보자. # !pip..
-
CTCI | 중복 없애기Algorithm/Linked List 2024. 4. 2. 16:03
Cracking the Coding Interview 문제: 정렬되어있지 않은 Linked List에서 중복되는 원소를 제거하는 코드 작성하기 우선 Linked List의 특징은, head에 대한 포인트를 갖고 시작한다는것과, 사이즈가 얼마나 될지 알지 못한다는 것이다. 이 문제를 풀 수 있는 가장 간단한 방법은, Set을 사용해서 지금까지 등장한 원소들을 저장해가면서, 만약 Set에 없다면, Set에 추가하고 넘어가고, 만약, Set에 존재한다면, 그 해당 노드를 건너뛰는 방식으로 진행할 수 있다. 여기서 또 한가지 생각해야하는것은 Deletion과 Edge케이스이다. 먼저, Delete를 어떻게 해나갈지, LinkedList를 그려가며 생각해보자. head 노드에서 2번 이동한 노드가, 중복 노드라고..