|  요약

종류 구분 내용 언제 쓰는 게 좋을까
HashTable 특징 - 해싱 함수를 통해 키 -> 해시로 변환한다
- key + value
- 특정 키와 값을 연결할 때(알파벳-단어, 사전, 전화번호부)
- 중복을 제거해야할 때(전체 명단 중 투표 여부 확인)
장점 - 해시 충돌이 없을 때 검색, 삽입, 삭제가 빠르다
  (시간복잡도 : 평균 O(1), 최악 O(n))
- 보안성이 높다 (Key와 Hash간의 연관성X)
- 데이터 캐싱에 자주 사용된다.
- 중복 제거에 유리하다.
단점 - 해시 충돌 : key1과 key2가 해시함수를 거쳐 동일한 해시값(공간)을 가지는 상태
- 공간 복잡도가 커진다
- 순서가 있는 경우에는 맞지 않는다
- 해시 함수 의존도가 높다

- 해시 테이블은 키와 값을 대응시켜 저장하는 구조로, 키를 통해 빠르게 값을 찾을 수 있다는 장점을 가진다.

- 단순히 [ 키 : 값 ] 로 대응시키는 것이 아니라 "해싱"을 통해 키를 변환시킨다.

- 일상생활에서 해시 테이블은 구매내역이나 To-do 체크리스트, 그리고 영어사전에서도 볼 수 있다. 

 


물품 - 가격이 매칭


체크박스 - 한 줄 문자열 매칭

단어 - 뜻이 매칭
출처 : https://witchform.com/ 출처 : https://www.yesform.com/ 출처 : https://gonggam.korea.kr/

 

|  해시함수와 해시값 그리고 해시 충돌

1. 해싱이란?

키를 해시 함수(어떤 계산식)를 통해서 바꾸어 값에 접근하도록 하는 과정

- 키 : 입력값 -> 해시 함수 : 키를 해시 값으로 매핑 -> 해시 값 : 해시 테이블의 인덱스 -> 해시 테이블 : 키-값 저장하는 구조

키(keys) 해시 함수(Hash Function) 해시 값(Hash Value) 해시 테이블(Hash Table)
int key1 = 0 key % table.length(3) 0 100
int key2 = 10 1 200
int key3 = 20 2 300

 

2. 해시 충돌이란? 

서로 다른 키에 대한 해시 값이 동일한 경우, 같은 공간에 값을 저장하게되는 충돌이 발생하는 것.

* 위의 표에 키를 하나 더 넣어서 해시 충돌을 임의로 일으켜 보자.

키(keys) 해시 함수(Hash Function) 해시 값(Hash Value) 해시 테이블(Hash Table)
int key1 = 0 key % table.length(3) 0 100
int key2 = 10 1 200
int key3 = 20 2 300
int key4 = 30 0 400

서로 다른 키 값 0과 30의 해시 값, 곧 인덱스가 0으로 동일하다. 이렇게 될 경우, 새로 들어간 400이 0자리에 덮어써진다.

 

|  해시 충돌을 해결하는 방법

- 해시 충돌을 해결하는 방법은 구글을 검색했을 때 정말 많이 나왔는데, 그 중에서도 대표적으로 크게 두 가지,

[1] 개방 주소법 [2] 분리연결법 를 이야기하려고 한다.

개방주소법(Open Address) 비어 있는 공간을 찾아서 데이터를 저장하는 방법

- 하나씩 찾는다면? 선형 탐사법
- +n^2씩 찾는다면? 제곱 탐사법
- 해시 함수를 하다 더 쓴다면? 이중 해싱
분리연결법(Separate Chaining) 해시 테이블을 연결 리스트로 구성하는 방식

- 배열 + 연결리스트의 느낌
- 키의 해시 값(인덱스) - 연결리스트

해시값 연결리스트
a 0 amanda avril agatha aeron
b 1 bob billy    
c 2 chris caeser carl  
d 3 dominic      

 

1. 개방주소법

- 해시테이블을 구현한 클래스 MyHashtable이 있다고 하자. 

- 나머지는 다 생략하고 해시 함수만 놓고 보았을 때 클래스 내 코드는 아래와 같은 상태일 것이다.

- 이 상태에서 개방주소법의 여러가지 종류, 선형탐사법, 제곱탐사법, 이중해싱을 다뤄보려 한다.

class MyHashTable{

    Integer table[];

    // 해시 함수
    public int getHash(int key) {
        return key % this.table.length;
    }
}

 

[1] 선형 탐사법 (Linear Probing)

: 충돌이 난 지점부터 +1를 하여 값이 없는 곳에 값을 넣는다.

- 코드를 보면 좀 더 이해하기 쉬울 것 같다.

- 아래 코드에서 보면 else 부문 안에 충돌 지점부터 배열의 인덱스를 하나씩 올리는 걸 볼 수 있다. 이처럼 선형탐사법은 사실상 배열의 인덱스값을 하나씩 올려주면서 배열의 빈 공간을 찾아 순회하는 걸 말한다.

class MyHashTable{

    Integer table[];

    // 해시 함수
    public int getHash(int key) {
        return key % this.table.length;
    }
    
    // 선형 탐사법 : 충돌난 지점부터 +1을 해서 비어있는 곳을 찾는다.
    public void put(int key, int value) {
        int idx = getHash(key);
    
    	if (this.isFull()){
            System.out.println("it is full!");
            return;
        } else if (this.table[idx] == null){
            this.table[idx] = value; // 키의 해시값(인덱스)에 값이 없으면 넣기
        } else {
            int newIdx = idx;
            while (true) { // 충돌지점부터 +1하여 값이 없는 곳 찾기 
               newIdx = (newIdx + 1) % this.table.length; 
               if (this.table[newIdx] == null) {
                  break;
               }
            }
            this.table[newIdx] = value;
        }
    }
}

- 단점 : 일차 군집화 문제가 발생할 수 있다.

- 일차 군집화는 뭘까?

충돌이 발생했던 지점에서 +1을 해서 비어있는 곳을 찾다보면, 충돌된 지점의 주위로 어느새 데이터들이 몰리는 현상이 발생한다. 이런 상황을 일차 군집화라고 한다. 

 

[2] 제곱 탐사법 (Quadratic Probing)

: 충돌이 난 지점부터 n^2만큼의 간격을 두고 탐사하는 방법이다.

- 단점 : 이차 군집화 문제

- 이차 군집화란, 특정 구간에 데이터가 몰리는 현상이 이차적으로 발생한다는 의미이다. 일차 군집화와 의미는 거의 비슷한데 발생 시점이 두번째라는 게 차이라 보인다.

* 위의 코드에서 else {} 지점만 빼서 수정한다면 아래와 같다.

class MyHashTable{

    /* 생략 */
    
    // 제곱 탐사법 : 충돌이 난 지점부터 n^2로 탐사
    public void put(int key, int value) {
        
        /* 생략 */
        
        } else {
            int newIdx = idx;
            int n = 1;
            while (true) { 
               newIdx = (newIdx + (int)Math.pow(n, 2)) % this.table.length; 
               if (this.table[newIdx] == null) {
                  break;
               }
               n++;
            }
            this.table[newIdx] = value;
        }
    }
}

 

[3] 이중 해싱 (Double Hashing)

- 말이 참 어려운데 풀이하면 해싱을 한 번 더 하겠다는 의미이다.

- 첫번째 해시함수로는 최초의 해시(인덱스)를 구하고, 충돌이나면 두번째 해시함수로 이동 간격을 잡고 빈 곳을 찾는다.

