Algorithm (18) 썸네일형 리스트형 [자료구조] Queue 구현 컬렉션으로서의 큐 1. 큐는 인터페이스이고, 이를 구현하는 구현 클래스를 참조하게 업캐스팅하여 사용해야 한다. e.g. Queue queue = new LinkedList(); || Queue queue = ArrayDequeue(); 좌변과 우변의 타입이 일대일 대응(?)되는 형태의 컬렉션들은 모두 그 자체로 구현 클래스여서 그러하다. 하지만 큐는 그렇지 않으므로 LinkedList나 ArrayDequeu같은 구현 클래스를 통해서 사용할 수 있다. 2. 인덱스를 써야하는 상황에선 LinkedList를, 다른 경우은 ArrayDequeue가 더 성능이 좋다. 아래 자바 컬렉션 상속도를 보면 알겠지만, LinkedList는 Queue인터페이스와 Dequque 인터페이스를 모두 구현한다. 그리고 ArrayD.. [자료구조] Stack 구현 stack을 배열로 구현 삼단 논법처럼 생각하면 쉽다. 1. stack에서 데이터가 들어가고 나가는 입구는 top뿐이다. 2. 스택은 배열로 구현할 수 있다. 3. 배열에서 데이터에 접근할 때는 index를 이용한다. => 스택을 배열로 구현하면, top을 인덱스로 사용하며 이것이 데이터에 접근할 유일한 통로가 된다. 주의 사항 1) 데이터가 들어오지 않았을 때 top은 -1이다. 하나가 들어오면 그때 0으로 스택의 top을 표시해야 하므로 top은 -1로 초기화한다. 2) 배열로 스택을 구현하였을때, 길이가 정해져있다는 배열의 특성을 반영해야 한다. 따라서 push를 할 때는 배열이 가득 찼는지, pop이나 peek을 할 때는 배열이 empty는 아닌지 고려해야 한다. 이를 고려하지 않으면 top이 배.. [자료구조] Circular Doubly LinkedList 구현 싱글, 더블리 링크드 리스트와 기본적으로 동일하지만, tail까지 가는 방법이 다르다. 싱글, 더블리 링크드 리스트에서는 tail까지 이동하기 위해서 아래 코드를 사용했지만, Node cur = this.head; while (cur.next != null) { cur = cur.next; } 원형 링크드 리스트는 모든 노드가 연결되어있으므로 while(cur.next != null)을 그대로 사용하면, 무한 루프가 발생한다. 따라서 tail까지 이동하는 조건으로 cur.next != head를 사용해야 한다. 또는 head가 있다는 조건 하에, head.prev로 바로 tail에 접근할 수 있다. // tail 접근법 1 Node cur = this.head; while (cur.next != this.. [자료구조] Doubly LinkedList 구현 싱글리 링크드 리스트와 달리, Node에서 prev와 next를 모두 저장한다. 따라서 삽입과 삭제를 한 후에도 정상적인 구조를 유지하도록 prev와 next를 모두 수정해주야 한다. package DoublyLinkedList; class Node{ int data; Node next; Node prev; Node(int data, Node prev, Node next){ this.data = data; this.prev = prev; this.next = next; } } class DoublyLinkedList { Node head; boolean isEmpty() { if (head == null) { return true; } return false; } int getSize() { int si.. [자료구조] Singly LinkedList 구현 배열처럼 원하는 값에 한번에 접근할 수 없으니 모든 접근을 head를 통해서 해야한다. 또한, next 링크가 삽입과 삭제 이후에도 정상적으로 작동할 수 있게 next를 제대로 수정해줘야 한다. 특히 어디에서 (중간에서 or head에서 or tail에서) 삽입/삭제할 것인지에 따라서 다르게 처리해줘야 한다는 것을 주의해해야 한다. 삽입 삭제의 자세한 원리는 아래 그림 참고하면 된다. 코드 package SinglyLinkedList; public class Main { class Node{ int data; Node next; Node(int data, Node next){ this.data = data; this.next = next; } } class SinglyLinkedList { Node he.. [자료구조] LinkedList 란? 데이터를 집어넣는 방법 메모리 확보 후 연속된 공간에 채워넣기 vs 필요할 때마다 메모리를 할당받아 데이터를 저장 전자는 배열이고 후자는 연결리스트 즉, Linked List 라고 함 배열과 링크드 리스트의 차이 배열의 특징 : 미리 공간을 확보하지만, 확보되는 공간보다 적게 사용하면 메모리가 낭비될 수 있음 cf. 배열의 한 칸을 셀(cell), 또는 요소(element)라고 함 링크드 리스트 특징 : 낭비되는 데이터는 없지만, 연관 데이터끼리 '연결' 짓는게 필요함 node는 필요에 따라 동적으로 할당되고 자바에서는 자동으로 메모리를 정리해주므로 낭비되는 저장 공긴이 없음 하지만 data와 idx만 저장하는 배열과 달리 추가적으로 저장해야 될 것이 있으므로 그 자체의 저장 공간은 배열보다 큰 편 링크.. 백준 11729번 : 하노이 탑 이동 순서 with 재귀함수 잘 설계하는 법 재귀함수 잘 설계하는 법 1. 마인드 세팅 : 함수의 흐름을 생각하지 말고, 큰 그림에 집중하기 재귀 함수를 잘 설계하기 위한 제 1 원칙은 '재귀적으로 생각하지 말기'이다. ❗함수의 실행 흐름과 콜스택을 그대로 따라가려하지 말자.❗ => 특히 내가 많이 하는 실수 특정 단계에서 이전 단계와 조합되어 어떻게 작동하는지에만 집중하자. 함수를 호출할 때마다 베이스 조건에 가까워져야 한다. 그 전 단계에서 무조건 정답이 리턴되었다고 믿자. 그리고 그 이상은 생각하지 말자. 이걸 '재귀적 믿음의 점프'라고도 부른다. (이런 용어가 있을 정도로 하나의 단계에 대해서만 생각하고, 이전 단계는 이미 정답이라 믿는 것이 재귀함수를 풀이하는 일반적인 방법임) 위의 마인트를 탑재했다면, 아래 방법으로 재귀함수를 만들어주면.. 백준 17609번 : 회문 문제 17609번: 회문 (acmicpc.net) 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 아이디어 우선 가장 간단한 아이디어는 StringBuilder의 reverse와 equals만을 이용하는 풀이이다. 1. reverse한게 원본과 같으면 0 출력 2. for문을 돌면서 하나씩 삭제한 다음, reverse한게 원본과 같으면 1 출력 3. for문을 다 돌 때까지 원본과 같지 않으면 2 출력 하지만, 이렇게 하면 reverse / delete / insert 와 같은 함수를 문자열의 길이만큼 반복해줘야 하므로 시간초과가 발생한다... 이전 1 2 3 다음
