띠용

투 포인터 알고리즘

: 정렬된 1차원 배열 내에서 시작과 끝을 가리키는 2개의 포인터를 설정한 후 이를 조작해가며 원하는 것을 얻는 알고리즘이다.

사용

- 배열 또는 리스트에서 특정 조건을 만족하는 부분 배열 또는 부분 리스트 찾기

- 배열에서 합이 특정 값이 되는 두 요소 찾기

- 정렬된 배열에서 특정 합이 되는 요소 쌍 찾기

시간 복잡도

: O(n)

- 각 포인터가 n번 누적 증가해야 알고리즘이 끝나기 때문에 O(n) 시간복잡도가 발생한다.

필요성

: 완전 탐색의 경우 O(n²) 시간복잡도가 발생하지만 투 포인터 알고리즘을 사용하면 O(n)의 시간복잡도가 발생한다.

공식

ex) 입력된 자연수 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 출력

- 모든 경우를 확인할 때까지 반복

     - 합 < 특정 값: end 포인터 이동하고 해당 값을 합에 더함

     - 합 > 특정 값: 합에서 start 포인터가 가리키는 인덱스의 값을 뺀 후 start 포인터 이동

     - 합 == 특정 값: count 변수를 1 증가시키고 합에서 start 포인터가 가리키는 인덱스의 값을 뺀 후 start 포인터 이동

- count 출력

import java.io.*;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(br.readLine());
        long n = Long.parseLong(input.nextToken());
        long start = 1;
        long end = 2;
    	long sum = start + end;
    	long count = 1;
    	
    	sum = start;
    	while(start < n && end <= n) {
    		if(sum < n)
    			sum += end++;
    		else if(sum > n){
    			sum -= start;
    			start++;
    		}
    		else {
    			count++;
    			sum -= start;
    			start++;
    		}
    	}
    	System.out.println(count);
    }
}

그림 설명

슬라이딩 윈도우 알고리즘

: 1차원 배열 또는 리스트에서 연속된 구간을 유지하면서 윈도우를 이동시켜 원하는 조건을 만족하는 연속 부분 배열을 찾는 알고리즘이다.

사용

- 연속 부분 배열의 합이 특정 값 이하 또는 이상인 최대 / 최소 길이 구하기

- 연속 부분 배열의 합이 특정 값이 되는 구간 개수 세기

- 문자열에서 주어진 조건 등을 만족하는 최대 / 최소 길이 부분 문자열 찾기

시간 복잡도

: O(n)

필요성

: 브루트포스 알고리즘의 경우 O(n²) 시간복잡도가 발생하지만 슬라이딩 윈도우 알고리즘을 사용하면 O(n)의 시간복잡도가 발생한다.

공식

ex) num[ ]에서 합이 최대인 k크기의 배열 찾기

1) 인덱스 0부터 인덱스 k-1 구간의 배열 요소들의 합을 초기화한다.

2) max에 초기화된 합을 할당한다.

3) num 배열 내에서 k크기의 구간의 요소들을 합을 구해 max와 비교한 후 더 큰 값을 max에 할당한다.

     - 슬라이딩 윈도우:  기존의 합에서 한 칸 우측의 인덱스의 요소를 더하고 해당 인덱스에서 구간의 크기만큼 뺀 인덱스의 요소를 빼면 윈도우를 한 칸 이동하는 것을 구현할 수 있다. 

import java.io.*;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(input.nextToken());
        int k = Integer.parseInt(input.nextToken());        
    	long sum = 0;        
        int[] num = new int[n];
        long max;
        
        //0~2까지의 구간의 합으로 초기화
        input = new StringTokenizer(br.readLine());
        for(int i = 0; i < k; i++) {
        	num[i] = Integer.parseInt(input.nextToken());
        	sum += num[i];
        }
        max = sum;
        
        //끝 인덱스를 size 인덱스부터 시작해서 윈도우 이동시켜 새 구간 형성
        for(int i = k; i < num.length; i++) {
        	num[i] = Integer.parseInt(input.nextToken());
        	sum = sum + num[i] - num[i - k];
        	if(sum > max)
        		max = sum;
        }
        System.out.println(max);
        
    }
}

그림 설명

합배열

정의

:  기존의 배열을 전처리한 배열

S[i] = A[0]  + A[1]   + A[2]   + A[3] + ··· + A[i-1]   + A[i]