- 마찬가지로 아래 코드를 보면, 해싱을 두번 하는 코드가 나오는 걸 볼 수 있는데, 두번째의 해싱에서는 해시테이블의 크기보다 조금 작은 소수를 통해 해시값을 %해주고, 거기에 다시 *1, *2, *3..을 하는 방식으로 이중해싱을 하는 걸 볼 수 있다. 이러한 방식으로 하다보면, 선형 탐사나 제곱 탐사보다는 데이터가 골고루 분포된다.

class MyHashTable{

    char p; // Hashtable의 size 보다 조금 작은 소수
    
    /* p를 구하는 함수 생략 */
    
    // 해시 함수1 - 최초 해싱
    public int getHash(int key) {
        return key % this.table.length;
    }
    
    // 해시 함수2 - 충돌 시 2차 해싱
    public int getHash2(int key) {
        int hash = 1 + key % this.p;
        return hash % this.table.length;
    }
    
    // 이중 해싱 : 충돌이 난 지점에서 2차 해싱
    public void put(int key, int value) {
        
        /* 생략 */
        
        } else {
            int newIdx = idx;
            int cnt = 1;
            while (true) { 
               newIdx = (newIdx + getHash2(newIdx) * cnt) % this.table.length; 
               if (this.table[newIdx] == null) {
                  break;
               }
               cnt++;
            }
            this.table[newIdx] = value;
        }
    }
}

 

2. 분리 연결법

- 충돌이 발생했을 때, 동일한 버킷(Bucket - 지점)에서 연결리스트 형태로 데이터를 연결하는 방식

- 위에서도 표로 잠깐 보여주었던 것처럼 충돌지점에 데이터를 이어 붙이는 걸 볼 수 있다.

https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

- 이번에는 구현 코드보다 자바 라이브러리로 분리 연결법을 사용할 때를 예를 들어보려고 한다.

// 분리연결법을 사용한 경우1 : 이름을 연결할때
// ex. a - amanda, avril, aeron...
Hashtable<String, LinkedList<String>> nameTable = new Hashtable();

// 분리연결법을 사용한 경우2 : (이름, 전화번호)를 담는 2차 배열을 연결할 때
// es. a - (amanda, 123-234-2342), (avril, 123-234-2213)...
Hashtable<String, LinkedList<ArrayList<String>>> phoneTable = new Hashtable();

 

|  Java 해시맵과 해시테이블의 차이점

  HashTable HashMap
공통점 두 클래스 모두 Map인터페이스를 구현했다.
차이점 key에 null 사용하지 않음 key에 null 사용
Thread-Safe (멀티 스레드 환경에서 우수) Thread-Safe X (싱글 스레드 환경에서 우수)

* 참조 : 멀티스레드용 HashMap이 별도로 있다 -- synchronizedMap, ConcurrentHashMap 

 

++ 유용하게 쓸만한 HashMap 메소드 - putIfAbsent(), getOrDefault()

// HashMap의 getOrDefault()
int[] nums = {3, 2, 1, 1, 2, 3, 5};
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
	// getOrDefault(key, defaultValue) - val가 있으면 val가져오고, 아니면 default로 세팅
    map.put(num, map.getOrDefault(num, 0) + 1); 
}

HashMap<Character, Node> map2 = new HashMap<>();
String word = "apple";
for (int i = 0; i < word.length(); i++) {
    char c = word.charAt(i);
    // putIfAbsent(key, val) : key가 없으면 val생성하고, 있으면 넘어간다.
    map2.putIfAbsent(c, new Node());
}

 

|  해시 관련 문제집

https://school.programmers.co.kr/learn/courses/30/parts/12077

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

[ 참고 ] 

https://hbase.tistory.com/185

위키백과 https://en.wikipedia.org/wiki/Hash_table#Separate_chaining

https://baeharam.github.io/posts/data-structure/hash-table/

https://velog.io/@roro/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94

|  스택

종류 구분 내용 언제 쓰는 게 좋을까
Stack 특징 - 후입선출(LIFO)
- top / bottom
- push, pop, peek 
- 데이터가 입력된 순서의 역순으로
  처리되어야 할 때
Ex.
- 함수 콜스택,역추적,인터럽트 처리
- 재귀, DFS
- 괄호 검사, 후위 연산, 문자열 역순출력, 실행취소
장점 - top을 통한 접근, 삽입, 삭제가 빠르다.
  (시간복잡도 O(1))
단점 - top 이외의 데이터에 접근 불가(탐색x)

- 스택은 마치 옷을 겹겹히 쌓듯 데이터를 쌓아 올렸다가 맨 위에서부터 꺼내는 구조이다.

- 스택에 대한 알고리즘 문제를 보면, "괄호 검사", "후위 연산", "문자열의 역순 출력", "실행 취소"와 같이 

  [ 넣었다가 위에서부터 빼는 행위 ]를 통해 문자열의 특정 문자를 검사하고, 어떤 행위를 역전 시키는 걸 볼 수 있다.

- 일상 생활에서 볼 수 있는 또다른 스택의 예시는, 제가 좋아하는 프링글스...위에서부터 뽑아먹는 재미가...

 

https://www.acmicpc.net/workbook/view/325

 

문제집: 스택 (kmg8280)

 

www.acmicpc.net

 

|  큐

종류 구분 내용 언제 쓰는 게 좋을까
Queue 특징 - 선입선출(FIFO)
- front / rear 
- enqueue(offer, add), dequeue(poll, remove) 
- 데이터를 순차적으로 삽입하고 꺼낼 때
Ex.
- 요세푸스 순열, 프로세스 관리, 대기 순서 관리(프린트 대기열)
- BFS
장점 - front/rear를 통한 접근, 삽입, 삭제가 빠르다.
  (시간복잡도 O(1))
단점 - 중간 위치의 데이터에 접근 불가

- 큐는 스타벅스 앞에 줄을 서고 있는 사람들처럼 먼저 들어간 데이터가 먼저 빠지는 구조이다.

- 원형 큐는 원형 연결리스트와 구조적으로 동일하다. 앞과 끝은 있으나 그걸 원형으로 벤딩해놓은 형태. 

  (자바에서는 그러나 원형 큐도 딱히 지원하지 않기 때문에 차라리 데크를 쓰는 편이 수월한 것 같다.)

- 자바에서는 큐는 인터페이스로 제공하고, 큐를 구현하는 객체를 쓸 수 있는데, LinkedList를 쓰면 된다.

- 한 가지 알아두어야 할 점은, 큐에 데이터를 삭제할 때

   poll()를 쓰면 데이터가 없어도 null을 반환하지만,

   remove()를 쓰면 데이터가 없을 때 예외가 발생하기 때문에, 안전성을 위해서 remove()를 쓰는 게 더 좋다는 것!

 

https://www.acmicpc.net/workbook/view/1504

 

문제집: Queue (jhlee1108)

 

www.acmicpc.net

 

|  데크

종류 구분 내용 언제 쓰는 게 좋을까
Deque 특징 = double-ended queue, stack + queue
- 양쪽에서 삽입 삭제가 가능
- front / rear
- add(offer), remove(poll) 
- addFirst, addLast, removeFirst, removeLast
- 데이터를 앞, 뒤쪽에서 삽입/삭제 처리 필요할 때

Ex.
팰린드롬 찾기, 카드묶음의 순서 변경하기 등
장점 - front / rear 양쪽을 통한 삽입, 삭제가 빠르다 
  (시간복잡도 O(1))
