코딩 테스트/자료구조 & 알고리즘

그리디 (Greedy) 알고리즘이란?그리디(Greedy)는 사전적으로 '탐욕적인'이라는 뜻이다.그리디 알고리즘은 말 그대로 탐욕적인 알고리즘이다.  그리디 알고리즘은 현재 상황에서 가장 최적의 해를 선택을 하며 선택을 번복하지 않는다.이러한 특성을 가지고 지역 최적해를 추구한다고 이야기 하기도 한다.이렇게 선택을 반복해 하나의 문제를 푸는 알고리즘이다. 하지만 그리디 알고리즘을 모든 상황에서 적용가능한 것은 아니다. 현재 상황의 최적의 해가 전체 상황의 최적의 해를 보장하는 것은 아니기 때문이다.  그렇다면 해당 문제가 그리디 알고리즘으로 해결이 가능한지 어떻게 알 수 있을까?그리디 알고리즘으로 문제를 해결하기 위해선 다음의 두 가지 조건을 만족해야한다.1. 최적 부분 구조: 부분해를 구하는 과정이 최적..

동적 계획법(Dynamic Programming)이란?동적 계획법이란 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고 이를 활용하여 전체 문제를 해결하는 방법이다.하지만 동적 계획법은 작은 부분 문제들을 통해 전체 문제를 해결한다고 해도 반드시 효율적인 것은 아니다.동적 계획법을 효율적으로 사용하기 위해선 다음의 두 가지 조건을 만족해야 한다.1. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복적으로 등장해야 한다.2. 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구할 수 있어야 한다. 어떠한 문제를 다음과 같이 작은 문제로 나누었다고 해보자.A, B, C, D의 작은 문제로 하나의 전체 문제를 푼다고 했을 때, 이 경우는 동일한 작은 문제가 반복적으로 등장하지 않..

1. 행렬의 덧셈과 뺄셈각 행렬에서 같은 위치에 있는 값끼리 더하거나 빼는 연산이다.이때 두 행렬의 크기는 같아야 한다. 행렬의 덧셈과 뺄셈을 자바로 구현하면 다음과 같다.// 행렬의 덧셈public static void matrixSum(int[][] arr1, int[][] arr2) { if(arr1.length != arr2.length || arr1[0].length != arr2[0].length){ System.out.println("두 행렬의 크기가 같지 않습니다."); return; } int[][] result = new int[arr1.length][arr1[0].length]; for(int i = 0; i 시간복잡도O(N^2)  2. ..

정렬이란?정렬(sort)이란 사용자가 정의한 순서로 데이터를 나열하는 것이때 사용자가 정의한 순서는 오름차순이나 내림차순일 수도 있고 임의 조건일 수도 있다. 정렬은 원하는 데이터를 쉽게 찾기 위해 필요하다. 예를 들어, 다음의 두 가지 데이터가 있다고 해보자.정렬된 데이터: [1, 3, 5, 7, 9]정렬되지 않은 데이터: [1, 5, 7, 9, 3]여기서 데이터의 중앙값을 찾는다고 할 때 어떤 데이터가 더 찾기 쉬울까?바로 정렬된 데이터이다.정렬된 데이터는 그냥 인덱스의 중앙값만 보면 된다. 반면 정렬되지 않은 데이터는 모든 데이터를 확인하며 찾아야 한다. 이 세상에는 수 많은 정렬 알고리즘이 존재한다.정렬 알고리즘은 시간복잡도로 분류할 수 있는데 지금부터 그 시간 복잡도별로 정렬 알고리즘에 대해 이..