Typiler

DAT는 자료구조입니다. 값을 배열의 index를 활용하는 것이 포인트 입니다. 

동작방식

배열을 사용하여 레코드를 해당 키에 매핑할 수 있는 데이터 구조입니다. 직접 주소 테이블에서 레코드는 키 값을 인덱스로 직접 사용하여 배치됩니다. 빠른 검색, 삽입 및 삭제 작업을 용이하게 합니다.

최대값에 1을 더한 크기의 배열을 만든 다음(0 기반 인덱스로 가정) 값을 인덱스로 사용합니다. 예를 들어 다음 다이어그램에서 키 21은 인덱스로 직접 사용됩니다.

시간복잡도

탐색,삽입,삭제 연산을 모두 O(1)

참고사이트

https://www.geeksforgeeks.org/direct-address-table/

기본코드

아래는 글을 입력받아 가장 많이 나온 문자를 찾아내는 간단한 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


public class DAT_example {
	
	/**
	 * DTA : Direct Address Table 자료구조 
	 * ==> 값을 index로 활용하는 것인 포인트
	 */
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException  {
		
		// 입력
		String input = br.readLine();
		int[] arr = new int[200];
		int max = 0;
		String maxChar = "";
		for(int i=0; i<input.length(); i++){
			arr[input.charAt(i)] += 1;
			if(arr[input.charAt(i)]  > max){
				max = arr[input.charAt(i)] ;
				maxChar = input.charAt(i)+"";
			}
		}
		
		// 풀이
		System.out.println(maxChar);
		
		br.close();
		bw.close();
	}

}

결과

AMDKIDD   <== 입력
D              <== 결과

알고리즘 문제를 풀다보면 정렬을 해야하는 경우가 많이 발생합니다. 기본적으로 제공되는 Arrays.sort() 함수가 있지만 이것만으로 문제를 풀기에는 한계가 있습니다. 특히 다중차순을 요하는 문제는 직접 구현하는 것이 빠르고 이해가 쉽습니다.

기본적인 정렬 코드

아래는 오름차순, 내림차순, 다중차순의 기본 정렬 구현 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;


class Node implements Comparable<Node>{
	int a;
	int b;
	
	public Node(int a, int b){
		this.a = a;
		this.b = b;
	}

	@Override
	public int compareTo(Node tar) {
		
		// tar 기준으로 tar vs this 중 tar 우선순위가 더 높으면 1
		// tar 기준으로 우선순위가 동등하면 0
		// tar 기준으로 tar vs this 중 tar 우선순위가 더 낮으면 -1
		
		if(tar.a > this.a) return 1;
		if(tar.a < this.a) return -1;
		
		// 첫 수가 우선쉰위가 도등할때 아래 조건을 따른다.
		if (tar.b < this.b) return 1;
		if (tar.b > this.b) return -1;
		
		return 0;
	}
}

public class Sort_ex01 {

	// 정렬
	// 1. 오름차순 
	// 2. 내림차순 
	// 3. 다중차순

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	
    public static void main(String[] args) throws IOException {

        Integer[] arr = {5,4,5,4,4,5};
        
        //1. 오름차순
        Arrays.sort(arr);
        
        //2. 내림차순
        Arrays.sort(arr, Comparator.reverseOrder());
        
        //3. 다중차순
        Node[] arrNode = new Node[6];
        arrNode[0] = new Node(5,8);
        arrNode[1] = new Node(4,2);
        arrNode[2] = new Node(5,1);
        arrNode[3] = new Node(4,9);
        arrNode[4] = new Node(4,7);
        arrNode[5] = new Node(5,3);
        
        // 정렬조건
        // 1) 첫번째 수가 큰수 우선
        // 2) 두번째 수가 작은 수 우선        
        Arrays.sort(arrNode);
        
        int a=1;

		br.close();
		bw.close();

    }
}

오름차순, 내림차순은 Arrays.sort() 함수를 이용하여 구현이 간단합니다. 하지만 다중차순의 경우 정렬 조건이 1) 첫번째 수가 큰수, 2) 두번째 수가 작은 수 우선이라고 한다면 위 코드와 같이 class 를 만들어 Comparable 을 이용하여 구현하여 줍니다. 정렬 우선순위는 compareTo() 함수를 오버라이드 하여 구현하는데, tar 기준으로 tar vs this 중 tar 우선순위가 더 높으면 1,  tar 기준으로 우선순위가 동등하면 0,  tar 기준으로 tar vs this 중 tar 우선순위가 더 낮으면 -1 이 중요합니다. 