- Stack, Queue와 달리 idx를 통해 임의 원소에 접근 가능
- 새로운 원소 삽입 시 메모리를 재할당하지 않고 메모리 블록을 재할당하여 삽입한다.(chunk 사용)
단점 - 중간 위치에 데이터를 삽입, 삭제가 어렵다
Scroll - 입력제한 데크
- 한 쪽의 입력을 제한한 데크
Shelf - 출력제한 데크
- 한 쪽의 출력을 제한한 데크

- 데크는 마치 양 옆이 열린 파이프와 같은 형태라고 생각하면 쉬운 것 같다.

- 양쪽에서 데이터를 삽입하고 삭제할 수 있으며, 필요에 따라 양 옆을 제한 시켜 사용할 수도 있다.

- 데크 또한 큐와 마찬가지로 삭제를 할 때, remove()를 쓰는 것이 안전성의 측면에서 더 좋다. 

 

|  자바 컬렉션의 시간 복잡도

1. Queue

  offer() peak() poll() size()
LinkedList O(1) O(1) O(1) O(1)
ArrayDequeue O(1) O(1) O(1) O(1)
PriorityQueue O(log n) O(1) O(log n) O(1)

 

2. Stack

  push() peek() pop() size()
Stack O(1) O(1) O(1) O(1)

 

|  요약

종류 구분 내용 언제 쓰는 게 좋을까
LinkedList


특징 - 각 노드가 연결된 상태
- 각 노드의 메모리 주소는 항상 연속적이지 않다.
- head / tail (양방향 이상)
- 자료의 삽입과 삭제가 많은 경우
장점 - 데이터의 삽입 및 삭제가 잦을 때 유리
  * 삽입, 삭제 시 새로운 배열 생성 없이 링크만 연결한다.
단점 - 특정 인덱스를 조회하는 데 시간이 O(n)만큼 소요된다.
  * 처음~끝까지 인덱스를 돌기 때문에 Array보다 느리다.
양방향 - 각 노드가 prev / next 두 가지의 연결점을 가진다.
원형 - head -> tail -> head 식으로 원형으로 연결된 상태

- 연결리스트는 각 노드가 연결된 상태로, 삽입과 삭제가 용이하다.

- 다만, 연결리스트는 조회에는 취약한데 그 이유는 처음부터 노드를 순회해야 원하는 타켓을 조회할 수 있기 때문이다.

 

|  단방향 연결리스트, 양방향 연결리스트, 원형 연결리스트

- 연결리스트는 기본적으로 각각의 노드가 데이터와 포인터를 가진 구조로 되어있다.

- 단방향 연결리스트는 아래와 그림과 같이 각 노드가 next 포인터를 통해 한 방향으로만 연결된 구조인데

  이러한 구조에서는 head노드가 있고, tail은 없는 상태이다.

- 양방향 연결리스트는 아래의 두번째 그림과 같이 각 노드에 prev, next 포인터가 각각 있는 상태를 말한다.

  이 구조에서는 head 노드도 있으며, tail 노드도 존재한다.

  왜냐하면, 각각의 노드 뿐 아니라 전체적인 방향 자체가 양방향이기 때문에 tail이 필요하기 때문

- 원형 연결리스트는 tail 노드의 next가 head를 향하고 있는 상태로, 결과적으로 리스트를 순회하는 구조이다.

  만약, 양방향 연결까지 더해준다면 시계방향, 반시계방향 모두로 순회가 가능하다.

 

단방향 양방향 원형

* 이미지 출처 : 위키 백과

 

|  연결리스트의 시간 복잡도

- 연결리스트의 삽입과 삭제는 O(1) 의 시간 복잡도를 갖는다. 

  단순히 노드 사이에 연결만 이루어지면 되기 때문이다.

- 하지만 조회시에는 O(n)의 시간복잡도를 갖는다는 단점이 있다.

  배열과 같이 인덱스가 있는 것이 아니라 노드의 head부터 타겟지점까지 모두 순회해야 하기 때문이다.

  add() remove() get() contains()
ArrayList O(1) or O(n) O(1) or O(n) O(1) O(n)
LinkedList O(1) O(1) O(n) O(n)

 

|  연결리스트와 큐, 데크

- 연결리스트는 큐와 구조적으로 동일하다고 볼 수 있는데, 이유는 큐와 마찬가지로 선입선출이 가능하기 때문이다.

- 자바에서는 Java.util 라이브러리의 LinkedList를 통해 연결리스트를 사용할 수 있으며, 단방향연결리스트만 제공한다.

- 만약, 양방향 연결리스트가 필요한 경우, Doubly-LinkedList를 별도로 구현하거나 단방향을 활용하는 게 필요하다.

- 만약, 원형 연결리스트가 필요하다면, Deque를 대안적으로 사용할 수 있다.

 

|  연결리스트 문제집

https://www.acmicpc.net/workbook/view/1066

 

문제집: Linked List (DryType)

 

www.acmicpc.net

 

 

[ 참고 ] 

https://hbase.tistory.com/185

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

|  요약

종류 구분 내용 언제 쓰는 게 좋을까
Array 특징 - 정해진 크기만큼 공간 할당
- 데이터가 연속적으로 하나씩 저장되어 있다.
- 데이터와 인덱스가 1 : 1로 매칭
- 많은 양의 데이터를 다룰때
- 특정 위치 자료를 빠르게 선택할때
장점 - 인덱스를 통해 빠르게 데이터에 접근할 수 있다.
단점 - 길이를 미리 설정해야 한다.
ArrayList 특징 - 가변 길이 배열
- 삽입 & 삭제 시, 배열을 새로 생성하고 복사한다.
장점 - 크기가 고정되어 있지 않다 (유동적)
단점 - 처음 또는 중간에 데이터를 삽입하거나 삭제할 때마다
  배열을 새로 생성&복사하거나,
  데이터를 모두 앞으로 미뤄야 한다. 

 

|  ArrayList은 어떻게 가변적으로 데이터를 관리하나

- ArrayList는 java.util 패키지 안에 들어있다.

- 예전에는 Vector라는 객체를 통해 ArrayList를 사용했는데, 버전이 높아지면서 향상된것이 ArrayList이다.

- ArrayList는 사실상 배열인데,

  공간 제약 없이 데이터를 삽입하고 추가하면서 배열 길이가 늘어나고 감소하도록 한 가변배열이다.

 

더보기

  1. ArrayList는 사실상 배열이고, 데이터가 늘어날 때마다 배열을 새로 만든다.  

자바 라이브러리에 들어있는 ArrayList 코드를 분석해보면 아래와 같았다.

[1] ArrayList의 디폴트 길이 10 - 그렇지만 중요한 건 실제 데이터의 양

처음 ArrayList를 생성할 때 디폴트 길이(size)는 10으로 되어 있는 걸 볼 수 있는데,

말만 디폴트이지, 생성과 동시에 데이터를 아무것도 넣지 않았다면 메모리상 실제 ArrayList의 길이는 0이다.

private static final int DEFAULT_CAPACITY = 10; //디폴트 길이

private static final Object[] EMPTY_ELEMENTDATA = {}; // 아무것도 안 들어가있다.

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 아무것도 안 들어가있다.

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA; // 아무것도 안 들어가있다.
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 아무것도 안 들어가있다.
}

>> 그렇다면 아래 코드에서 사이즈는 몇일까?

