# 2월 2주차 내용 정리 취합 (5조 - 정준영, 최지혜)

Created: Feb 6, 2021 8:28 PM
Last Edited Time: Feb 7, 2021 11:12 PM

## 1. 연결리스트

### 1.1 리스트

- 순서를 가진 데이터의 집합을 가리키는 추상 자료형
- 동일한 데이터를 가지고 있어도 상관 없다.
- 구현 방법에 따라 두 가지로 나뉜다.
- 순차 리스트
- 연결 리스트

### 1.2 순차 리스트

- 구현 방법
- 1차원 배열에 항목들을 순서대로 저장한다.
- 데이터 접근
- 배열의 인덱스를 이용하여 원하는 위치에 데이터를 접근한다.
- 데이터 삽입
- 삽입 위치 다음 항목들이 존재하면, 이동이 필요하다.

- 데이터 삭제
- 삭제 위치 다음 항목이 존재하면, 이동이 필요하다.

- 순차 리스트의 문제점
- 데이터 삽입/삭제 과정에서 원소들의 이동 작업이 필요하다.
- 데이터의 개수가 많고, 삽입/삭제 연산이 빈번하면 작업 시간이 많이 소요된다.
- 배열의 크기가 정해져 있는 경우, 메모리 낭비가 발생할 수 있다.
- 메모리 보다 많은 데이터를 사용하게 되는 경우 새로운 배열 생성이 필요하다.

### 1.3 연결 리스트

- 메모리 상의 물리적 순서와 논리적 순서가 일치하지 않음.
- 순차 리스트 처럼 물리적 순서 맞추기 작업이 필요 없다.
- 자료 크기 동적 조정가능하기 때문에 메모리의 효율적인 사용이 가능하다.

#### 1.3.1 노드
- 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위
- 구성요소
- 1. 데이터 필드
- 원소의 값을 저장하는 자료구조
- 저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함
- 2. 링크 필드
- 다음 노드의 주소를 저장하는 자료구조

#### 1.3.2 헤드
- 리스트의 처음 노드를 가리키는 레퍼런스
- 헤드는 노드가 아니다.

### 1.4 단순 연결 리스트

#### 1.4.1 연결 구조
- 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조.
- 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
- 최종적으로 NULL을 가리키는 노드가 리스트의 가장 마지막 노드이다.

#### 1.4.2 첫 번째에 노드 삽입 방법
1. 메모리를 할당하여 새로운 노드 new 생성
2. 새로운 노드의 데이터 필드에 데이터 저장
3. 새로운 노드의 링크 필드에 Head에 저장된 주소 값을 저장
4. Head에 새로운 노드의 주소 값 저장

addtoFirst(L, i)
    new <- CreateNode();
    new.data = i;
    new.link = L;
    L = new;
end addtoFirst();

#### 1.4.3 중간에 노드 삽입 방법
1. 메모리를 할당하여 새로운 노드 new 생성
2. 새로운 노드의 데이터 필드에 데이터 저장
3. 새로운 노드의 링크 필드에 삽입 노드 다음 값 주소저장
4. 리스트의 삽입 전 노드의 링크 필드에 새로운 노드의 주소 값 저장

add(L,pre, i)
    new <- CreateNode();
    new.data = i;
    if(L = NULL) then{
        L = new;
        new.link = NULL;
    }
    else{
        new.link = pre.link;
        pre.link = new;
    }
end end();

#### 1.4.4 마지막 노드 삽입 방법
1. 메모리를 할당하여 새로운 노드 new 생성
2. 새로운 노드의 데이터 필드에 데이터 저장
3. 새로운 노드의 링크 필드에 NULL저장
4. 리스트의 마지막 노드의 링크 필드에 새로운 노드의 주소 값 저장

addtoLast(L, i)
    new <- CreateNode();
    new.data = i;
    new.link = NULL;
    if(L=NULL)then{
        L = new;
        return;
    }
    temp = L;
    while(temp.link != NULL)do
        temp = temp.link;
    temp.link = new;
end addtoLast();

#### 1.4.5 노드 삭제 방법
1. 삭제할 노드의 앞 노드 탐색
2. 삭제할 노드의 링크 필드를 선행 노드의 링크 필드에 복사
3. 삭제할 노드의 링크 필드에 NULL 저장

