Algorithm/Linked List
-
CTCI | LoopAlgorithm/Linked List 2024. 4. 4. 21:03
Linked List에 있는 Loop을 찾아라 Linked List에 Cycle이 있을 수 있다. 이런 경우, 제일 첫번째 노드를 찾으라는 문제이다. 이 문제는 내가 가장 좋아하는 문제중 하나이다. 플로이드의 거북이와 토끼 알고리즘을 이용해서 풀 수 있는데, 이 알고리즘은 마치 이야기 속에서 튀어나온 듯한, 연결 리스트에서 사이클을 찾는 데에 사용되는 기발한 방법이다. 이 알고리즘은 두 주인공, 느린 거북이와 빠른 토끼를 등장시킨다. 이들은 같은 출발점, 즉 리스트의 헤드에서 여정을 시작한다. 이야기는 이렇다: 거북이는 한 번에 한 걸음씩 꾸준히 앞으로 나아간다. 반면, 토끼는 매우 빠르기 때문에, 두 걸음씩 뛴다. 만약 리스트에 사이클이 존재하지 않는다면, 토끼는 리스트의 끝에 도달하여 멈춘다. 하지만..
-
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을 이용해 로..
-
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..
-
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번 이동한 노드가, 중복 노드라고..