시간 복잡도

: O(1)

- 합 배열을 미리 구해두면 구간 합을 O(1)의 시간복잡도로 계산할 수 있다.

공식

S[i] = S[i-1] + A[i]

class PrefixSum{
    private long[] sum;
    
   	//생성자
    PrefixSum(int[] arr){
    	sum = new long[arr.length];
        sum[0] = arr[0]; 
        for(int i = 1; i < arr.length; i++){
            sum[i] = sum[i-1] + arr[i];
        }
    }
}

필요성

: 합배열을 미리 구해놓으면 구간합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

=> 합 배열 미리 구해두면 구간 합은 한 번의 계산으로 구할 수 있다.

/*

합배열 없이 구간합 구하는 경우

- A[i]부터 A[j]까지 배열 합 구하기

최악의 경우: i = 0, j = N => 시간복잡도: O(N)

*/

구간 합

공식

: i~j까지 구간 합

S[j] - S[i - 1]

class PrefixSum{
    private long[] sum;
    
   	//생성자
    PrefixSum(int[] arr){
    	sum = new long[arr.length];
        sum[0] = arr[0]; 
        for(int i = 1; i < arr.length; i++){
            sum[i] = sum[i-1] + arr[i];
        }
    }
    
    //필요한 구간합 반환
    //s: 시작 인덱스, e: 끝 인덱스
    public long prefixSum(int s, int e){
    	//처음부터 시작하는 구간합
    	if(s == 0)
        	return sum[e];
            
        //특정 인덱스부터 시작하는 구간합
        return sum[e] - sum[s - 1];
    }
}

예시

: 인덱스 2~5까지의 구간 합

S[5] = A[0]  + A[1]   + A[2]   + A[3] + A[4] + A[5]

S[1] = A[0]  + A[1]

구간 합 = S[5] - S[1] = A[2]   + A[3] + A[4] + A[5]   => O(1)

Queue

: 데이터를 일시적으로 쌓아놓는 자료구조이다.

특징

- FIFO: 선입선출

- 단방향 구조

- 한 번에 데이터 한 개만 삽입, 삭제

- 버퍼, BFS 등에서 사용

구성요소

- Element: 데이터 요소

- Front: 맨 앞 요소의 인덱스로 물리적이 아니라 논리적인 데이터 순서

- Rear: 맨 뒤 요소의 하나 뒤 인덱스로 물리적이 아니라 논리적인 데이터 순서

선언

- java.util.Queue 클래스에서 제공한다.

//ex Integer 형
Queue<Integer> queue = new Queue<>();

데이터 추가

1. add();

- 성공: true 반환

- 실패: false 반환

- 큐가 꽉 찬 경우 IllegalStateException 발생

Queue<Integer> queue = new Queue<>();

queue.add(6);

2. offer();

- 성공: true 반환

- 실패: false 반환

- 큐가 빈 경우 NoSuchElementException 발생

- 큐가 꽉 찬 경우 fasle 반환

Queue<Integer> queue = new Queue<>();

queue.offer(6);

데이터 제거

1. remove();

- front 항목 반환 및 제거

- 큐가 빈 경우 null 반환

Queue<Integer> queue = new Queue<>();

queue.add(1);
queue.add(2);
queue.add(3);

queue.remove();

2. poll();

- front 항목 반환 및 제거

- 큐가 빈 경우 NoSuchElementException 반환

Queue<Integer> queue = new Queue<>();

queue.add(1);
queue.add(2);
queue.add(3);

queue.poll();

다양한 메서드

종류

1. 선형 큐(Linear Queue)

: FIFO의 특징을 갖는 기본 큐

주요작업

- Enqueue: rear에 항목 추가

- Dequeue: front에서 항목 제거

특징

- front: 삭제 연산만 수행

- rear: 삽입 연산만 수행

- FIFO

- Underflow, Overflow 발생 가능

단점

- Dequeue 시 front에 값이 없기 때문에 한 칸씩 값 이동시켜야 한다 => 시간 복잡도 ↑

// 이동시키지 않는 경우 공백이 삭제로 인해 공백이 발생한다. => 그냥 값이 빈다.

2. 원형 큐(Circular Queue)

: 선형 큐의 단점을 보완한 큐

주요작업

- 초기 상태: 빈 상태: front = -1, rear = -1, 배열 크기 = n

