ALGORITHM
-
확실히 알고가야 하는 자료구조, 알고리즘 개념 (7) : Linked List 루프 찾기ALGORITHM 2021. 3. 31. 16:20
어떤 Linked List 안에 루프가 형성되어 있습니다. 이 루프의 시작 노드를 찾기 위해, 먼저 토끼와 거북이가 필요합니다. 토끼는 2 노드씩, 거북이는 1 노드씩 움직입니다. 여기서 토끼와 거북이는 절대 만나지 않는다고 걱정할 필요는 없습니다. 계속해서 토끼가 거북이를 뛰어 넘는다는 명제는 참이 될 수가 없는데, 미지수로 설정해 놓고 계산해보면 이 명제가 거짓임을 알 수 있습니다. 뛰어 넘었을 경우 토끼의 위치를 i로 설정한다면, 거북이의 위치는 i-1일 것입니다. 그렇지만 시간을 돌려 한 단계 전으로 이동하면, 토끼는 2 칸씩이니 i-2 거북이는 1 칸씩이니 (i-1)-1, 즉 i-2로 토끼와 거북이는 이미 만났다는 것이 됩니다. 그러니, 이 걱정은 접고 루프의 시작 노드를 찾는 방법으로 계속 진..
-
확실히 알고가야 하는 자료구조, 알고리즘 개념 (6) : LinkedList 교차점 찾기ALGORITHM 2021. 3. 28. 16:59
주어진 두 개의 단방향 LinkedList에서 교차되는 노드를 찾으시오. 단, 값이 아닌 주소로 찾아야 한다. 노드를 하나하나 비교하면 시간이 과하게 소요됩니다. 시간을 줄이기 위해, 노드의 끝을 맞춥니다. (교차된 이후 노드값들은 일치할 것이기 때문입니다.) 그 후, 길이가 일치하게끔 보다 긴 리스트의 길이를 자릅니다. 그리고부턴 일치되는 private static Node getIntersection (Node l1, Node l2){ //지난번에 만든 LinkedList의 길이를 반환하는 함수를 호출합니다. int len1 = getListLength(l1); int len2 = getListLength(l2); //길이가 맞게끔 잘라주는 작업을 합니다. if(len1 > len2){ l1 = l1..
-
확실히 알고가야 하는 자료구조, 알고리즘 (4) : Linked List 중간 노드 삭제하기ALGORITHM 2021. 3. 27. 13:47
삭제해야 하는 노드의 다음 노드의 데이터를 복사하여 삭제해야 하는 노드에 덮어 씌웁니다. 그리고 중복되는 노드를 삭제합니다. public class Test { public static void main (String[] args){ LinkedList ll = new LinkedList(); ll.append(1); ll.append(2); ll.append(3); ll.append(4); ll.retrieve(); deleteNode(ll.get(2)); ll.retrieve(); } private static boolean deleteNode(Node n){ if(n == null || n.next == null){ //이 로직은 처음과 마지막 노드는 삭제할 수 없습니다. return false; ..
-
확실히 알고가야 하는 자료구조, 알고리즘 개념 (3) : 단방향 Linked List의 끝에서 k 번째 노드 찾기ALGORITHM 2021. 3. 26. 16:07
방법 1 뒤에서 k 번째는 앞에서 n - k + 1 번째 노드 방법 2 재귀 호출 : 조건이 만족될 때까지 계속해서 호출하는 방법 >> 끝까지 들어갔다가 k 번을 세면서 나오면 됩니다. private static void KthToLast(Node n, int k){ if(n == null){ return 0; } int count = KthToLast(n.next, k) + 1; if (count == k){ System.out.println(k + "th to last node is" + n.data); } return count; } 값이 아닌 노드를 찾으라는 문제였기에, 다른 것을 출력해야 합니다. C++에서는 PathByReference라는 기능(값이 아닌 주소를 전달)을 이용해 노드를 출력할 ..
-
확실히 알고가야 하는 자료구조, 알고리즘 개념 (2) : 단방향/양방향 Linked ListALGORITHM 2021. 3. 25. 18:17
단방향 Linked List Linked List지만, 자기보다 앞선 노드의 주소는 모르고, 자신 바로 뒤에 있는 노드의 주소만 알고 있는 경우, 단방향 Linked List라고 합니다. 그렇기에, 검색 시에는 가장 앞에 있는 노드부터 시작합니다. 양방향 Linked List 자신 앞, 뒤의 주소를 추가적으로 가지고 있습니다. 삽입 삭제 수정 시, 양방향 Linked List는 삽입하고자 하는 앞, 뒤의 노드를 전부 수정해야 합니다. 단방향 Linked List는 앞의 노드만 수정하면 됩니다. 효율성에 대해 더 알아봐야 합니다.
-
확실히 알고가야 하는 자료구조, 알고리즘 개념 (1) : Linked ListALGORITHM 2021. 3. 25. 18:08
Linked List 컴퓨터에 자료를 저장하는 자료구조 중 하나입니다. 일렬로 연결된 데이터를 저장할 때 사용합니다. 데이터, 그 안에 다음 순서의 데이터 주소를 저장해 놓습니다. 배열과의 비교 배열은 만들어질 때, 방을 만듭니다. 이 때, 방은 크기를 줄이거나 늘일 수 없습니다. 삽입 시, Linked List의 경우, 앞선 노드에 저장되어 있는 다음 노드의 주소를 자신의 것으로 가져오는 형태입니다. 제거 시, Linked List의 경우, 삭제되어야 하는 노드의 주소를 다음 노드의 주소로 변경해주는 형태입니다. (이 때, 삭제된(실제로는 해당 노드로 향하는 주소가 저장되어있지 않아 삭제된 것 처럼 보이는) 노드는 JAVA에선 자동으로 삭제를 해줍니다. 허나 C#, C++에선 안쓰겠다고 반드시 명시를 ..
-
알고리즘: 이분탐색(Binary Search)ALGORITHM 2020. 11. 8. 16:31
이분 탐색의 개념 1부터 20까지의 수가 있다고 가정하자, 여기서 13을 찾아내려고 할 때, 아무 생각을 하지 않고 코드를 작성하면 단순히 for문을 통해 for(int i = 1; i < 21; i++) 로 찾게 될 것이다. 찾고자 하는 값이 1, 2처럼 시작점과 가까운 값이라면 시간 효율이 나쁘지 않겠지만, 18, 19와 같이 끝자락에 있는 수라면, 시간 효율이 극악이다. 사실 20이라는 작은 범위 내에서는 거기서 거기지만, (눈으로도 그냥 가능하다) 백의 자리, 천의 자리로 넘어가면 사람의 눈으로 빠르게 판단하는 데에는 불가능하고, 십만, 백만, 천만 등 그 수가 기하급수적으로 커지게되면 컴퓨터 역시 시간효율이 좋은 방법을 찾아내야 한다. 이 때 사용하는 탐색 방법이 이분 탐색이다. 이분 탐색의 원..