ArrayList<Integer> list = new ArrayList<>(10);
list.add(1);
list.add(2);
System.out.println(list.size());

>>> 답은 2.

-- 초기값을 지정해준다고 해도, 중요한 건 실제 데이터의 양이었다.

-- 결국 size는 지정해줘봤자 실제로 데이터가 들어간 만큼만 나온다.

-- 그런데도 지정해주는 이유는 뭘까? 이유는 ArrayList 크기를 미리 지정해두는 게, 계속해서 배열을 생성하고 복사하는 과정을 줄일 수 있기 때문이다. 

 

[2] 길이의 자동 변경? - 사실은 새로운 크기의 배열을 생성하고 기존걸 복사하는 것

- 아래 java.util.ArrayList의 add(E e, Object[] elementData, int s) 코드를 보면, 

- 배열 공간을 넘어설 때, Arrays.copyOf(T[] original, int newLength)로 결국 배열을 새로 생성하는 걸 볼 수 있다. 

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow(); //아래의 grow()를 보자
    elementData[s] = e;
    size = s + 1;
}
    
private Object[] grow(int minCapacity) { 
    return elementData = Arrays.copyOf(elementData, // 결국 배열을 또 만든다
                                       newCapacity(minCapacity));
}

 

  2. ArrayList의 데이터를 추가하고 삭제할때  

[1] 데이터를 추가할 때

- 1-[2]에서 본 것처럼 배열은 데이터를 추가할 때 공간(크기)을 벗어나면 새로운 배열을 생성하고, 복사한다.

위치 배열 길이 벗어나지 않을 때 배열 길이 벗어날 때
처음 또는 중간 우측의 2) - 3)만  1) 길이 + 1의 배열 생성
2) 처음 ~ 이전 끝까지 복사
3) idx + 1부터 이전 배열의 idx ~ 끝까지 복사  
우측의 2) - 3)만  1) 길이 + 1의 배열 생성
2) 처음 ~ 이전 끝까지 복사
3) 끝에 새로운 데이터 추가
// 끝에 삽입 시 : 배열 새로 생성 + 처음부터 끝까지 복사 + 새 데이터 추가하기
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow(); //배열 새로 생성 + 복사
    elementData[s] = e; //끝에 새로운 데이터 추가
    size = s + 1;
}

// 중간 삽입 시 : 배열 새로 생성 + 특정 index ~ 끝까지 복사 + 새 데이터 끼우기
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow(); //배열 새로 생성 + 복사
    System.arraycopy(elementData, index, //넣을 자리부터 ~ 끝까지 데이터를 
                     elementData, index + 1, //넣을 자리 + 1 위치에 
                     s - index); //전체 사이즈에서 넣을 자리 뺀만큼 복사
    elementData[index] = element; //넣을 자리에 새로운 데이터 넣기
    size = s + 1;
}

 

[2] 데이터를 삭제할 때

시작하기 전에 잠시 전급하자면 ArrayList의 배열 타입은 Object[]이다.

- ArrayList를 쓸 때 정수형 데이터(int)를 boxing해야하는 경우들이 있었다.

- 예를 들어, 배열스트림-->List로 변경할때, Arrays.stream(arr).boxed().collect(Collectors.toList()) 

- 그 외에도, forEach문을 쓸 때 때때로 boxing을 해줄 때가 있었는데, 그 이유는 ArrayList의 배열 타입이 Object[]여서 였다.

 

이제 다시 데이터 삭제로 돌아가자.

ArrayList에서 "삭제"란 데이터를 실제로 "없앤다"기 보다는 "참조값(주소)"를 바꾸는 걸 얘기한다

>> 예를 들어, 중간 데이터를 삭제할 때는 중간 데이터 이후부터 데이터들을 앞으로 미루고,

>> 마지막 인덱스를 null로 바꿔주는 걸 볼 수 있다.

 

참고로 데이터를 삭제할 때에는 인자로 null 값까지도 확인을 하는데, null을 삭제해달라 요청하면 true를 반환한다.

위치 방법
처음 또는 중간 1) 삭제하려는 데이터가 처음으로 나타나는 지점(idx) 확인
2) idx + 1 ~ 끝까지를 idx위치로 이동
3) 끝을 null로 변경
1) 끝 인덱스를 null로 변경
// 실제로는 제거가 아니라, 마지막 인덱스를 null로 변경하는 것
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i) //(처음포함)중간 인덱스를 제거하는 거라면
        System.arraycopy(es, i + 1, es, i, newSize - i); //인덱스 다음~끝을 인덱스자리에 복사
    es[size = newSize] = null; //끝 인덱스를 null로 변경
}

public boolean remove(Object o) {
    final Object[] es = elementData;
    final int size = this.size;
    int i = 0;
    found: { //데이터가 있는지 없는지 확인
        if (o == null) {
            for (; i < size; i++)
                if (es[i] == null)
                    break found;
        } else {
            for (; i < size; i++)
                if (o.equals(es[i]))
                    break found;
        }
        return false;
    }
    fastRemove(es, i); //있으면 fastRemove()
    return true;
}

- 마찬가지로 clear도 같은 원리로 모든 데이터 위치를 null로 변경한다.

public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

 

  3. 배열이나 ArrayList를 스택을 옆으로 누인 형태로 쓸 수 있다.  

- 스택은 LIFO, 나중에 들어간 데이터를 빼주는 형태다 

- ArrayList는 추가할 때 (공간 내에서) 처음부터 순차적으로 추가하면 새로운 배열을 생성하고 카피하지 않는다. 

- ArrayList를 삭제할 때 끝부터 삭제하면 데이터를 카피하는 작업 없이 null처리만으로도 삭제가 가능하다. 

- 결국 배열이나 ArrayList도 스택처럼 사용이 가능하다는 의미이다.

 

  4. ArrayList 구현하기  

이제 위의 원리를 토대로 ArrayList를 다시 구현해보면 아래와 같다.

import java.util.Arrays;

class MyArray {
    int[] arr;
    
    int size; // 현재 저장된 실제 사이즈

//  배열의 초기 사이즈 설정
    MyArray(int initialSize) {
        arr = new int[initialSize];
    }

//  배열에 데이터 삽입
    // 끝에 삽입
    public void add(int data) {
        if (size == arr.length) {
            arr = Arrays.copyOf(arr, size + 1);
        }
        arr[size] = data;
        size++;
    }

    // 특정 인덱스에 삽입
    public void add(int idx, int data) {

        if (idx > arr.length - 1) {
            this.add(data);
        } else if (idx >= 0){

            int[] newArr = arr.clone();
            int newSize = size;

            if (size == arr.length){
                newArr = Arrays.copyOf(arr, size + 1);
                newSize++;
            }

            System.arraycopy(arr, idx, newArr, idx + 1, size - idx);
            newArr[idx] = data;
            arr = newArr;
            size = newSize;

        } else {
            System.out.println("Idx Error!");
        }
    }

//  배열에서 데이터 삭제
    // 특정 데이터 삭제
    public boolean remove(int data) {

        int idx = 0;
        boolean hasData = false;

        for (int i = 0; i < size; i++) {
            if (arr[i] == data) {
                idx = i;
                hasData = true;
                break;
            }
        }

        if (hasData) {
            fastRemove(idx);
        } else {
            System.out.println("해당 데이터가 없습니다.");
        }

        return hasData;
    }

