늘 겸손하게

유클리드 호제법 ( Euclidean algorithm ) 두 정수 A, B의 최대공약수를 구하는 알고리즘입니다. 원리 두 정수 a, b가 주어졌을때, a를 b로 나눈 나머지를 r이라고 하자. a, b의 최대공약수를 (a, b)라고 하면, 다음이 성립한다. (a, b) = (b, r) ex) (1071, 1029) = (1029, 42) = (42, 21) = (21, 0) = 21 코드 public int gcd(int p, int q) { if (q == 0) return p; return gcd(q, p % q); } 팁 : 큰 숫자를 첫 번째 인자로 주어야 불필요한 재귀 1번을 아낄 수 있다.

버블 정렬 배열 정렬 알고리즘으로 거품이 수면 위로 올라오듯이 배열을 정렬한다 해서 버블 정렬이라는 이름이 붙여졌다. 버블 정렬 구현 길이가 n인 배열이 주어졌을때 오름차순으로 정렬하려면 1. 인덱스 0번 요소와 바로 오른쪽 요소값을 비교하여 0번 요소가 더 크면 두 값을 교환(swap) 2. 인덱스 1, 2, 3, ... n - 2번 요소에 대해 1번 과정 반복하면 배열의 최대값이 마지막에 배치된다. 3. 인덱스 1, 2, 3, ..., n - 3번 요소로 위 과정 반복 4. 인덱스 1, 2, 3, ..., n - 4번 요소로 위 과정 반복 5. 오름차순으로 정렬됨. 코드 public static void main(String[] args) { int [] arr = {9, 4, 6, 1, 14, 5}..

코딩테스트 문제를 풀다보면 순열, 조합 혹은 중복순열, 중복조합을 활용해야 하는 경우가 종종 있다. 하나하나 정리해보자. 1. 순열 순열은 주어진 n개의 원소에서 순서에 상관있게 r 개를 나열하는것을 말합니다. 예로 1, 2, 3, 4 에서 2개의 원소를 뽑아 나열하는 경우 1, 3 3, 1 은 다른 경우가 됩니다. 두 경우 모두 1과 3으로만 이루어져 있지만 순서가 다르기 때문에 다른 경우로 봅니다. 경우의 수는 총 nPr = n! / (n - r)! 구현 방식 백트래킹 방식으로 구현 가능하며 한 번 방문한 요소는 다시 방문할 필요가 없으므로 visit 배열을 활용해 방문하지 않은 원소 위주로 탐색합니다. depth를 1씩 늘려가며 이전에 방문하지 않은 요소를 정답 기록용 배열 (int[] rec) 에..

안녕하세요 besforyou입니다 백준 문제 10709번 문제 풀이를 설명하겠습니다 문제 풀이 c가 나온 지점으로부터 오른쪽으로 얼마나 떨어져 있는지를 알아내어 출력하는 문제입니다. 이 문제에 dp 알고리즘을 적용하면 O(H*W) 시간안에 풀어낼 수 있습니다. 1. 구름의 위치 입력값을 받을 2차원 배열 cloud와 정답을 기록할 2차원 배열 ans를 생성합니다. 2. 2차원 배열 ans의 모든 원소값은 -1로 초기화합니다. (memset 이용) 3. 2차원 배열 cloud에 모든 입력값을 저장합니다. 4. for문을 이용하여 cloud의 모든 원소를 순차적으로 참조하는데, 1. 해당 cloud 좌표에 c가 있는 경우 : 0 2. c가 참조되지 않았지만 이전 원소가 -1이 아닌 경우(c가 이전에 이미 읽..