gaeggu's blog gaeggu's blog

최소 공배수와 최대 공약수를 구할 수 있다면 쉽게 풀 수 있다. 최소공배수(LCM, Least Common Multiple)는 최대공약수(GCD, Greatest Common Divisor)를 이용해서 구할 수 있다. public int LCM(int x, int y) { return x * y / GCD(x, y); } 최대공약수는 유클리드 호제법을 통한 재귀용법으로 구현할 수 있다. public int GCD(int x, int y) { if (y == 0) { return x; } return GCD(y, x % y); } 배열에 주어진 수들의 최소 공배수는 배열에 있는 모든 수를 곱하고 공통의 최대공약수를 나누면 된다. 예를 들어 {2, 4, 6, 8}의 공통 최대공약수는 직관적으로 2라는 것을 ..

첫 번째 줄에 동전 종류의 개수 n 두 번째 줄에 동전의 종류가 n개 세 번째 줄에 거슬러 줄 돈 change가 주어질 때 거슬러 줄 동전이 최소가 되는 개수를 출력하라. intput) 3 1 3 5 15 output) 3 import java.util.*; public class Main { static int n, change, min = Integer.MAX_VALUE; static int[] arr; private static void solution(int cnt, int change) { if (min = 0; i--) { if ..

퀵 정렬은 합병 정렬과 함께 대표적인 분할 정복 알고리즘 중 하나이다. 여기서 분할 정복 알고리즘이란 하나의 큰 문제를 여러 개의 작은 문제로 나누어 문제를 해결하는 알고리즘을 뜻한다. 퀵 정렬은 특정 값을 기준으로 작은 값과 큰 값을 나눈다. 이때의 기준값을 피벗(pivot)이라 한다. 예시를 통해 살펴보자. 예시 다음 숫자들을 오름차순으로 정렬하라. 1. 분할 오름차순으로 정렬하기 위해서는 피벗보다 작은 값은 피벗 왼쪽에 피벗보다 큰 값은 피벗의 오른쪽에 와야 한다. 그리고 이를 위해서 배열 양쪽에 포인터를 두고, 왼쪽 포인터는 피벗보다 큰 값이 나올 때까지 이동하고 오른쪽 포인터는 피벗보다 작은 값이 나올 때까지 왼쪽으로 이동하며 값을 교환한다. 아래 그림을 보면 왼쪽 포인터는 피벗보다 큰 값을 찾..

개념 삽입 정렬은 특정 원소의 앞에 있는 원소들이 이미 정렬되어 있다는 가정 하에 앞에 원소에서 적절한 위치에 특정 원소를 삽입하는 정렬 방식이다. 예제를 살펴보면서 삽입 정렬이 어떻게 수행되는지 살펴보자. 예제 다음 숫자들을 오름차순으로 정렬하라. 삽입정렬에서는 앞에 있는 원소들이 정렬되어 있는 것을 가정하기 때문에 자신보다 작은 수(오름차순 시 우선순위가 높은 원소)를 만나면 바로 그 뒤가 삽입되어야 할 위치이고, 그 전까지는 큰 수를 만나면 하나씩 자신보다 뒤로 밀어낸다고 생각하면 된다. 10 앞에는 삽입할 위치가 없으니 3부터 시작해보자. 3 앞에 있는 원소들이 정렬되어 있다는 가정하에 3 은 어디에 삽입되어야 할까? 인접한 원소부터 앞으로 차례차례 비교해보면 10은 3보다 크고, 그 앞에는 비교..

개념 버블 정렬은 바로 옆에 있는 값과 비교해서 우선 순위가 높은 값을 앞으로 보낸다. 예제 다음은 5개의 정수 배열 {5, 3, 4, 2, 1} 을 오름차순으로 버블 정렬하는 과정을 보여준다. 다음 그림과 같이 인접한 두 수를 비교하고 앞에 있는 수가 뒤에 있는 수보다 클 때 교환하는 과정을 반복하며 끝까지 진행하면 가장 큰 수인 5가 맨 뒤에 오게 된다. 이렇게 되면 첫 번째 순회가 끝난다. 그 이후에는 마지막 인덱스를 제외하면서 계속 순회하며 정렬하는 과정을 반복한다. 구현 class Sort { public static void bubbleSort(int[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = 0; j < arr.length -..

개념 주어진 값들 중 최솟값을 선택해서 배열의 맨 앞의 값과 교환한다. 그리고 맨 앞을 제외한 나머지 중에서 최솟값을 선택하고 교환하는 과정을 반복한다. 예제 {5, 4, 3, 2, 1} 로 이루어진 배열을 오름차순으로 선택 정렬하는 순서이다. 파란색 화살표는 주어진 범위에서 최소값이 위치할 공간을 가리키며, 빨간색 화살표는 최솟값을 가리킨다. 두 화살표가 가리키는 공간에 있는 값끼리 교환(swap)이 일어난다. 코드 class Sort { public static void selctionSort(int[] arr) { int min; int idx = 0; for (int i = 0; i < arr.length; i++) { min = Integer.MAX_VALUE; for (int j = i; j ..

코딩테스트 연습 - 문자열 다루기 기본 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 a234이면 False를 리턴하고 1234라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 이�� programmers.co.kr [문제 설명] 문자열의 길이가 4 또는 6이면서, 숫자로만 구성되어 있는지를 확인하는 함수를 작성하라. [제한 사항] s는 길이 1 이상, 길이 8 이하이다. [고민] - 문자형 '0'과 '9'를 상수로 변경하는 것이 더 나은 결정인가? Class Solution { private final char ZERO = '0'; private final char NINE = '9'; public boolean so..

문제에 대한 설명은 아래 링크에서 볼 수 있다. 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 [sun, bed, car]이고 n이 1이면 각 단어의 인덱스 1� programmers.co.kr [기본 설명] 문자열로 구성된 배열을 각 문자열의 특정 인덱스를 기준으로 오름차순 정렬을 구현하는 문제이다. (단, 두 문자열의 인덱스가 같을 경우 사전 순으로 정렬) [개선 사항] 1. 파라미터인 strings를 Arrays.sort() 메소드를 이용해 정렬하고 정렬된 파라미터를 반환하는 것으로 구현 => 파라미터를 정렬한다면 String 배열을 반..