Etc./Algorithm

유클리드 호제법(Euclidean Algorithm)

유클리드 호제법 유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 고통된 소수둘의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다. 핵심이론 유클리드 호제법을 수행하려면 MOD연산을 이해하고 있어야 한다. 연산 기능 예제 MOD 두 값을 나눈 나머지를 구하는 연산 10 MOD 4 = 2 MOD 연산으로 구현하는 유클리드 호제법 1) 큰수를 작은수로 나누는 MOD 연산을 수행한다. 2) 앞 단계에서의 작은 수와 MOD 연산 결괏값으로 MOD연산을 수행한다. 3) 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다. 손으로 풀어보기 코드로 구현하기 public int Euclidean(int N, int..

에라토스테네스(Eratosthenes)의 체

소수란? 소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다. 이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다. 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체가 있다. 에라토스테네스의 체 원리를 살펴보자. 에라토스테네스의 체 원리 1) 구하고자 하는 소수의 범위만큼 1차원 배열을 생성2) 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.3) 배열의 끝까지 (2)를 반복한 후 배열에 남아 있는 모든 수를 출력한다. 1부터 30까지의 수 중 소수를 구하는 예시를 보면서 원리를 이해해보자. 1) 먼저 주어진 범위까지 배열을 생..

[알고리즘] 슬라이딩 윈도우(sliding window) 알고리즘 이란?

슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 알고리즘과 유사하지만 부분 배열의 길이가 고정적이다. 고정적인 틀을 오른쪽으로 밀어 오면서 틀 안에 있는 값들을 부분배열이라고 생각하면 된다. 투 포인터 알고리즘은 두 개의 포인터를 이동하기 때문에 2개의 변수가 필요하지만 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 하기 때문에 1개의 변수만 필요하다. 설명 아래 노란색 칸이 3의 고정길이를 가지는 부분 배열이라 가정, 주어진 문제가 부분 배열의 합을 구하는 것이라 하면 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에 겹치는 부분이 존재한다. 즉 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가하면 된다. 예시 2가지 긴..

[알고리즘] Two Pointers 알고리즘이란?

투포인터 알고리즘이란? 투포인터 알고리즘 또는 슬라이딩 윈도우라고 부른다. 1차원 배열이 있고, 배열에서 각자 다른 원소를 카리키고 있는 2개의 포인터를 조작하면서 원하는 값을 얻는 방법이다. 설명 1. 포인터 2개를 준비 , start_index , end_index 2. 항상 start_index

[알고리즘]Prefix sum 알고리즘이란?

누적합(Prefix sum)란? 나열된 수의 누적된 합을 말한다. 배열의 일부 구간에서 대한 합을 매우 빠르게 구할 수 있게 해준다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 누적합을 이용하면 부분합을 0(N+M)으로 구할 수 있다. 설명 1차원 배열 arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. 활용법 arr의 i항부터 j항 까지 합을 S(i,j)라고 하자. 이때 S(ij) = sum[j] - sum[i-1]이다. S(2,4) = S[4]=S[1]이다. 쉽게 생각하면 참고문제) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 ..

[알고리즘] Time Complexity(시간 복잡도) 알아보기

Time Complexity(시간 복잡도) 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 쉽게 말해서 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 시간 복잡도 정의하기 시간 복잡도 유형 빅-오메가(-Ω(n)): 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-세타(θ(n)): 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅-오(O(n)): 최악일 때(worst case)의 연산횟수를 나타낸 표기법 코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까? 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다. 실제 테스트에서는..

[알고리즘] JAVA (String, StringBuilder,List,Collections)메소드 정리

String 관련 메소드 String str = "abcde"; str.length() // str의 길이 반환 str.isEmpty() // str의 길이가 0이면 true, 아니면 false str.charAt(2) // 인덱스로 문자 찾기, c 반환 str.indexOf("c") // 문자로 첫번째 인덱스 찾기, 2 반환 str.lastIndexOf("c") // 문자의 마지막 인덱스 찾기, 2 반환 str.substring(2, 4) // 2~3 위치의 문자열 "cd" 반환 str.substring(3) // 3부터 끝까지의 문자열 "de" 반환 str.replace('b', 'k') // b를 k로 변경 (akcde) str.equals("abcde") // str과 abcde를 비교해서 같으면..