이러한 방법을 통하여 "숫자와 문자를 다음과 같은 우선순위 조건으로 맞추어 정렬 후 출력" 하는 문제도 해결이 가능합니다. (ex, 1)짝수 우선 2)숫자 오름차순 3)문자 오름차순)

정렬은 알고리즘에서 응용을 많이 하는 것으로 방법을 꼭 숙지하여야 합니다.

플러드 필 알고리즘은 다차원 배열의 어떤 카과 연결된 영역을 찾는 알고리즘 입니다. 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용됩니다.

동작과정

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 한다.
2. 큐에 원소를 꺼내어 그 칸에 인접한 칸(ex. 상,하,좌,우)에 대하여 3과 같이 동작한다.
3. 인접한 칸에 대하여 방문여부를 판단하여 처음 방문했다면 방문 표시를 남기고 큐에 넣는다.
4. 큐의 모든 원소가 빌 때까지 2의 행동을 반복한다.

시간복잡도

모든 칸이 큐에 1번 들어가는 것이 보장되므로 칸이 N개일 때 시간복잡도는 O(N) 입니다.

참고사이트

https://choijiuen.tistory.com/99

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

기본코드

2차원 배열 (4*4) 에서 2,1 에서 시작하여 모든 배열을 도는데 걸리는 cnt를 알아내는 예제입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;

class PNode {
    int y, x;
    PNode(int a, int b)
    {
        y = a;
        x = b;
    }
}

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int [][]map = new int[4][4];
    static Queue<PNode> q = new LinkedList<PNode>();

    public static void main(String[] args) throws IOException {        

        map[2][1] = 1;
        q.add(new PNode(2, 1));

        int[][] direct = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int cnt = 0;

        while(!q.isEmpty()) {
            PNode now = q.poll();

            //now에서 다음 퍼지는 길 모두 등록
            for (int t = 0; t<4; t++ ) {
                int ny = now.y + direct[t][0];
                int nx = now.x + direct[t][1];
                if (ny < 0 || nx < 0 || ny >= 4 || nx >= 4) continue;
                if (map[ny][nx] != 0) continue;

                map[ny][nx] = map[now.y][now.x]+ 1;
                if (map[ny][nx] > cnt) cnt = map[ny][nx];

                q.add(new PNode(ny, nx));
            }
        }

        bw.write(cnt + "\n");

        br.close();
        bw.close();
    }
}

실행하여 map 의 변화를 알아보면 처음 map은 (2,1) 에서 시작하기 때문에 아래와 같다.

[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 1, 0, 0]
[0, 0, 0, 0]

전부 완료되었을때 map 은 아래와 같이 변경된다.

[4, 3, 4, 5]
[3, 2, 3, 4]
[2, 1, 2, 3]
[3, 2, 3, 4]

위와 같은 결과로 모든 배열이 채워지는데 마지막 숫자인 5가 결과로 나타난다.

파라매트릭 서치(Parametric Search)는 바이너리 서치와 매우 유사합니다. 차이점은 최적화 문제를 결정문제로 바꾸어 푸는 것입니다. 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고 싶은 경우에 사용을 합니다.

• 바이너리 서치 : 배열에서 중앙값이 가리키는 값이 내가 찾는 값인지가 중요
• 파라매트릭 서치 : 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것

동작과정

1. 데이터를 정렬한다.
2. 범위를 반씩 좁혀간다.
3. S 와 E 가 같을때 까지 진행한다.

시간복잡도

바이너리 서치와 같은 O( log N ) 입니다.

참고사이트

https://www.crocus.co.kr/1000

https://en.wikipedia.org/wiki/Parametric_search

기본코드

'#' 의 개수를 알아내는 문제

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static char[] arr;
    
    static int parametricSearch(int s, int e){
    	
    	int maxIndex = -1;
    	
    	while(s<=e){
    		int mid = (s+e)/2;
    		char mVal = arr[mid];
    		
    		if (mVal == '#') {
                if (maxIndex < mid) maxIndex = mid;
                s = mid + 1;
            }
            else {
                e = mid - 1;
            }
    	}
    	
    	return maxIndex;
    	
    }
    
    public static void main(String[] args) throws IOException {      
    	
    	String str = "#######___";
   		arr = str.toCharArray();
  		
   		int cnt = parametricSearch(0, arr.length-1) + 1;
    		
   		bw.write(cnt+"\n");
    	
        br.close();
        bw.close();        
    }
}