delete(L, pre)
    if (L=NULL) then error;
    else{
        target = pre.link;
        if(target == NULL) then return;
        pre.link = target.link;
    }
    freeNode(target)
end delete()

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

### 1.6 리스트 관련 팁
- java에서 제공하는 API를 이용하여 구현하지 않아도 사용할 수 있다.

import java.util.LinkedList;
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(33);

- 속도적인 부분에서는 직접 구현하는 것이 빠르다.

# 1. 트리
### 트리의 개념

- 비선형 구조 (전후 관계가 1:1이 아닌)
- **원소들 간에 1 : n 관계**를 갖는 자료구조 (n : m → 그래프 자료구조)
- 원소들 간에 **계층관계**를 갖는 계층형 자료구조
- 상위 원소에서 하위 원소로 내려가면서 **확장**되는 트리(나무)모양의 구조

### 트리의 정의

- 한 개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.
1. 노드 중 최상위 한 개 노드를 루트(root)라고 한다. (마치 연결리스트의 head처럼)

+) 자식이 없는 노드 : (단말노드 = leaf 노드), 궁극적으로 표현하고 싶은 데이터가 단말노드에 담겨 있는 경우가 많다.

2. 나머지 노드들은 n(≥0)개의 분리 집합 T1, ..., TN 으로 분리될 수 있다.
- 이들 T1, ... TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라고 한다.

### 용어 정리

- 노드(node) : 트리의 원소
- 간선(edge) : 노드를 연결하는 선으로 부모노드와 자식노드를 연결
- 루트 노드(root node) : 트리의 시작노드
- 형제 노드(sibling node) : 같은 부모 노드의 자식 노드들

** 형제 노드들끼리는 연결되어있지 않음에 유의

- 조상 노드 : 간선을 따라 루트노드까지 이르는 경로에 있는 모든 노드들
- 서브 트리(subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
- 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 (자식노드의 자식노드도 포함)
- 차수(degree)

노드의 차수 : 노드에 **연결된 자식 노드의 수 ****(자손노드 아님)

트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값(루트노드의 차수가 아님에 유의

단말 노드(리프 노드) : 차수가 0인 노드, 즉 자식 노드가 없는 노드

- 높이(level)

노드의 높이 : **루트에서 해당 노드에 이르는 간선의 수 → 루트 노드의 레벨 : 0**

트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대레벨

# 이진트리

- **모든 노드들이 2개의 서브트리를 갖는** 특별한 형태의 트리 → ???
- **각 노드가 자식 노드를 최대한 2개까지만** 가질 수 있는 트리
- 왼쪽 자식 노드(left child node)
- 오른쪽 자식 노드(right child node)
- 이진 트리의 예

## 이진트리의 특성

- 레벨 i 에서 노드의 최대 개수는 2^i 개
- 높이가 h 인 이진트리가 가질 수 있는 노드의 최소 개수는 h+1, 최대개수는 2^(h+1) -1

## 이진트리 종류

### 포화 이진트리 (full)

- 모든 레벨의 노드가 포화상태로 차있는 이진트리
- 높이가 h일 때 최대 노드 개수인 2^(h+1) -1 개의 노드를 가진 이진트리
- 루트를 1번으로 하여 레벨에 따라 ?번호 부여함

### 완전이진트리 (complete)

**예) heap → priority queue**

- 높이가 h이고 노드수가 n개 일 때, 포화 이진트리의 **노드번호 1번부터 n번까지 빈자리가 없는** 이진트리

- 루트부터 노드를 채우는 방식은 포화이진트리 방식으로 채운다
- **마지막 레벨은 꽉 채우지 않아도 된다.**

### 편향 이진트리 (Skewed)

- 높이 h에 대한 최소 개수의 노드를 가지면서 (= h+1) 한쪽 방향의 자식 노드만을 가진 이진트리
- 왼쪽 편향 이진 트리
- 오른쪽 편향 이진 트리

## 이진트리의 표현

### 배열을 이용한 이진트리의 표현

- 이진트리에 각 **노드 번호**를 다음과 같이 부여 (→ 번호를 배열의 인덱스로 활용, 배열크기는 노드 최대개수+1로 선언, 0인덱스는 안 사용하므로)

→ 내 번호에 2 곱하면 내 왼쪽 자식노드의 번호, 2곱해서 1 더하면 내 오른쪽 자식노드의 번호, 2나누면 내 부모노드의 번호

- 루트 번호를 1로 함
- 레벨 n에 있는 노드에 대하여 왼쪽부터 오른쪽으로 2^n부터 2^(n+1) -1 까지 번호를 차례로 부여

- 편향이진트리인 경우 배열을 이용하여 표현할 때 메모리 공간 낭비가 많음

+) 노드 삭제, 삽입의 경우 배열은 크기가 가변적이지 않으므로 비효율적 → 더블 연결리스트!(왼쪽자식link, 오른쪽자식link) (아이디어만 알기)