    // 실질적인 삭제
    public void fastRemove(int idx) {

        int[] newArr = new int[size - 1];

        if (idx < size - 1) { //처음 또는 중간 인덱스 제거시

            int newIdx = 0;

            for (int i = 0; i < idx; i++){
                newArr[newIdx++] = arr[i];
            }

            for (int i = idx + 1; i < size; i++){
                newArr[newIdx++] = arr[i];
            }

        }else{ //마지막 인덳 제거시
            for (int i = 0; i < idx; i++){
                newArr[i] = arr[i];
            }
        }
        arr = newArr;
        size = size - 1;
    }


}

 

 

|  배열과 ArrayList 사용하기

배열과 ArrayList는 인덱스와 데이터를 1 : 1로 매칭하기 때문에 아래와 같을 때에 유리하다.

- (선형 구조에서)LIFO 방식으로 데이터를 삽입/삭제할 때(add, remove -- 이때는 O(1))

- 많은 양의 데이터에서 특정 index의 데이터를 선택해야할 때(get)

 

그럼 언제 배열을 쓰는 걸 지양해야 할까?

- (선형 구조에서)중간 인덱스에 삽입/삭제가 빈번할 때(add, remove -- 이때는 O(n))

- 상대적으로 많지 않은 데이터에서 특정 값의 데이터가 있는지 찾을 때(contains)

 

ex. 그래프의 경우, 많은 양의 데이터를 다루면서 간선 수가 적을 경우 배열 보다는 연결리스트를 사용한다.

ex. 중복된 데이터들이 아닌 수열에서 특정 값을 찾을 때 곧, contains()를 쓸 때, HashSet을 쓰는게 오히려 빠르다(O(1))

 

|  자바 ArrayList 의 시간 복잡도

  add() * remove() * get() contains()
ArrayList O(1) or O(n) O(1) or O(n) O(1) O(n)

* add() 또는 remove()의 경우, 사이즈를 지정하지 않고 중간에 데이터를 삽입/삭제할 경우,

  새롭게 배열을 만들고 데이터를 삽입하기 때문에 O(1)이 아니라 O(n)의 시간 복잡도를 갖는다.

 

 

[ 참고 ]

시간 복잡도 - https://hbase.tistory.com/185

삽입 삭제 - https://webprogramcustom.tistory.com/47

|  자릿수와 경우의 수

(1) X진수의 K자릿수에 대한 모든 경우의 수

어떤 연속된 10진수 수 3개에 대한 배열이 있다고 가정할 때,

각 자리에 올 수 있는 수의 범위는 0 ~ 9이다. 

0 0 0
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
0 0 9

..... (생략) 

 

10진수의 세 자릿수에 대한 모든 경우의 수는 아래와 같다 

--> 10 x 10 x 10 = 1000 (곧, 000 ~ 999)

 

결국 x 진수의 k자릿수에 대한 모든 경우의 수는

--> x * x * x.... = x^k (자릿수 하나당 0 ~ x-1)

 

(2) x진수의 각 자릿수 하나당 0 ~ x-1 범위를 가지며, x - 1를 넘어서면 올림이 이루어진다.

- 10진수일 때

1 1 8
1 1 9
1 2 0

- 8진수일 때

1 1 8
1 2 0
1 2 1

 

- 10진수인 세자리수 ㅁㅁㅁ 에 올 수 있는 모든 경우의 수는 10^3개였다.

- 8진수인 세자리수 ㅁㅁㅁ 에 올 수 있는 모든 경우의 수는 8^3개이다.

- N진수인 세자리수 ㅁㅁㅁ 에 올 수 있는 모든 경우의 수는 N^3개이다. 

- 복합진수(a,b,c)인 세자리수 ㅁㅁㅁ 에 올 수 있는 모든 경우의 수는 (a x b x c)개이다.

 

(3) 복합 진수의 전체 범위 : 0 ~ (a x b x c) - 1

- 8진수 세자릿수

전체 범위 :  0부터 8^3 - 1  

 

- 복합진수일 때

전체 범위 :  0부터 (a x b x c) - 1 

 

|  코드 구현

문제 :

세 개의 교실 a, b, c에 수용 가능 인원수가 4, 3, 4 일 때, 각 교실에 배치할 수 있는 인원수의 모든 경우의 수를 나열하시오.

public class Test06_05_2_jarik {
    public static void main(String[] args) {

        int[] digit = {4, 3, 4}; // 각 수용인원
        int allCases = Arrays.stream(digit).reduce(1, (x, y) -> x*(y+1)); // 각 자리에 올 수 있는 모든 경우의 수

        System.out.println("abc abc abc abc abc abc abc abc abc abc");
        for (int i = 0; i < allCases; i++) { // 000~allCases-1

            int[] buff = new int[3]; // 세자릿수 버퍼 역할

            long denominator = allCases; // 분모 : allCases
            long numerator = i; // 분자 : 000, 001, 002 .....

            for (int j = 0; j < 3; j++) { //주어진 수 i(0~allCases-1)에 대해
                denominator /= digit[j] + 1; // 자릿수를 맞추고
                buff[j] = (int) (numerator / denominator) ; // 자릿수의 수 구하기 ex. 999/100
                numerator %= denominator; // 자릿수 외 나머지 구하기 ex. 999%100
            }

            // 출력
            String result = String.format("%d%d%d", buff[0], buff[1], buff[2]);
            if ((i + 1) % 10 == 0) {
                System.out.println(result);
            }else {
                System.out.print(result + " ");
            }
        }
    }
}

>> 결과

abc abc abc abc abc abc abc abc abc abc
000 001 002 003 004 010 011 012 013 014
020 021 022 023 024 030 031 032 033 034
100 101 102 103 104 110 111 112 113 114
120 121 122 123 124 130 131 132 133 134
200 201 202 203 204 210 211 212 213 214
220 221 222 223 224 230 231 232 233 234
300 301 302 303 304 310 311 312 313 314
320 321 322 323 324 330 331 332 333 334
400 401 402 403 404 410 411 412 413 414
420 421 422 423 424 430 431 432 433 434

 

|  합성수와 소수

합성수 나누어떨어지는 수가 하나라도 존재하는 수 ex. 100 = 1 x 100, 2 x 50, 4 x 25, 5 x 20, 10 x 10... 
소수 오직 1과 자기 자신만으로 나누어떨어지는 수 ex. 3 = 1 x 3

 

소수에 관한 알고리즘 문제는 보통 아래의 세가지가 있다고 하는데요.

 

1. 자연수 N이 소수인지 판별하거나, 

2. 1~N까지 중 소수의 갯수를 구하거나

3. 1 ~ N 까지의 소수를 나열하는

 

이 중에서 먼저 1.자연수 N이 소수인지 판별하는 법을 이야기해 보려고 합니다.

 

|  N을 2부터 N - 1 까지 모두 나누기

[1] 소수는 1과 자기 자신을 제외한 다른 수로는 나누어떨어져서는 안됩니다. 

 

그것을 판별하기 위한 코드는 아래와 같은데요. 2부터 N - 1가 N의 약수인지 확인하는 과정입니다.

public static boolean solution(int n) {

    // 1은 소수가 아니다.
    if (n == 1) {
        return false;
    }

    for (int i = 2; i < n; i++) { 
        if ((n % i) == 0) {
           return false;
        }
    }

    return true;
}

 

[2] 여기에서 합성수의 성질을 이용해 2 ~ N - 1이 아닌 2 ~ 루트N까지로 소수 여부를 확인할 수 있어요.

 