바이너리 서치와 바이너리 서치 트리는 차이가 있습니다. 이중 오늘 공부할 내용은 바이너리 서치(Binary Search) 입니다. 자료구조가 아니라 알고리즘입니다. 바이너리 서치는 정렬되어있는 상태에서 내가 원하는 값을 찾고 싶을때 찾는 알고리즘 입니다. 여기서 정렬되어있는 상태가 중요합니다. 이것이 기본조건입니다. 데이터를 빨리 찾기 위한 방법입니다.

동작과정

1. 데이터를 정렬한다.
2. 범위를 반씩 좁혀가며 데이터를 찾는다.

시간복잡도

한번 탐색할때 마다 크기를 반으로 줄이기 때문에 시간복잡도는 O( log N ) 이 됩니다.

참고사이트

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

기본코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;


class 바이너리서치_기본코드 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] arr = {50,30,1,2,5,7,9,10};
    static int tar = 7;
    
    static void bSearch(int s, int e){
    	while(s<=e){
    		int mid = (s+e)/2;
    		int mVal = arr[mid];
    		
    		if(mVal == tar){
    			System.out.println("발견");
    			return;
    		}
    		
    		if(mVal < tar) s= mid + 1;
    		else e = mid - 1;
    	};
    	
    	System.out.println("미발견");
    }
    
    public static void main(String[] args) throws IOException {      
    	
    	// 바이너리 전제조건 => 정렬이 필수
    	Arrays.sort(arr);
    	
    	bSearch(0,arr.length-1);
    	
        br.close();
        bw.close();        
    }
}

Union-Find는 자료 구조입니다. 그래프 알고리즘에서 사용하는 대표 알고리즘입니다. 여러개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. Union-Find 알고리짐은 다른 고급 그래프 알고리즘의 베이스가 되니 반드시 학습하셔야 합니다.

동작과정

• 파인드(Find) : 어떤 원소가 주어졌을 때 이 원소가 속한 집합을 반환한다. 파인트는 일반적으로 어떤 원소가 속한 집합을 '대표'하는 원소를 반환하는데, 이를 위해서 어떤 원소와 각 대표 원소들 간의 파인드 결과를 비교하여 같은 집합임을 판단한다.
• 유니온(Union) : 두 개의 집합을 하나의 집합으로 합친다.

시간복잡도

평균적으로 트리의 높이마큼 탐색하는 O(logN) 입니다.

참고사이트

https://m.blog.naver.com/ndb796/221230967614

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

기본코드

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

class UnionFind_기본코드 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static char[] uArr = new char[100];

    static char getFind(char tar) {
        //최종보스가 누군지 리턴하는 함수        
        if (uArr[tar] == 0) return tar;        
        char ret = getFind(uArr[tar]);
        uArr[tar] = ret; //현재 보스를 최종보스로 교체
        return ret;        
    }

    static void setUnion(char t1, char t2)
    {
        char a = getFind(t1);
        char b = getFind(t2);
        if (a == b) return;
        uArr[b] = a;
    }

    public static void main(String[] args) throws IOException {        

        setUnion('A', 'B');
        setUnion('B', 'C');
        setUnion('E', 'D');        
        setUnion('F', 'E');        
        setUnion('G', 'H');        
        setUnion('I', 'J');        

        System.out.println("A:"+getFind('A'));
        System.out.println("B:"+getFind('B'));
        System.out.println("C:"+getFind('C'));
        System.out.println("D:"+getFind('D'));
        System.out.println("E:"+getFind('E'));
        System.out.println("F:"+getFind('F'));
        System.out.println("G:"+getFind('G'));
        System.out.println("H:"+getFind('H'));
        System.out.println("I:"+getFind('I'));
        
        //활용, A랑 E랑 같은 조직인지 확인하는 코드
        if (getFind('E') == getFind('D')) {
            System.out.println("같은조직");
        }
        else {
            System.out.println("다른조직");
        }

        br.close();
        bw.close();
    }
}

그래프 문제에서 대표적인 최단 경로를 구하는 알고리즘입니다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다고 알려져 있습니다. 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려줍니다. (단, 음의 간선을 포함할 수 없음)

응용이 많은 부분이라 기본적인 내용을 확실히 숙지하여야 합니다.

동작과정