# 비선형 자료구조의 완전탐색

- 비선형구조인 트리와 그래프의 각 노드(정점)를 중복되지 않게 전부 방문(visit) 하는 것을 말하는데

비선형구조는 선형구조와 달리선후 연결관계를 알 수 없다.

→ 따라서 특별한 방법이 필요하다

- 두 가지 방법
1. 너비 우선 탐색(Breadth First Search)
2. 깊이 우선 탐색(Depth First Search)

# BFS

- 너비우선탐색은 루트 노드의 자식노드들을 먼저 모두 차례로 방문한 후에,

방문했던 자식 노드들을 기준으로 하여 다시 해당 노드의 자식노드들을 차례대로 방문하는 방식(=레벨 별로)

- 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선 탐색을 진행해야 하므로

**선입선출 형태의 자료구조인 큐를 활용함 (탐색 순서를 유지**하기 위함)

예) 할아버지는 자기 자식하고만 직접 연결되어있음, 손자까지 가려면 먼저 아들을 거친 후 이 때 아들의 자식링크를 큐에 저장해야 함)

탐색 순서 : 할아버지 → 아들 → 딸 → 아들의 자식... → 딸의 자식...

큐 : 아들의 자식 저장 → 딸의 자식 저장

- BFS 알고리즘

루트노드 기준 연결된 간선의 수(=자식 수?)를 너비라고 보면 됨

큐에 무얼 넣을지는 문제에 따라 달라질 수 있음!

BFS()
	큐 생성
	루트 v를 큐에 삽입
	while(큐가 비어있지 않은 경우) {
		t <- 큐의 첫 번째 원소 반환
		t 방문
		for (t와 연결된 모든 간선에 대해){
			u <- t의 자식노드
			u를 큐에 삽입
		}
  }
end BFS()

# ** 디버깅

1. 더블클릭으로 break point 정하기 → F11 키 (Ctrl은 말고)
2. 우측 상단에 벌레모양 아이콘 누르고 역삼각형 눌러서 static variable에 체크하면 variables 탭에서 확인 가능
3. 디버깅 다 했으면 빨간 네모 아이콘 눌러서 중지해주어야 메모리 안잡아먹음
- F5는 메서드에 찍으면 타고 들어감 잘못들어가면 F7로 다시 나올 수 있음
- F6은 메서드에 찍으면 기능은 다 하고 다음 라인으로 넘어감
- F8은 다음 쭉 진행함 만약 break point 만나면 거기서 멈춤
- expression 탭에 연산결과나 메서드호출결과는 수식으로 직접 입력 가능함. 예) queue.size()
- windows - preferences → step 검색 → stop filtering 선택 → Select All 혹은 알아서 체크 후 apply and close 누르면

q.poll()같은거에 F5 실수로 눌러도 타고 안들어감

- 재귀는 프린트로 확인하는 것이 편함(?)
- if문 괄호 안 조건들 사이에 엔터 치면 조건마다 분리해서 확인할 수 있음

# DFS

- 깊이우선 탐색은 **루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색**해 가다가

더 이상 갈 곳이 없게 되면, **가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서** 다른 방향의 노드로 탐색을 계속 반복하여

결국 모든 노드를 방문하는 순회방법이다.

- 가장 마지막에 만났던 갈림길의 노드로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로

**재귀적으로 구현**하거나 후입선출 구조의 스택을 사용해서 구현한다.

- DFS 알고리즘

DFS(v)
	v 방문;
	if(v의 자식노드  없으면) return;
	for(v의 모든 자식노드 w) { 
		DFS(w);
	}