- 예를 들어, N이 100이라고 할 때, 1과 자기자신인 100을 제외한 약수를 구하면 아래 표와 같아요.

- 보면 10 x 10 을 전후로 a x b 가 b x a로 바뀌는 걸 볼 수 있습니다.

- 우리는 N이 합성수가 아닌지를 보려는 것이므로, 루트N까지 a가 있는지 확인하면 됩니다.

 

2x50
4x25
5x20
10x10
20x5
25x4
50x2

 

- 그럼 코드는 아래와 같이 변경됩니다.

public static boolean solution(int n) {

    // 1은 소수가 아니다.
    if (n == 1) {
        return false;
    }

    for (int i = 2; i <= (int)Math.sqrt(n); i++) { 
        if ((n % i) == 0) {
           return false;
        }
    }

    return true;
}

 

이번에는 2. 1~N까지 중 소수의 갯수를 구하는 법을 얘기하려 합니다.

2.3. 1 ~ N까지 범위의 소수의 갯수나 소수 나열을 위한 알고리즘은 여러가지가 있으나

그 중에서도 가장 많이 사용되는 것이 에라토스테네스의 체라고 해요.

 

|  에라토스테네스의 체

- 소수는 2가 아닌 짝수가 나올 수가 없습니다.

- 그리고, 각 소수 2, 3, 5, 7의 배수면 소수가 아니죠.

- 에라토스테네스는 체에 거르듯이 소수가 아닌 수들을 거르는 알고리즘을 말합니다.

 

에라토스테네스의 체 알고리즘

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
  2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  5. 자기 자신을 제외한 3의 배수를 모두 지운다.
  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  9. 자기 자신을 제외한 7의 배수를 모두 지운다.
  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

출처 : 위키백과

 

- 코드는 그러면 아래와 같이 나옵니다.

public static int solution(int n) {

    int[] numArr = new int[n];

    // 1로 초기화 (0, 1 제외)
    for (int i = 2; i < n; i++) {
        numArr[i] = 1;
    }

    // 2 ~ 루트n까지의 수들이 N의 약수인지 확인한다
    for (int i = 2; i <= (int)Math.sqrt(n); i++) {
        if (numArr[i] == 0) continue; // 이미 검사된 수 건너띄기

        // 자기자신을 제외한 모든 i의 배수 제외
        for (int j = i * 2; j < n; j+=i) { // i : 3, j : 6, 9, 12
            numArr[j] = 0;
        }
    }

    return Arrays.stream(numArr).sum();
}

 

 

[참조]

https://rebro.kr/46?category=449699 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

|  시작하기 전에

지난번에는 일차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루었다면,

이번에는 이차원 배열에 있는 데이터에 대한 구간합을 구하는 법을 다루어보았다.

🔖 일차원 구간합에 대한 포스팅은 아래에

 

[백준 11659] 구간합

🛎 11659 구간합 | 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. | 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N

why-dev.tistory.com

 

🛎 11660 구간 합 구하기 5

|  문제 

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

|  입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

|  출력

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

|  예제 입력

4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4

|  예제 출력

27
6
64

 

🔎 문제분석

이 문제도 지난번 일차원 구간합 구하기 문제처럼, 반복문을 사용하면 시간 초과가 난다.

[1] 자료형을 뭘 써야할까? 만약, 여기서 단순 반복을 사용하면 얼마나 오랜 시간이 걸릴까?

아래는 입력값들의 범위인데,

변수명 입력값 범위
N 표의 크기 (행의 크기) 1 ~ 1,024
데이터 배열의 데이터 1 ~ 1,000
M 합을 구해야하는 횟수 1 ~ 100,000

- 표의 크기최대 1024 x 1024 이며, 그렇게 되면 최대 1,048,576개의 데이터 수를 받게 된다.

- 데이터의 크기는 최대 1000인데, 최대 표 크기에서 모든 데이터가 1000이라고 할 때,

  최대 범위인 (1, 1)부터 (N, N)까지 최대 구간합은 1,048,576,000가 된다. 

- int타입 데이터의 표현 범위는 -2,147,483,648 ~ 2,147,483,647(약 -21억 ~ 21억, -2^31 ~ 2^31 - 1)이기 때문에 

  구간합의 자료형은 int로 두어도 괜찮다.

 

이제 단순 반복을 했을 때에 얼마나 시간이 걸릴 것인가를 구해 보려고 한다.

[행 x 열]에 대한 이중 반복 루프에서 각 (x1, y1) ~ (x2, y2)까지의 합을 구한다고 하면 

- 시간 복잡도는 O(n^2)가 나온다. (만약 M만큼 범위를 입력받으면서 동시에 구간합을 처리하게 되면 O(n^3) )

 

만약에 최대 크기 배열M이 최댓값이 나온다하고 범위가 (1, 1) ~ (N, N)이면- 100,000 x 1024 x 1024(104,857,600,000)만큼 데이터를 확인하고 합을 구한다.

 

[2] 2차원 배열의 구간합을 구하는 방법을 구해보자..

(1) 먼저, 입력 배열은 D[N + 1][N + 1]로, 구간합 배열은 S[N + 1][N + 1]로 만들려 한다.

- 배열 크기는 입력을 (1, 1)부터 (N, N) 사이값으로 받기 때문에 N+1 x N+1으로 하는게 더 쉬웠다..

- (D는 dataArr의 약자고, S는 sumArr의 약자로 임의로 잡았다.)

 

(2) D --> S 로 구간합을 구하는 방법이다.

 

가. 먼저 행이 1일 때와, 열이 1일 때를 보면

  1 2 3 4 구간합
-------->
  1 2 3 4
1 1 2 3 4 1 1 3 6 10
2 2 3 4 5 2 3      
3 3 4 5 6 3 6      
4 4 5 6 7 4 10      

 

- 행이 1인 경우에는, S배열에서 바로 전 열(j - 1)의 값과 D[ i ][ j ] 를 더해주면 된다.

  S [ i ][ j ] = S [ i ][ j - 1 ] + D[ i ][ j ]

- 열이 1인 경우에도, S배열에서 바로 전 행(i - 1)의 값과 D[ i ][ j ] 를 더해준다. 

  S [ i ][ j ] = S [ i - 1 ][ j ] + D[ i ][ j ]

 

나. 행과 열이 1이 아닌 경우를 보면

  1 2 3 4 구간합
-------->
  1 2 3 4
1 1 2 3 4 1 1 3 6 10
2 2 3 4 5 2 3 8    
3 3 4 5 6 3 6      
4 4 5 6 7 4 10      

 

S[2][2]를 구하는 방식을 풀어보면 아래와 같다.

- S[1][2] = D[1][1] + D[1][2]

- S[2][1] = D[1][1] + D[2][1]

- S[2][2] = D[1][1] + D[1][2] + D[2][1] + D[2][2]

              = S[1][2] + S[2][1] - D[1][1] + D[2][2]

 

이를 토대로 공식을 만드면 아래와 같이 만들 수 있다.

- S [ i ][ j ] = S [ i ][ j - 1 ] + S [ i - 1 ][ j ] - S[ i - 1 ][ j - 1 ] + D[ i ][ j ]

 