- 첫 번째 Enqueue: front = -1, rear = 0 => front = 0, rear = 0

- 그 이후의 Enqueue: rear에 항목 추가, rear 포인터 + 1

- Dequeue: front에서 항목 제거, front 포인터 + 1

- 마지막 Dequeue: front = rear => front = rear = -1

특징

- 큐 다 차지 않는 이상 무한으로 데이터 삽입 삭제 가능

- 메모리 효율적으로 사용 가능

단점

- 초기화 시점에 배열 크기 결정해서 동적으로 크기 조절이 불가하다

3. 우선순위 큐(Priority Queue)

: 먼저 들어온 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 구조

- 힙으로 구현한다.

- 비선형 자료구조이기 때문에 다른 게시글에서 설명하겠다.

4. 데 큐(De Queue)

: 양 끝이 front이자 rear인 구조

특징

- Stack과 Queue의 장점을 갖고 있다.

- FIFO, LIFO 유연하게 지원한다.

- 양쪽에서 data를 삽입, 삭제가 가능하다.

     - front

          - addFirst()

          - offerFirst()

     - rear

          - addLast()

          - offerLast()

Stack

: 데이터를 일시적으로 쌓아놓는 자료구조이다.

특징

- LIFO: 후입선출

- 단방향 구조

- 한 번에 데이터 한 개만 삽입, 삭제

- 스택이 비었을 때 pop() 또는 peek()를 호출할 시 EmptyStackException 발생

- DFS 등에서 사용

구성요소

- Element: 데이터 요소

- Top: 가장 최근에 들어온 데이터의 위치로 데이터의 추가, 삭제가 이뤄지는 지점

- Bottom: 가장 먼저 들어온 데이터의 위치로 스택의 가장 아래 지점 

선언

- java.util.Stack 클래스에서 제공한다.

//ex Integer 형
Stack<Integer> stack = new Stack<>();

데이터 추가

- push();

- 값 추가 및 반환

- 스택 비어있을 시 EmptyStackException 반환

Stack<Integer> stack = new Stack<>();

stack.push(6);

데이터 제거

- pop();

- 가장 상단 값 반환 및 제거

- 스택 비어있을 시 EmptyStackException 반환

Stack<Integer> stack = new Stack<>();

stack.push(1);
stack.push(2);

stack.pop();// 2제거
stack.pop();// 1제거

다양한 메서드

EmptyStackException

- Stack이 비어있는 상태에서 pop() 또는 peek()를 호출하면 EmptyStackException이 발생한다.

Stack 클래스 사용 지양

이유

: Vector 클래스는 구현된지 오래된 클래스라 취약점이 많다.

Stack 클래스는 Vector 클래스를 상속받아 구현된 클래스로 부모 클래스가 취약점이 많은 문제에 따라

자식클래스인 Stack 클래스도 불안정해지는 문제가 발생한다.

예시

- Vector 클래스의 add()를 사용할 수 있어 Stack의 의도와 다르게 사용할 수 있는 문제가 발생한다.

Stack<Integer> stack = new Stack<>();

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);

stack.add(2, 6); //Vector 클래스의 add() 사용 가능 => 특정 인덱스에 6을 추가할 수 있게 됨
System.out.println(stack.pop()); //마지막에 넣은 값인 6이 아니라 5가 출력됨

*해당 게시물은 배열을 검색할 때를 기준으로 한다.

선형 검색(순차 검색)

: 원하는 키값을 갖는 요소를 만날 때까지 앞에서부터 차례로 검색한다.

- 사용: 무작위로 늘어서 있는 데이터 모임에서 검색한다.

- 종료조건: 검색 성공 | 검색 실패 => 2개

     - 문제: 종료 조건 검사 비용을 무시할 수 없다

     - 개선: 보초법 

          - 맨 끝에 검색하고자 하는 키값을 저장하는 보초를 둔다.

          - 검색 성공 조건만 판단한다

          - 검색값이 보초인 경우 검색 실패를 나타내는 조건을 필요하다.

     - 결과: 조건 검사 비용 50% 감소

- 시간복잡도: O(n)

이진 검색

: 일정한 규칙으로 늘어서 있는 데이터 모임에서 효율적으로 검색한다.

- 사용: 정렬되어 있는 데이터 모임에서 검색한다.

- 특징: 검색할 요소의 범위가 절반씩 줄어든다. 

