한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다. 

---

 

사각형을 4개 단위로 쪼개면서 1칸이 남을 때까지 분할하여 해결하였습니다.

구현하는 과정에서 모든 칸에 대한 방문 순서를 기록했지만 메모리 초과와 시간 초과가 발생했고, 불필요한 칸을 쪼개기 때문에 이러한 문제가 발생했습니다.

해결 

1) 인덱스를 비교해서 쪼갤 사각형 내에 있는지 확인하고, 그렇지 않다면 사각형의 크기 만큼 방문 순서를 더해줍니다.

2) 쪼갤 사각형 내에 있다면, 재귀를 호출합니다.

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

/**
 * Z
 */
public class BOJ1074 {

    static int pow[];
    static int count = 0;
    static int r, c;

    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bufferedReader.readLine().split(" ");
        int N = Integer.parseInt(s[0]);
        r = Integer.parseInt(s[1]);
        c = Integer.parseInt(s[2]);

        pow = new int[N + 1];
        pow[0] = 1;

        for (int i = 1; i <= N; i++) {
            pow[i] = 2 * pow[i - 1];
        }

        divide(0, 0, N);

        System.out.println(answer);
    }

    static void divide(int x, int y, int n){

        if (n == 0) {

            if(x == r && y == c){
                answer = count;
            }

            count++;
            return;
        }

        int xx = x + pow[n - 1];
        int yy = y + pow[n - 1];
        int size = pow[n-1] * pow[n-1];

        if (r < xx && c < yy) {
            divide(x, y, n - 1);
        }
        else if(r < xx && c >= yy )
        {
            count += size;
            divide(x, yy, n - 1);
        } else if (r >= xx && c < yy) {
            count += (2 * size);
            divide(xx, y, n - 1);
        } else {
            count += (3 * size);
            divide(x + pow[n - 1], y + pow[n - 1], n - 1);
        }
    }

}

시간 제한 : 6초

메모리 제한 : 256MB

JAVA 라이브러리에는 PriorityQueue가 있어서 Heap 자료구조를 직접 구현하지 않아도 우선순위 큐를 쉽게 이용할 수 있습니다.

기본적으로는 최소 힙을 사용하며, 생성자에 Comparator.reverseOrder()을 두면 최대 힙을 사용할 수 있습니다.

저는 최소 힙과 최대 힙을 모두 사용하여 연산을 구현했습니다.
이때, 연산을 하다보면 두 우선순위 큐에 데이터가 불일치하게 됩니다. 따라서 저는 Map 자료구조를 사용하여 데이터의 개수를 체크해서 데이터를 일치시키도록 하였습니다.

// 최소 힙, 최대 힙, 데이터 개수를 저장할 Map, 현재 유지하는 데이터의 수
PriorityQueue<Integer> minQ = new PriorityQueue<>();
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
HashMap<Integer, Integer> dataCounter = new HashMap<>();
int Q_size = 0;

• 삽입 연산 구현 ( I )
  1. minQ, maxQ 모두에 데이터를 삽입합니다.
  2. 데이터의 수를 갱신합니다. ( dataCounter, Q_size 갱신 )
• 삭제 연산 구현
  • 삭제 연산
    1. Q_size로 큐가 비어있는지 확인하고, 비어있으면 연산을 종료합니다.
    2. minQ(또는 maxQ)의 가장 앞에 있는 데이터가 이미 삭제된 데이터인지 확인합니다.
       ( 만약 이미 삭제된 데이터인 경우, 버리고 다음 데이터로 1번 수행 )
    3. Q_size와 dataCounter 갱신 ( 각각 -1 )

import java.io.*;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

// 이중 우선순위 큐
public class BOJ7662 {

    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int T = Integer.parseInt(bufferedReader.readLine());

        while (T-- > 0) {
            int k = Integer.parseInt(bufferedReader.readLine());
            operate(k);
        }