=> 이 상태에서 다시 위의 가.로 넘어가면 N + 1 x N + 1 크기를 만들어줄 것이므로,

    S [ i ][ j ] = S [ i ][ j - 1 ] + S [ i - 1 ][ j ] - S[ i - 1 ][ j - 1 ] + D[ i ][ j ]

    만약 행이 1이라면, 그 위인 S[0][N] 값은 모두 0이 될 것이므로

    S [ i ][ j ] = S [ i ][ j - 1 ] + 0 - 0 + D[ i ][ j ]

                  = S [ i ][ j - 1 ] + D[ i ][ j ]  // 나. 의 공식을 그대로 사용해도 무방하다는 걸 볼 수 있다.

    마찬가지로 열이 1일때도 동일하다. 

 

[3] 구간합 배열에서 범위값을 구하는 방법

만약에 (1, 1)에서 (3, 3)까지의 구간합을 구하라 하면 범위값을 구하는 건 쉽다.

- 그냥 S[3][3]를 반환하면 된다.

 

그런데 (2, 2)에서 (3, 3)까지의 구간합을 구하라 한다면?

 

  1 2 3 4 구간합
-------->
  1 2 3 4
1 1 2 3 4 1 1 3 6 10
2 2 3 4 5 2 3 8 15 24
3 3 4 5 6 3 6 15 27 42
4 4 5 6 7 4 10 24 42 64

 

S[3][3]에서 (1, 2) ~ (1, 3)과 (2, 1) ~ (2, 3) 합을 빼주고 (1, 1)값을 더해주어야 한다.

- 만약 범위를 (x1, y1) ~ (x2, y2)라고 한다면

  구간합 범위를 구하는 식 : S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1 - 1][y1 -1]

 

⌨️ 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        // 입력
        int N = Integer.parseInt(st.nextToken()); // 행의 길이
        int M = Integer.parseInt(st.nextToken()); // 케이스 수

        // 기존 배열 D 
        int[][] D = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 1; j <= N; j++) {
                D[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 구간합 배열 S  
        int[][] S = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + D[i][j];
            }
        }

        // 케이스당 하나씩 처리
        // 범위 (x1, y1) ~ (x2, y2)의 구간합 구하기
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());

            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

            int sum = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1 - 1][y1 -1];

            sb.append(sum);
            sb.append("\n");

        }

        System.out.println(sb.toString());

    }
}

 

팰린드롬이란, 앞 뒤가 똑같은 전화번호 문자열을 말한다고 합니다.

단순히 "abba" 문자열이 팰린드롬인가를 확인한다면, 

[1] 문자열을 거꾸로 뒤집어서 확인하거나

[2] 양끝에 left, right로 커서를 두고 left < right 일때까지 양 끝을 비교해도 되는데요.

 

물론 우리의 알고리즘은 그렇게로만 끝나지 않기 때문에 더 향상된 버전의 팰린드롬을 만날 수 있었습니다.

제 수준에서 풀만한 것들을 먼저 뽑아보았어요..

아래 중에서 하나씩 풀어보려 합니다.

|  백준 팰린드롬 문제 모음

브론즈 1259 팰린드롬수 바로가기
실버 1213 팰린드롬 만들기
1254 팰린드롬 만들기
17609 회문
바로가기
바로가기
바로가기
골드 1053 팰린드롬 공장 바로가기

 

🛎 17609 회문

|  문제 

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

|  입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

|  출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

|  예제 입력

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

|  예제 출력

0
1
1
2
2
0
1

 

⌨️ 코드1 - 반복문

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static int isPanlindrome(char[] arr, int left, int right, int delCnt){

        while (left < right) {
            if (arr[left] == arr[right]) {
                // 회문인 경우
                left++;
                right--;
            } else {
                // 회문이 아닌 경우
                int l2 = left;
                int r2 = right;

                // 좌측 문자를 하나 삭제 후 확인
                l2 += 1;
                while (l2 < r2) {
                    if (arr[l2] == arr[r2]){
                        l2++;
                        r2--;
                    } else {
                        delCnt++;
                        break;
                    }
                }

                if (delCnt == 0) { // abca와 같이 좌측 제거 후 유사회문인 경우 고려
                    return 1;
                }

                // 우측 문자를 하나 삭제 후 확인
                l2 = left;
                r2 = right - 1;
                while (l2 < r2) {
                    if (arr[l2] == arr[r2]){
                        l2++;
                        r2--;
                    } else {
                        delCnt++;
                        break;
                    }
                }

                // 좌우축 모두 확인 후에 delCnt를 반환
                return delCnt; // 반환하지 x면 무한 루프

            }
        }

        return delCnt;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T --> 0) {
            String s = br.readLine();
            sb.append(isPanlindrome(s.toCharArray(), 0, s.length()-1,0));
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }
}

 

⌨️ 코드2 - 재귀

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    // 재귀로 풀 경우
    public static int isPanlindrome2(char[] arr, int left, int right, int delCnt){

        while (left < right) {
            if (arr[left] == arr[right]) {
                // 회문인 경우
                left++;
                right--;
            } else {
                // 처음 불일치한 경우
                if (delCnt == 0) {
                    // 좌우측을 하나씩 삭제한 문자열이 회문인지 확인
                    if (isPanlindrome2(arr, left + 1, right, 1) == 0 ||
                            isPanlindrome2(arr, left, right - 1, 1) == 0) {
                        return 1;
                    } else {
                        return 2;
                    }
                } else {
                    return 2;
                }
            }
        }

        return 0;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T --> 0) {
            String s = br.readLine();
            sb.append(isPanlindrome2(s.toCharArray(), 0, s.length()-1,0));
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }
}

행복한 수에 대한 연습문제를 풀다가, 백준에 관련된 문제가 있나 싶어 찾아보았습니다.

행복한 수만 구하는 문제는 아니고, 행복한 소수를 구하는 문제가 있었어요.

그래서 한 번 개념 정리를 먼저 하고 문제를 풀어보고 정리를 하려 합니다.

 

|  행복한 수란?

십진수의 수가 있을 때, 예를 들어 14가 있다고 할 때, 

각 자릿수를 제곱한 합은 1^2 + 4^2 = 18 입니다.

다시 29의 각 자릿수를 제곱한 합을 구하면 1^2 + 8^2 = 65

이 과정을 계속하다보면, 64,37,58,89,145,42,20,4,16,37,58,89,145,42.... 이 나오게 되는데요.

 

- 어떤 수는 14처럼 '1이 아닌 중복되는 수'를 지점으로 무한히 동일한 수열이 반복되는 반면,

- 어떤 수는 제곱합의 끝이 1이 되면서 이후에는 1이 반복되어 나옵니다.

 

'행복한 수'는 이처럼 제곱합의 끝이 1이 나오는 수를 이야기합니다.

 

[ 행복한 수를 찾는 코드 ]

public static boolean isHappy(int n) {

        // 중복된 지점부터는 저장X
        HashSet<Integer> set = new HashSet<>();

        while (set.add(n)) { //set이 이미 해당 값을 가지고 있을 때 false --> 루프탈출
            // 각 자릿수의 제곱합
            int sum = 0;
            while (n > 0) {
                sum += (int) Math.pow(n % 10, 2);
                n /= 10;
            }

			// 합이 1이 나오면 행복한 수, 아니면 set에 add하고 중복수 있는지 확인
            if (sum == 1) {
                return true;
            } else {
                n = sum;
            }
        }

        return false;
    }

 

|  소수 구하기

소수는 자연수 N을 1부터 N까지 나누었을 때 나누어떨어지는 수가 오직 1과 자기자신 뿐인 수를 말합니다.

단순 구현을 하게 되면 아래와 같이 풀 수 있는데요

