삶을 코딩하다, 필드를 걷다

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가 결과로 나타난다.

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();
	}
}