- 시간복잡도: O(log n)

static int binarySearch(int[] a, int n, int key){
	int start = 0;	//검색 범위의 첫 인덱스
    int end = n - 1;	//검색 범위의 마지막 인덱스
    
    do{
    	int middle = (start + end) / 2;	//검색 범위의 중간 인덱스
    	if(a[middle] == key)
        	return middle;
        else if(a[middle] < key)
        	start = middle + 1;
        else	//a[middle] > key
        	end = middle - 1;
    }while(start <= end);
    
    return -1;	//검색 실패
}

//java에서는 binarySearch 메서드를 제공한다.

//static int binarySearch(배열, 키)     자료형 관계없이 사용가능하도록 오버로딩 되어 있다.

//제네릭: static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

Linked List(연결 리스트)

구현

1. 연결 리스트 

import java.util.Comparator;

//연결 리스트 클래스
public class LinkedList<E>{

	// Node클래스
	class Node<E>{
    	private E data;	// 데이터
        private Node<E> next;	// 다음 노드 참조
        
    	// Node클래스 생성자
    	Node(E data, Node<E> next){
    		this.data = data;
        	this.next = next;
    	}
        
    }
    
    
    private Node<E> head;	// 머리 포인터: 머리 노드를 가리킴
    private Node<E> crnt;	// 선택 포인터: 현재 선택한 노드를 가리킴

	//연결 리스트 생성자
	public LinkedList(){
    	//head: 빈 연결 리스트는 노드가 없고 head가 가리킬 곳도 없기 때문에 null을 넣음
        //crnt: 어떤 요소도 선택하지 않게 하기 위해 null을 넣음
    	head = crnt = null;
	}


	//검색, 삭제, 삽입 등의 메서드
}

2. 메서드 구현해보기(포인터 이용)

2-1. 검색 메서드

: 검색하는 노드 만날 때까지 머리 노드부터 순서대로 스캔

1) 매개변수

- E obj: 검색 시 키가 되는 데이터 넣어 둔 객체

- Comparator<? super E> c: obj와 노드 안의 데이터를 비교하기 위한 Comparator

     - Comparator<T>: 함수형 인터페이스로 int compare(T t1, T t2)메서드로 두 객체를 비교해 정수, 0, 또는 양수 반환

     - 와일드카드 ?: 제네릭에 들어올 수 있는 어떤 타입이든 지정할 때 쓰는 미지 타입

     - ? super E: 하한 경계로 E 타입 또는 E의 슈퍼타입을 의미

          ex) Comparator<Animal>은 Comparator<? super Dog>에 할당 가능

     => E 타입의 값과 비교할 수 있는 c면 뭐든 비교 허용

          ex) E가 Integer라면 Number, Object를 허용

2) 분석

      1. 스캔 노드 참조 변수 ptr을 head로 초기화 - 머리노드

      2. 스캔할 노드가 있는 지 확인

      3. 데이터 obj와 스캔 중인 노드의 데이터 ptr.data를 Comparator c로 비교

           3-1. compare 메서드가 0을 반환하면 종료 및 검색 성공     // 찾고자 하는 값 == 스캔 중인 노드의 값

           3-2. 선택 포인터가 ptr.data를 반환

      4. obj와 ptr.data가 일치하지 않으면 ptr에 ptr.next를 대입해 ptr이 다음 노드를 가리키도록 함

      5. 검색 실패 시 null 반환

3) 시간복잡도: O(n)

public E search(E obj, Comparator<? super E> c){
	Node<E> ptr = head;	//현재 스캔 중인 노드
    
    while(ptr != null){
    	if(c.compare(obj, ptr.data) == 0){	//검색 성공
        	crnt = ptr;
            return ptr.data;
        }
        ptr = ptr.next;	//다음 노드 선택
    }
    return null;	//검색 실패
}

2-2. 삽입 메서드

1) 머리에 노드 삽입하는 메서드

public void addFirst(E obj){
	Node<E> ptr = head;
    head = crnt = new Node<E>(obj, ptr);
}

2) 꼬리에 노드 삽입하는 메서드

      1. 리스트 스캔

      2-1) 리스트가 빈 경우: addFirst(obj);

      2-2) 리스트가 안 빈 경우: 리스트를 순회하여 ptr이 꼬리노드를 가리킬 때 반복문에서 나와 노드를 삽입한다.