        bufferedWriter.flush();
    }

    static void operate(int k) throws IOException {
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Comparator.reverseOrder());
        HashMap<Integer, Integer> dataCounter = new HashMap<>();
        int Q_size = 0;

        for (int i = 0; i < k; i++) {
            String s[] = bufferedReader.readLine().split(" ");
            char op = s[0].charAt(0);
            int val  = Integer.parseInt(s[1]);

            // Insert 연산
            if (op == 'I') {
                minQ.add(val);
                maxQ.add(val);
                Q_size++;

                if (dataCounter.containsKey(val)) {
                    dataCounter.replace(val, dataCounter.get(val) + 1);
                } else {
                    dataCounter.put(val, 1);
                }
            }

            if (op == 'D') {

                if (Q_size == 0) {
                    continue;
                }

                if (val == 1) {
                    Integer max = maxQ.poll();

                    while (dataCounter.get(max) == 0){
                        max = maxQ.poll();
                    }

                    dataCounter.replace(max, dataCounter.get(max) - 1);
                }

                if (val == -1) {
                    Integer min = minQ.poll();

                    while (dataCounter.get(min) == 0){
                        min = minQ.poll();
                    }

                    dataCounter.replace(min, dataCounter.get(min) - 1);
                }

                Q_size--;
            }
        }

        if (Q_size == 0) {
            bufferedWriter.append("EMPTY\n");
        } else {

            Integer min = minQ.poll();
            Integer max = maxQ.poll();

            while (dataCounter.get(min) == 0){
                min = minQ.poll();
            }

            while (dataCounter.get(max) == 0){
                max = maxQ.poll();
            }
            bufferedWriter.append(max + " ");
            bufferedWriter.append(min +"\n");
        }
    }


}

https://www.acmicpc.net/problem/7662

문제

N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,

색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.

시간 제한 : 1초

메모리 제한 : 128MB

DP[ i ] : i번째 숫자에서 연속부분최대곱

이전까지의 연속부분최대곱 x 현재 숫자를 했을 때 더 큰 값을 저장하도록 하면 연속부분최대곱을 구할 수 있습니다. 

이를 식으로 정리하면 다음과 같습니다.

dp[ i ] = Math.max(  num[ i ] , dp[ i -1 ] * num[ i ] )

주어진 예 ) 

i는 0일 때
연속부분최대곱은 1.1이므로  dp[0] = num[0] ( == 1.1 )이 됩니다. ( dp의 초깃값 저장 )

i = 1, num[1] = 0.7, dp[0] = 1.1 ) 

dp[0]  * num[1] = 1.1 * 0.7 = 0.77

0.77 > 0.7 이므로 dp[1] = 0.77

i = 2, num[2] = 1.3, dp[1] = 0.77 )

dp[1] * num[2] = 1.3 * 0.77 = 1.001

1.001 < 1.3 이므로 dp[2] = 1.3

i = 3, num[3] = 0.9 dp[2] = 1.3 )

dp[2] * num[3]  = 1.3 * 0.9 = 1.17

1.17 > 0.9 이므로 dp[3] = 1.17

... 이하 생략 

        for (int i = 1; i < dp.length; i++)
        {
            dp[i] = Math.max(num[i], num[i] * dp[i - 1]);
            maxValue = Math.max(maxValue, dp[i]);
        }

• 이 부분을 코드로 나타내면 위와 같습니다.
• dp 배열을 채워나가면서 가장 큰 값을 저장하였습니다. 

+ 자바에서 소수점 n번째 자리 반올림 하는 방법 

1) Math.round( ) 메서드 사용

• Math 클래스의 round() 메서드는 매개변수로 받은 값을 소수점 첫째 자리에서 반올림하여 long 형으로 리턴해주는 메서드입니다. 
• 무조건 소수점 첫째 자리에서 반올림하므로 주의가 필요합니다!

// 소수점 넷째 자리에서 반올림하려면 미리 1000을 곱한 후 다시 1000.0으로 나눠주어야 합니다.
double maxValue = Math.round(maxValue * 1000) / 1000.0;

2) String.format( ) 메서드 사용

• String 클래스의 format() 메서드도 format으로 지정한 부분까지 반올림을 해주는 메서드입니다. 
  ( String.format( "%.3f" , maxValue )로 지정하는 경우 소수점 넷째 자리에서 반올림 )

// 소수점 셋째 자리까지 출력
System.out.println(String.format("%.3f", maxValue));

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

