8.7

바킹독 - 정렬

Bj2752 세수정렬
  - Arrays.sort(arr);

Bj2490 윷놀이
  - 도개걸윷모 확인
  
Bj2576 홀수
  - 

Bj2493 탑
  - 메모리초과 -> stringbuilder 사용
  - 인덱스 접근 -> 클래스 만들어서.

알고리즘 - 연결리스트

그래프 : 비선형 자료구조.

-----
리스트
  - 순서를 가진 데이터의 집합을 가리키는 추상자료형
  - 동일한 데이터를 가지고 있어도 상관없다.
  
  - 구현방법에 따라 크게 두 가지로 나뉜다.
    - 순차 리스트 : 배열을 기반으로 구현된 리스트 -> 메모리에 순차적할당 관리
    - 연결 리스트 : 메모리의 동적 할당으로 구성.

-----
순차리스트
  - 1차원 배열에 차례대로 저장.
  - 특정 위치 삽입 삭제가 이루어질 시 연산 많음.
  
단점
  - 자료의 삭제/삽입 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시켜야 한다.
  - 
  
-----
연결 리스트, Linked List
  - 자료의 논리적인 순서와 메모리의 물리적인 순서가 일치하지 않고, 개별적으로 위치한 각 원소를 연결하여 하나의 전체적인 자료구조를 이룬다.
  - 링크를 통해 원소에 접근하므로 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
  
-----
노드
  - 연결 리스트에서 하나의 원소를 표현하는 building block
  - 구성 요소
    - 데이터 필드
      - 원소의 값을 저장
      - 저장할 원소의 종류나 크기에 따라 구조를 정의
    - 링크 필드 : 연결리스트 유지(관리)
      - 다음 노드의 참조값을 저장.
헤드
  - 연결리스트 첫 노드에 대한 참조값을 갖고 있음.
  - 단 꼬리로 가려면 엄청 긴 여정 끝에 가야함.
    - 필요 시, tail 위치도 참조값을 저장.
 
-----
단순 연결 리스트
  - Data, Link.
  - 링크 필드가 null인 노드가 가장 마지막 노드.

  삽입 -  =============================

-----

+ 스택 구현 해보기.
import java.util.EmptyStackException;

public class LinkedListStack<E> implements IStack<E>{

	private Node<E> top = null;
	
	@Override
	public void push(E e) {
		top = new Node<>(e,top);
	}

	@Override
	public E pop() {
		if(isEmpty())
			throw new EmptyStackException();
		Node<E> popNode =top;
		top = popNode.getLink();
		popNode.setLink(null);
		return popNode.getData();
	}

	@Override
	public E peek() {
		return top.getData();
	}

	@Override
	public int size() {
		int size = 0;
		
		for(Node<E> temp = top; temp !=null;temp = temp.getLink()) {
			++size;
		}
		
		return size;
	}

	@Override
	public boolean isEmpty() {
		return top == null;
	}

}

-----
이중 연결 리스트
  - 양방향으로 순회할 수 있도록 노드를 연결한 리스트
  - 두 개의 링크 필드와 한 개의 데이터 필드로 구성.

-----
원형 연결 리스트
  - 임의의 노드에서 완전탐색을 가능하게 함.

------

Quiz. 2의 제곱근 판단법.
System.out.println((n & (-n)) == n ? "1" : "0");
컴퓨터는 2의 보수로 음수를.

------
1228. [S/W 문제해결 기본] 8일차 - 암호문1
  - 덱 하나 더 만들어서 옮기고 넣고 옮기고.