1. 출발 노드를 설정
2. 출발노드 기준으로 각 노드의 최소비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐서 톡정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 과정에서 3~4 과정을 반복

시간복잡도

• 힙의 구조를 활용하면 : O(N * log N)

참고 사이트

• 동빈나 : https://blog.naver.com/ndb796/221234424646
• 위키백과 : https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

기본코드

아래와 같은 그래프가 존재한다고 합시다. 0에서 시작하여 각 노드까지의 최단 거리를 구하는 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;

class Node implements Comparable<Node>{
    int n;
    int dist;

    Node(int a, int b) {
        n = a;
        dist = b;
    }

    @Override
    public int compareTo(Node tar) {
        if (tar.dist < this.dist) return 1; 
        if (tar.dist > this.dist) return -1; 
        return 0;
    }    

}

class 다익스크라_기본코드_단방향 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static ArrayList<ArrayList<Node>> alist = new ArrayList<ArrayList<Node>>();
    static PriorityQueue<Node> q = new PriorityQueue<Node>();

    static int[] best;
    static int[] used;

    public static void main(String[] args) throws IOException {        

        int n = 5;
        best = new int[n];
        used = new int[n];

        for (int i = 0; i<n; i++) {
            alist.add(new ArrayList<>());
        }

        alist.get(0).add(new Node(2, 70));
        alist.get(0).add(new Node(1, 10));
        alist.get(0).add(new Node(4, 170));        
        alist.get(1).add(new Node(2, 50));
        alist.get(1).add(new Node(3, 20));
        alist.get(2).add(new Node(4, 60));    
        alist.get(3).add(new Node(2, 15));

        //다익스트라 초기세팅
        q.add(new Node(0, 0));
        for (int i = 0; i<n; i++) best[i] = Integer.MAX_VALUE;
        best[0] = 0;

        while(!q.isEmpty()) {
            Node via = q.poll();
            if (used[via.n] == 1) continue; //이미 했었던 경유지면 탈락
            if (best[via.n] != via.dist) continue; //예전정보면 탈락

            used[via.n] = 1;             

            for (int i = 0; i<alist.get(via.n).size(); i++) {
                Node tar = alist.get(via.n).get(i);

                //지금까지 구했던 최고의 비용보다, 더 저렴한 비용이 발견되면 
                if (best[tar.n] > via.dist + tar.dist) {
                    best[tar.n] = via.dist + tar.dist; //갱신 
                    q.add(new Node(tar.n, best[tar.n]));
                }
            }
        }

        System.out.println(best[4]);

        br.close();
        bw.close();
    }
}

0에서 시작하여 각 노드들의 최단 거리는 아래와 같이 빨강색 경로로 이동을하여 4까지 가는 최단경로의 거리는 105 입니다.

BufferedReader / Writer 예제

10만개가 넘어가는 Data를 빠른 속도로 입력 / 출력 받기 위해서는 BufferedReader / BufferedWriter 를 사용해야합니다.

입력예시
5 3
5 4 3 2 1
1 3
2 4
5 5

출력예시
N : 5
K : 3
numbers : 5 4 3 2 1 
questions : (1, 3) (2, 4) (5, 5) 

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

public class Main {

	static int[] numbers;
	static int[][] questions;
	static int N;
	
	
	public static void main(String[] args) throws IOException {
		// 파일에 이별된 예제를 사용.. 시험에서는 아래 한줄을 주석 처리
        System.setIn(new FileInputStream("input\\rsq.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        numbers = new int[N+1]; // 0은 사용하지 않으니까 1부터 N까지
        questions = new int [K+1][2];
        
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
        	numbers[i] = Integer.parseInt(st.nextToken());
        }
        
        
        for(int i=1; i<=K; i++){
        	st = new StringTokenizer(br.readLine());
        	questions[i][0] = Integer.parseInt(st.nextToken());
        	questions[i][1] = Integer.parseInt(st.nextToken());
        }
        
        bw.write("N : " + N + "\n");
        bw.write("K : " + K + "\n");
        bw.write("numbers : ");
        for(int i=1; i<=N; i++){
        	bw.write(numbers[i] + " ");
        }
        bw.write("\n");
        
        bw.write("questions : ");
        for(int i=1; i<=K; i++){
        	bw.write("(" + questions[i][0] + ", " + questions[i][1] + ") ");
        }
        bw.write("\n");
        
        br.close();
        bw.close();
	}
}