Algorithm & PS/Algorithm

알고리듬 - Next Permutation

Permutation 관련 문제를 푸는데 더 빠른시간에 푼 코드를 확인해보니 Next Permutation(NP)을 사용하고 있었다. 특정 조건을 만족한다면 NP를 활용하는 것이 좋아보여서 이에 대한 내용을 작성하고자 한다. 다음 순열(Next Permutation) Next Permutation(이하 NP)은 순열을 순차적으로 탐색하는 알고리듬이다. 특징 재귀를 활용하지 않는다. 재귀를 활용한 순열 탐색보다 속도가 빠르다. 사전 순 정렬이 된 상태에서 탐색을 시작해야 온전히 모든 순열을 구할 수 있다. 특정 개수의 순열을 뽑을 수 없다. 동작 과정 NP의 동작 과정은 아래와 같다. 배열의 가장 오른쪽에서 시작해 왼쪽으로 가며 값이 작아지는 순간의 인덱스(Pivot)을 구한다. 배열의 가장 오른쪽에서 시..

알고리듬 - 맨해튼 거리, 유클리드 거리

문제를 풀던 중 맨해튼 거리라는 개념을 처음 보았다. 이 글을 작성할 지에 대해 고민했는데 작성해 둬서 나쁠 것이 없으니 간단하게나마 정리하고자 한다. 맨해튼 거리 맨해튼 거리(Manhattan distance)는 직교 좌표계에 일정한 좌표축의 점 위에 투영한 선분 길이의 합을 말한다. 간단히 표현하자면 가로, 세로로만 이동했을 때 거리의 합이다. 자세한 내용은 아래에서 확인할 수 있다. https://ko.wikipedia.org/wiki/%EB%A7%A8%ED%95%B4%ED%8A%BC_%EA%B1%B0%EB%A6%AC 맨해튼 거리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 맨해튼 거리와 유클리드 거리의 비교: 맨해튼 거리인 빨간색, 파란색, 노란색 선의 길이는 모두 12이..

알고리듬 - 순열

프로그래머스 2단계에 순열을 활용하는 완전탐색 문제가 보여서 이에 대한 전반적인 내용을 정리하고자 한다. 순열(Permutation) 순열이란 서로 다른 n개 중 r개를 골라 순서를 고려해 나열한 경우의 수이다. 순열의 계산은 아래와 같이 한다. 순열의 개수 계산 구현 식만 알고 있으면 순열의 수 계산을 구현하는 것은 어렵지 않다. public class Main { public static void main(String[] args) { System.out.println(calculatePermutation(10, 3)); } static int calculatePermutation(int n, int r) { int sum = 1; for(int i = 0; i < r; i++) sum *= n--;..

알고리듬 - 순위 매기기

알고리듬 문제를 푸는데 순위를 매겨야 할 때마다 막혀서 이에 대해 정리하고자 한다. 순위 매기기 아래의 배열에 대해 큰 순서대로 순위를 매겨보자. int[] arr = {12, 34, 46, 37, 21, 48, 53, 35, 19}; 먼저 순위 정보를 담을 배열을 생성한다. int[] rank = new int[arr.length]; 다음으로 아래의 이중 for문을 돌린다. for(int i = 0; i < arr.length; i++) { rank[i] = 1; for(int j = 0; j < arr.length; j++) if(arr[i] < arr[j]) rank[i]++; } 한 값을 다른 값과 비교해 가면서 조건이 맞으면 순위 값을 1 증가시킨다. 조건은 상황에 맞게 바꾸면 된다. 전체 코드..

알고리듬 - 최대 공약수 & 최소 공배수 구하기(유클리드 호제법)

최대 공약수(GCD: Greatest Common Divisor)와 최소 공배수(LCM: Lowest Common Multiple) 를 구하는 방법에 대해 알아보자. 유클리드 호제법 유클리드 호제법(Euclidean-Algorithm)은 주어진 두 값의 최대 공약수를 구하는 알고리듬이다. 계산은 MOD 연산(%)을 활용한다. 진행 과정은 아래와 같다. 1. 주어진 두 값 중 큰 값을 작은 값으로 MOD 연산한다. 2. 앞의 과정에서 작은 값을 MOD 연산의 결과로 MOD 연산한다. 3. 결과가 0이 나오면 종료한다. 아래는 120과 34의 최대 공약수를 구한 예이다. 구현 내용이 어렵지 않아 바로 구현해 보았다. 전체 코드 package practice; public class GCD { public s..

알고리듬 - 소수 구하기(에라토스테네스의 체)

코딩 테스트 문제를 푸는 중 소수를 구해야 하는 상황이 종종 있어서 소수를 구하는 방법을 정리하고자 한다. 에라토스테네스의 체 에라토스테네스의 체는 소수를 구하는 대표적인 방법이다. 해당 방법은 수학자 에라토스테네스가 발견한 것으로 동작 과정은 아래와 같다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수 ko.wik..

알고리듬 - 깊이 우선 탐색, 너비 우선 탐색

깊이 우선 탐색(DFS: Depth-First Search)과 너비 우선 탐색(BFS:Breadth-First Search)은 그래프 완전 탐색 기법 중 하나이다. 이 둘에 대해 알아보자. 깊이 우선 탐색(DFS) DFS는 그래프의 시작 노드에서 출발해 한쪽 분기를 최대 깊이까지 탐색한 후 다른 쪽 분기를 탐색하는 형식이다. 방문한 정점을 시작 정점으로 하여 다시 탐색을 진행하는 방식으로 진행한다. DFS는 노드 수를 V, 간선 수를 E라고 했을 때 그래프가 인접 리스트로 구현되었으면 시간복잡도가 O(V + E), 그래프가 인접 행렬으로 구현되었으면 시간복잡도가 O(n2)이다. 동작 그림으로 보자. 아래와 같은 그래프가 있고 정점 0을 시작 정점으로 하였다. 정점 1을 먼저 탐색한다고 했을 때, 다시 정..

알고리듬 - 합병, 퀵, 기수 정렬

합병, 퀵, 기수 정렬은 앞서 알아본 버블, 선택, 삽입 정렬에 비해 구현이 어려운 대신 좋은 성능을 가지고 있다. 이에 대해 알아보자. 합병 정렬 합병 정렬(Merge Sort)은 분할 정복(Devide and Conquer)을 이용해 정렬을 하는 방식이다. 진행 과정은 아래와 같다. 1. 주어진 배열을 반으로 나눈다. 2. 왼쪽 배열과 오른쪽 배열을 각각 정렬한다. 3. 두 배열을 합쳐 하나의 정렬된 배열을 만든다. 합병 정렬은 배열을 각각 정렬할 때 재귀를 이용하는데 배열을 반으로 나누고 그 배열을 다시 반으로 나누면서 해결해야 하는 문제를 줄인다.(D&C) 먼저 전체 과정을 그림으로 보자. 합병 정렬은 분할 정복을 거쳐 정렬을 한다. 다음은 Merge 과정이다. 각 배열을 가리키는 포인터를 이용한..