// 방법1. 2부터 N - 1까지 루프를 돌려 n을 나누어 본다.
public static boolean isPrimeNumber(int n) {

    for (int i = 2; i <= n - 1; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

아래의 두가지 원리를 이용해서 위를 개선하면 아래와 같았어요.

(1) 2가 아닌 짝수는 절대 소수일 수가 없다는 점 - ex. 4, 6, 8, 10.. 모두 2로 나누어떨어지죠
(2) 홀수 N을 짝수인 수로 나누면 나누어떨어지지 않는다는 점 - ex. N이 125일 때, 나누어떨어지는 수는 1, 5, 125
      > 이는 짝수인 수의 구구단을 생각하면 쉬웠어요. 
      > 예를 들어, 4의 구구단은 4x1 = 4, 4 x 2= 8, 4 x 3 = 12.... 모두 짝수가 나와요.
      > 결국 짝수인 수를 다른 자연수로 곱해봤자 절대 홀수가 나올 수 없다는 의미이죠.
// 방법2. 수학적 원리 사용 - 2가 아닌 짝수는 소수가 아님
public static boolean isPrimeNumber2(int n) {

    // 2가 아닌 짝수 여부
    if (n != 2 && n % 2 == 0) { 
        return false;
    }

    // 3부터 홀수로만 나누어본다.
    for (int i = 3; i <= n - 1; i+=2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

 

🛎 10434 행복한 소수

|  문제 

Q. : 아래의 수열에서 다음에 올 수를 찾으시오.

313 331 367 ...

경복 : ??

강산 : 379.

경복 : 뭐?

강산 : 행복한 소수잖아.

경복 : 행복한 뭐?

강산 : 그러니까, 자리수의 제곱의 합을 구하는 연산을 계속 반복했을 때 1이 되는 수를 행복한 수라고 하잖아. 행복한 소수는 그 중 소수인 수이고.

7은 분명 소수이다. 과연 행복할까?

  • 7 → 72 = 49
  • 49 → 42 + 92 = 97
  • 97 → 92 + 72 = 130
  • 130 → 12 + 32 + 02 = 10
  • 10 → 12 + 02 = 1

7은 행복한 수이다 ☺.

사실 7은 행복한 소수 중 가장 작은 수이다. (이 문제에서는 1을 소수가 아닌 것으로 생각한다)

어떤 수가 주어지면 이 수가 행복한 소수인지 판정해보자.

|  입력

첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)

각 테스트 케이스는 테스트 케이스 번호와 행복한 소수인지 판정해야 할 정수인 M으로 이루어져 있다. (1 ≤ m ≤ 10000).

|  출력

각 테스트 케이스마다, 테스트 케이스의 번호, 입력받은 수, 만일 M이 행복한 소수라면 YES 아니라면 NO를 공백으로 각각 구분하여 출력한다.

|  예제 입력

4
1 1
2 7
3 383
4 1000

|  예제 출력

1 1 NO
2 7 YES
3 383 YES
4 1000 NO

 

⌨️ 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Ex10434 {

	// 1단계 메서드 : 소수 확인 (단, 1은 소수가 아니다)
    public static boolean isPrimeNumber(int n) {

        // 탈출문1 : 1은 소수X
        if (n == 1) {
            return false;
        }

        // 탈출문2 : 2가 아닌 짝수는 소수x
        if (n != 2 && n % 2 == 0) {
            return false;
        }

        // 3 ~ N 까지 홀수로 나누어떨어지지 않는지 확인 
        for (int i = 3; i <= n - 1; i+=2) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }

	// 2단계 메서드 : 행복한 수 확인
    public static boolean isHappy(int n) {

        // 중복수 확인용 set
        HashSet<Integer> set = new HashSet<>();

        while (set.add(n)) { 
            // 각 자릿수의 제곱합이
            int sum = 0;
            while (n > 0) {
                sum += (int) Math.pow(n % 10, 2);
                n /= 10;
            }

            if (sum == 1) {
            	// 1이면 행복한 수
                return true;
            } else {
            	// 아니면
                n = sum;
            }
        }

		// 중복수가 나온 경우
        return false;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int P = Integer.parseInt(br.readLine()); // 케이스 수
        int[] allCase = new int[P];

        // 모든 케이스 입력
        while (P > 0) {
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken()) - 1;
            int num = Integer.parseInt(st.nextToken());

            allCase[idx] = num;

            P--;
        }

        // 각 케이스별 행복한 소수여부 확인
        for (int i = 0; i < allCase.length; i++) {

            System.out.printf("%d %d ", i + 1, allCase[i]);

            if (!isPrimeNumber(allCase[i])){
                System.out.print("NO\n");
                continue;
            }

            if (!isHappy(allCase[i])) {
                System.out.print("NO\n");
                continue;
            }

            System.out.print("YES\n");

        }

    }
}

🛎 11659 구간합

|  문제 

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

|  입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

|  출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

|  예제 입력

5 3
5 4 3 2 1
1 3
2 4
5 5

|  예제 출력

12
9
1

 

🔎 문제분석

이 문제를 반복문으로 풀려고 했을 때, 계속적으로 시간초과가 나타났다.

입출력을 내가 아는 모든 방법을 총동원해서 변경해보았지만 역부족.

'뭐지, 풀 수 없는 문제인가' 했었는데, 그게 아니라 이 문제를 푸는 다른 방법이 있어서였다.

 

※ 구간합을 구하는 방법

[1] 먼저, 둘째줄에서 받은 N개의 수들을 arr배열에 넣어준다.

[2] arr배열을 토대로 합배열을 별도로 만든다.

인덱스 0 1 2 3 4
arr 5 4 3 2 1
hap 5 9 12 14 15

[3] 구간 (x1, x2)가 있다고 할 때, 구간의 합을 구하는 방법은 다음과 같다.

1) 만약 x1이 1이라면 : 인덱스 0 부터 x2-1까지의 누적합을 구하는 것이므로 그냥 hap[x2-1]를 반환하면 된다.

2) 만약 x1이 1보다 크면 : 예를들어 (2, 5)라고 할때

    >> 실제 인덱스 범위는 1~4일 것이다.

    hap[4] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4]

    hap[1] = arr[0] + arr[1]

    -----------------------------------------------------------------------------------

    hap[1~4] = arr[1] + arr[2] + arr[3] + arr[4]    <------- 구하려는 값

    >> 구하려는 값이 나오기 위해서는 실제 인덱스 범위는 결국 (x1-2, x2-1)일 것이다.

 

이제 위 원리는 바탕으로 코드를 만들면 다음과 같다.

 

⌨️ 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Ex11659 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(st.nextToken()); //수의 개수
        int M = Integer.parseInt(st.nextToken()); //합을 구해야 하는 횟수

        // 입력받은 수 배열
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            arr[i] = num;
        }

        // 합 배열을 구한다
        int[] hap = new int[N];
        for (int i = 0; i < N; i++) {
            if (i == 0) {
                hap[i] = arr[i];
                continue;
            }
            hap[i] = hap[i - 1] + arr[i];
        }

        // 구간합을 구한다.
        for (int i = 0; i < M; i++) {

            st = new StringTokenizer(br.readLine());

            int x1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());

            int sum = 0;
            if (x1 == 1) {
                sum = hap[x2 - 1];
            }else {
                sum = hap[x2 - 1] - hap[x1 - 2];
            }

            bw.write(String.valueOf(sum));
            bw.write("\n");

        }
        
        bw.flush();
        bw.close();
        
    }
}

 

+ Recent posts