public void addLast(E obj){
	if(head == null)
    	addFirst(obj);
    else{
    	Node<E> ptr = head;
        while(ptr.next != null)
        	ptr = ptr.next;
        ptr.next = crnt = new Node<E>(obj, null);
    }
}

2-3. 삭제 메서드

- 해제라고 생각하면 좋을 것 같다

1) 머리노드 삭제하는 메서드

public void removeFirst(){
	if(head != null)//리스트 안 빔
         head = crnt = head.next;
}

2) 꼬리노드 삭제하는 메서드

      1. 리스트 스캔

      2-1) 리스트에 노드가 1개인 경우: removeFirst();        //노드가 1개인 리스트라면 head에 null을 대입하면 빈 상태가 된다.

      2-2) 리스트에 노드가 2개 이상인 경우: pre가 꼬리 앞 노드를 ptr이 꼬리노드를 가리키면 pre의 next에 null을 대입한다.

public void removeLast(){
	if(head != null)
    	if(head.next == null)
        	removeFirst();
    else{
    	Node<E> ptr = head;
        Node<E> pre = head;	//ptr의 앞쪽 노드
        while(ptr.next != null){
        	pre = ptr;
        	ptr = ptr.next;
        }
        pre.next = null;
        crnt = pre;
    }
}

3) 선택한 노드 삭제하는 메서드

- 삭제할 노드 p가 머리 노드면 removeFirst()

public void remove(Node p){
	if(head != null){
    	if(head.next == null)
        	removeFirst();
        else{
            Node<E> ptr = head;

            while(ptr.next != p){
                ptr = ptr.next;
                if(ptr == null)//리스트에 p가 없음
                    return;
            }
            ptr.next = p.next
            crnt = ptr;
        }
    }
}

4) 모든 노드 삭제 메서드

- 머리노드 반복 삭제

public void clear(){
	while(head != null){
    	removeFirst();
    }
    crnt = null;
}

Sequential List

: 데이터들을 논리적인 순서대로 메모리에 연속해 저장하는 구조이다.

종류

1. Array

2. ArrayList

Array

: 크기가 고정되어있는 고정 길이 배열 구조이다.

특징

- 고정된 크기를 가진다.

- 메모리 구조 단순하다.

- 인덱스를 통해 검색한다: O(1)

- 삽입, 삭제 시 추가작업 필요하다(원소 이동 비용 발생): O(n)     // 삽입, 삭제 연산 늘어날수록 연산 시간 증가

삽입

: 삽입할 자리를 만들고 삽입한다.

- 원소 옮기는 추가작업 필요

삭제

: 원소 삭제 후 삭제한 원소 뒤의 요소들을 앞으로 옮긴다.

- 원소 옮기는 추가작업 필요

검색

: 인덱스를 통해 원소를 탐색한다.

- 추가 작업이 불필요

ArrayList

: 크기를 자동으로 늘릴 수 있는 동적 배열 구조이다.

특징

- 인덱스를 통해 검색한다: O(1)

- 크기를 자동으로 조정할 수 있다(복사 비용 발생): O(n)

- 삭제 시 추가작업 필요하다(원소 이동 비용 발생): O(n)     // 삽입, 삭제 연산 늘어날수록 연산 시간 증가

- 중간 삽입 시 추가작업 필요하다(원소 이동 비용 발생): O(n) 

- 끝에 삽입 시 공간 여유가 있으면 O(1), 없으면 resize로 인해 복사 비용(O(n)) 발생한다.

더블링

:내부적으로 배열이 다 차게 되면 배열의 크기를 두 배로 늘리고 기존 데이터를 복사한다.

시간 복잡도 비교

// n = 데이터 개수

자료구조

정의: 데이터의 자료를 조직화하고 정리하는 데이터 구조이다.

필요성: 컴퓨터가 대량의 복잡한 정보를 처리하는 것을 용이하게 하기 위해 필요하다. 

- 코드를 더 단순하게 하고 효율성을 높일 수 있다.

분류

1. 선형구조(Linear data structure)

: 데이터들이 일렬로 저장된 구조

종류

- 순차 리스트

- 연결 리스트

- 스택

- 큐

2. 비선형구조(Linear data structure)

: 데이터들이 일렬이 아닌 형태로 저장된 구조

종류

- 트리

- 그래프