end DFS

## 이진트리 - DFS 순회(traversal) 방법

- 순회 : 트리의 노드들을 쳬계적으로 방문하는 것
- 3가지의 기본적인 순회방법
1. 전위순회 VLR : 부모노드 방문 후 자식노드를 좌,우 순서로 방문
2. 중위순회 LVR : 왼쪽자식노드 → 부모노드 → 오른쪽 자식노드 방문
3. 후위순회 LRV : 자식노드를 좌,우 순서로 방문한 후 부모노트를 방문

### 전위순회 (preorder traversal)

- 수행방법 :
1. 현재 노드 T를 방문하여 처리 → V
2. 현재 노드 T의 왼쪽 서브트리로 이동한다 → L → 같은 알고리즘으로 처리한다 (=재귀)
3. 현재 노드 T의 오른쪽 서브트리로 이동한다 → R → 같은 알고리즘으로 처리한다 (=재귀)
- 전위순회 알고리즘

preorder_traverse (T)
	if ( T is not null) {
		visit(T);
		preorder travers(T.left);
		preorder travers(T.right);
	}
End preorder_traverse

- 중위순회 ,후위순회도

visit(T); preorder travers(T.left); preorder travers(T.right);

순서만 다름

### 수식트리

수식을 표현하는 이진 트리

수식이진트리라고도 함

. . . (각자 읽어보기)

# Heap

: **완전 이진 트리**에 있는 노드 중에서 **키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해**서 만든 **특별한 자료구조**

### 최대 힙(max heap)

- 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 > 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 큰 노드

### 최소 힙(min heap)

- 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
- 부모 노드의 키 값 < 자식 노드의 키 값
- 루트 노드 : 키 값이 가장 작은 노드

### 활용

1. 원소 넣을때

배열이라면 최대값인 1000 저장할 때 큰 순서로 정렬하려고 하면 맨 앞부터 1000번 비교해야 함

그런데 만약 최대 힙을 사용하면

→ 완전이진트리의 모양을 유지하도록 넣어줌 (왼쪽→오른쪽 자식 순서로 부모노드가 자식노드보다 큰지 확인하고 스왑 작업을 하면서)

→ 약 10번만 비교하면 됨 (logN)

2. 루트노드 삭제할 때

완전이진트리는 유지해야함 그러므로 마지막 리프노드를 루트로드로 가져온다

그 다음 크기 비교하며 스왑 작업 반복 (logN)

⇒ **힙으로 구현된 것이 우선순위 큐**이다.

기본은 Natural ordering 으로 최소힙으로 관리되고 있다.

순서 관리하는 기준을 변경하고 싶다면 comparable과 comparator를 사용한다.

# 이번 주 문제
## 정사각형 방(그래프)
- 문제의 조건을 활용하여, 탐색할 범위 제한 가능
- 이미 탐색된 값을 저장하여 다른 위치에서 탐색할 때 활용 가능.
- 재귀의 리턴 값을 활용하여 연산 가능
## 스택 계산기(스택)
- 스택을 이용한 우선순위에 따른 데이터 처리 방법
- infix에서 postfix로의 전환 방법

## 암호문(연결리스트)
- 연결리스트 구현 연습해보기
- 연결리스트의 중간(처음,끝X) 삽입 메서드를 활용 가능
## 한빈이와 spot mart(완전탐색)
- 정렬하여 그리디적으로 접근가능
- 과자르 2봉지만 고르느 것이므로 재귀 말고 for문으로도 간딘히 구현 가능
## 요세푸스(연결리스트)
- 제거한 사람의 다음을 head로 하고 제거한 사람의 이전 사람들을 연결리스트의 마지막 노드부터 순서대로 추가하는 작업을 한 명도 남지 않을 때 까지 반복
- 각 노드의 링크 간 연결에 유의
- 사람 수 보다 순서 K가 큰 경우 K-사람수 를 K가 사람 수보다 작거나 같을 때까지 반복
## 색종이(2차원배열?)
- 도화지의 상태를 표현하는 2차원 배열 생성
- 입력 받은 색종이의 왼쪽 아래 위치로부터 가로, 세로로 10만큼의 영역을 1로 저장
- 1의 합을 구하면 색종이의 넓이