알고리즘

 

- 문제를 해결하기 위한 절차. (절차가 없다면 알고리즘이 아니다..!)

* 의사 코드와 순서도를 이용해 많이 표현된다.

 

 

1. 알고리즘 평가 기준

• 정확도 - 답을 정확하게 찾아내는지
• 작업량 - 얼마나 적은 작업(할당, 연산 등)으로 정답을 찾아내는지 (속도)
• 메모리 사용량 - 얼마나 적은 메모리를 사용하는지

1) 시간 복잡도

if ) 1부터 n까지 모든 자연수의 합을 구한다.

// 총 수행되는 할당 및 연산 : 2*n + 1
public static int sumUntilN(int n) {
		// 할당 1번
        int sum = 0;
        for (int i=1; i<=n; i++) {
            sum += i; // 매 반복마다 덧셈1번, 할당1번
        }
        return sum;
} 


    // n * (n+1) / 2 를 하면 1부터 n까지의 자연수를 합한 것과 동일하다.
    public static int sumUntilN2 (int n) {
    // n+1 : 1번
    // *n : 1번
    // /2 : 1번
        return n*(n+1)/2;
    } 
    // 고정된 연산 횟수 3번

 

 

총 걸린 시간의 차이가 있다.

 

 

2) Big-O Notation 

: 알고리즘이 문제를 해결하는데 걸리는 상한선을 기준으로 표현된 시간 복잡도.

- 최고차항만 남긴다. (종국에 가서는 최고차항의 영향력이 다른 모든것보다 더 커지기 때문이다..)

- 가장 많은 계산이 일어났을 때 상황을 바탕으로 표시. 

 

 

2. 문자열 다루기

1) 문자열 한글자씩 가져오기

• string.toCharArray() : 문자열을 구성하는 char[]을 반환
• string.charAt(int index) : 문자열의 index번째 char을 반환

public class Solution {
    public String solution(String str1, String str2) {
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        String answer = "";
        for (int i = 0; i < chars1.length; i++) {
            answer += chars1[i];
            answer += chars2[i];
        }

        return answer;
    }
}


public class Solution {
    public String solution(String str1, String str2) {
        String answer = "";
        for (int i = 0; i < str1.length(); i++) {
            answer += str1.charAt(i);
            answer += str2.charAt(i);
        }

        return answer;
    }
}

 

2) StringBuilder

: '+' 연산자는 뒤에 덧붙이는 것처럼 보이긴 하지만, 사실은 새로운 문자열 객체를 만든다. (성능상 문제) 

>> StringBuilder를 사용하면 문자열 뒤쪽에 append 메서드를 통해 데이터를 추가할 수 있다.

// +연산자 사용
public class Solution {
    public String solution(String str1, String str2) {
        String answer = "";
        for (int i = 0; i < str1.length(); i++) {
            answer += str1.charAt(i);
            answer += str2.charAt(i);
        }
        return answer;
    }
}

// StringBuilder 사용
class Solution {
    public String solution(String str1, String str2) {
        // 문자열을 만들기 위한 StringBuilder
        StringBuilder lineBuilder = new StringBuilder();
        for(int i = 0; i < str1.length(); i++) {
            lineBuilder.append(str1.charAt(i));
            lineBuilder.append(str2.charAt(i)); //append()를 통해 덧붙일 데이터 전달 가능
        }
        return lineBuilder.toString();
    }
}

왼: + 연산자 사용                                                                                 오 : StringBuilder 사용                                                        

 

 

3) BufferedReader

- Scanner를 사용하면 입력 받는데 시간이 오래 걸릴 수 있다. >> BufferedReader 활용.

- .readLine()을 통해 한줄을 문자열로 입력받는다. + IOException 발생할 수 있어 throws를 추가해주어야 한다.

- new BufferedReader를 선언하며, 인자로 new InputStreamReader()를 전달.

- InputStreamReader는 어떤 데이터 입력을 읽어들이는 역할.

public class Main {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String input = br.readLine();
    }
}

 

4) string.split(" ")

- 정규 표현식을 인자로 전달하여 해당 정규 표현식을 기준으로 문자열을 나눈다.

- 과거에는 StringTokenizer라는 클래스를 이용해 입력받은 문자열을 토큰 단위로 나눠서 사용하는 방법이 있었으나, 현재는 split() 메서드가 성능적 측면에서 더 뛰어나다고 평가받는다.

public class Main {
	public static void main (String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String line = br.readLine();
        String[] inPiecesRaw = line.split(" ");
        int[] inPieces = new int[6];
        for (int i=0; i<6; i++) {
        	String piecesRaw = inPiecesRaw[i];
            inPieces[i] = Integer.parseInt(pieceRaw);
        }
    }
}

 

3. 2차원 배열

: 배열을 선언하는 과정에서 대괄호를 두번 사용해 정의할 수 있다. 

- 각 원소를 순회하고 싶으면 이중반복을 이용해 각 원소에 접근 가능.

 

public class Main {
    public static void main(String[] args) {
        // 3 * 3의 크기의 행렬
        int[][] matrix = new int[3][3];

        // 1부터 9까지, 각각 행렬에 할당해보자.
        int num = 1;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                matrix[i][j] = num;
                num++;
            }
        }
    }
}

// 중괄호 중첩으로 만들 수도 있다.
public class Main {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
    }
}

 

- 델타 탐색 : 4개의 방향에 따라 변화하는 좌표값을 따로 저장해서 배열 탐색에 활용할 수 있다.

int[][] deltas = new int[][]{
        // N
        {-1, 0},
        // S
        {1, 0},
        // W
        {0, -1},
        // E
        {0, 1}
};

for (String route : routes) {
    String[] routeInfo = route.split(" ");
    int distance = Integer.parseInt(routeInfo[1]);
    int dIndex = getDirIndex(routeInfo[0]);
    int[] delta = deltas[dIndex];
    if (!checkBounds(
            answer[0] + delta[0] * distance,
            answer[1] + delta[1] * distance,))
         continue;
    // 생략
}