big O
-
CTCI | LoopAlgorithm/Linked List 2024. 4. 4. 21:03
Linked List에 있는 Loop을 찾아라 Linked List에 Cycle이 있을 수 있다. 이런 경우, 제일 첫번째 노드를 찾으라는 문제이다. 이 문제는 내가 가장 좋아하는 문제중 하나이다. 플로이드의 거북이와 토끼 알고리즘을 이용해서 풀 수 있는데, 이 알고리즘은 마치 이야기 속에서 튀어나온 듯한, 연결 리스트에서 사이클을 찾는 데에 사용되는 기발한 방법이다. 이 알고리즘은 두 주인공, 느린 거북이와 빠른 토끼를 등장시킨다. 이들은 같은 출발점, 즉 리스트의 헤드에서 여정을 시작한다. 이야기는 이렇다: 거북이는 한 번에 한 걸음씩 꾸준히 앞으로 나아간다. 반면, 토끼는 매우 빠르기 때문에, 두 걸음씩 뛴다. 만약 리스트에 사이클이 존재하지 않는다면, 토끼는 리스트의 끝에 도달하여 멈춘다. 하지만..
-
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번 이동한 노드가, 중복 노드라고..
-
Linked List | Swapping Nodes in a Linked ListAlgorithm/Linked List 2021. 5. 15. 20:14
You are given the head of a linked list, and an integer k. Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed). 앞에서 k번째, 그리고 뒤에서 k번째 노드의 값을 swap, 즉 바꾸라는 Medium 난이도의 문제이다. 아래와 같은 조건도 주었다. 노드의 값이 크지 않기때문에 swap하는것은 별로 큰 문제가 없겠지만, 총 리스트의 크기가 100,000 이기때문에 (컴퓨터에게는 그렇게 큰 숫자는 아니지만) 리스트를 travel 하는 숫자를 적게 하는..
-
Linked List | Merge In Between Linked ListsAlgorithm/Linked List 2021. 5. 13. 23:29
You are given two linked lists: list1 and list2 of sizes n and m respectively. Remove list1's nodes from the ath node to the bth node, and put list2 in their place. Medium 난이도의 문제이다. 두 Linked List가 주어졌을 때, list1의 a번부터 b를 삭제한 후, 삭제된 자리에 list2를 넣는 문제이다. O(N)으로 해결하기 위해 아래와 같이 접근했다. class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode temp = null; ..
-
Linked List | Merge Two Sorted ListsAlgorithm/Linked List 2021. 5. 2. 17:11
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists. 두 Linked List를 Merge하라는 문제이다. 두 리스트 모두 이미 순서대로 (작은숫자부터 큰숫자로) 정렬되어있다. 가장 단순한 방법은, 비교를 해가면서 새로운 리스트에 값을 복사하는 방법이 있을 것 같은데, 메모리를 조금 아끼려면, 주어진 Linked List자체를 변형하는 방법이 있다. class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode tempHe..