public class BOJ2670 {

    static int n;
    static Double num[];
    static Double dp[];
    static Double maxValue = 0.0;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());

        num = new Double[n];
        dp = new Double[n];

        for (int i = 0; i < n; i++) {
            num[i] = Double.parseDouble(bufferedReader.readLine());
        }

        dp[0] = num[0];

        for (int i = 1; i < dp.length; i++)
        {
            dp[i] = Math.max(num[i], num[i] * dp[i - 1]);
            maxValue = Math.max(maxValue, dp[i]);
        }

        System.out.println(String.format("%.3f", maxValue));
    }
}

https://www.acmicpc.net/problem/2670

시간 제한 : 1초

메모리 제한 : 512MB

DFS를 재귀로 구현하였고, 세 번 이동할 수 있으므로 Depth가 3일 때까지 탐색을 진행했습니다. 문제 조건에 따라 해당 칸을 떠나는 즉시 장애물이 있는 칸으로 변경시키기 때문에 탐색이 끝난 후 다음 탐색에 영향을 주지 않으려면 장애물로 바꿨던 칸을 다시 바꿔주어야 합니다. 이를 해결하고자 재귀함수가 끝날 때마다 장애물로 바뀐 칸을 다시 원래 칸으로 바꿔주었습니다.

클래스 변수 ( 전역 변수로 사용 )

    static int mx[] = {0, -1, 0, 1};	// 좌, 상, 우, 하 이동을 위한 배열 mx
    static int my[] = {-1, 0, 1, 0};	// 좌, 상, 우, 하 이동을 위한 배열 my
    static int map[][] = new int[5][5];	// 입력받는 전체 보드
    static int start_x, start_y;		// x, y 좌표 시작 위치
    static int result;					// 결과값

메인 메서드 : 입력을 받고 findApple() 메서드를 호출하여 결과를 저장한 후 출력

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
        // 사용자의 입력을 공백으로 나누어 받습니다.
        for (int i = 0; i < 5; i++) {
            String s[] = bufferedReader.readLine().split(" ");
            for (int j = 0; j < 5; j++) {
                map[i][j] = Integer.parseInt(s[j]);
            }
        }

        String[] split = bufferedReader.readLine().split(" ");
        start_x = Integer.parseInt(split[0]);	// 탐색 시작 x좌표 저장
        start_y = Integer.parseInt(split[1]);	// 탐색 시작 y좌표 저장 
		
        // 탐색 시작 지점과 현재 depth, 현재 apple의 수를 매개변수로 넘겨 메서드 호출
        findApple(start_x, start_y, 0, 0);
		
        System.out.println(result);	// 결과 출력
    }

재귀 메서드 : findApple(int x, int y, int depth, int apple) 

    public static void findApple(int x, int y, int depth, int apple) {
        // 이동한 칸이 사과면 apple 값을 하나 더해줌
        if (map[x][y] == 1) {
            apple++;
        }

        // 세 번 이동하는 경우 탐색 종료
        if (depth == 3) {
            // 사과를 두개 이상 먹은 경우 결과를 1로 바꿔줌
            if (apple >= 2) {
                result = 1;
            }
            return;
        }

        // 좌, 상, 우, 하 방향으로 이동하면서 dfs 수행
        for (int i = 0; i < 4; i++) {
            int xx = x + mx[i];
            int yy = y + my[i];

            // 배열의 범위 밖으로 벗어나거나 벽인 경우 이동을 안 함
            if (xx < 0 || xx >= 5 || yy < 0 || yy >= 5 || map[xx][yy] == -1) {
                continue;
            }

            // 지금 이동한 칸으로 다시 돌아올 수 없으므로 임시로 벽을 세움
            map[x][y] = -1;
            findApple(xx, yy, depth + 1, apple);
            // 다음 번의 탐색에는 세운 벽을 다시 없앰
            map[x][y] = 0;
        }



    }

• for문 내에서 다음 좌표로 이동한 후 장애물(벽)을 세우고 해당 메서드가 끝나면 다시 장애물을 없애줍니다.
  ( map[x][y] = 0 ) 

https://www.acmicpc.net/problem/26169