알고리즘

[SWEA][모의 SW 테스트] 2105 - 디저트 카페 (자바/Java)

대각선으로 사방탐색을 하는 문제다. 주의해야할 조건은 같은 숫자의 디저트를 만나면 안된다. 시작점을 제외하고 이미 방문했던 곳은 다시 방문할 수 없다. 시작점으로 돌아오도록 사각형이 그려져야 한다. 최대한 많은 디저트를 먹어야 한다. map의 좌표가 N일 때, 대각선으로 투어를 해야하기 때문에 양 끝 꼭짓점에서는 순회를 시작할 수 없다. 가장 큰 사각형의 가로 세로의 합은 N-1이다. 위 사진에서 N은 5고, 두 사각형이 가능한 최대 길이의 사각형이다. 왼쪽의 경우 가로가 3, 세로가 1이고 오른쪽은 가로가 2, 세로가 2다. 일직선이나 자기 자신만 투어하는 경우는 불가능하기 때문에 사각형의 한 변의 최소 길이는 1, 최대 길이는 N-2가 될 것이다. 이를 활용해서 두 변의 길이의 합이 최대일 때부터 최..

[알고리즘] 비트 연산자 & 부분집합 (자바/Java)

비트 연산자 &둘 다 1 이면 1 / 해당 비트가 있는지 검사! System.out.println(3 & 5); // 3 = 011 // 5 = 101 // -------- // 001 -> 1 | 하나라도 1이면 1 System.out.println(3 | 5); // 3 = 011 // 5 = 101 // -------- // 111 -> 7 ^ XOR - 서로 다르면 1 System.out.println(3 ^ 5); // 3 = 011 // 5 = 101 // -------- // 110 -> 6 A >1); // 5 / (2^1) = 2 // 101 -> 010 = 2 부분집합 N개의 원소를 가진 집합에서 전체 부분집합의 개수 = 2^N 1. 재귀 부분집합은 공집합부터 원소가 1개, 2개, … ..

[알고리즘] 너비 우선 탐색 BFS & 깊이 우선 탐색 DFS (자바/Java)

목차 BFS & DFS 그래프에서 모든 정점을 방문하는 방법 [참고] 그래프의 인접 노드 구현 1. 인접 행렬 n * n 행렬에 (i, j) (j, i)에 1 (또는 가중치)를 할당 장점 이해하기 쉬움 간선의 존재 여부를 빠르게 알 수 있음 단점 n^2에 해당하는 공간이 필요 모든 원소를 채우는 데에도 시간이 오래 걸림 2. 인접 리스트 보통 연결 리스트를 사용, 각 정점마다 인접한 정점들을 연결 리스트에 표현 장점 행렬에 비해 공간 낭비가 없다. (간선의 총 수에 비례하는 양만큼만 공간이 필요) 단점 만약 거의 모든 정점에 대해 간선이 존재한다면 (dense) 연결 리스트의 정보를 표현하기 위한 오버헤드가 많이 든다. 간선이 존재하는지 알아볼 때 리스트에서 차례로 훑어야 하기 때문에 인접 행렬보다 시간..

[알고리즘] 기본 수학 - 순열 조합 중복순열 중복조합 (자바/Java)

순열/조합 순열, 조합, 중복 순열, 중복 조합을 dfs를 이용하여 구할 수 있다. 백준의 N과 M시리즈가 순열/조합을 공부하기 좋은 문제들이다. https://www.acmicpc.net/workbook/view/2052 1. 순열 순열은 N개의 수에서 R개의 수를 뽑아 순서대로 나열하는 것이다. {1, 2, 3, 4} 4개의 수에서 2개의 수를 뽑아 나열하는 경우의 수는 {1, 2} {1, 3} {1, 4} {2, 1} {2, 3} {2, 4} {3, 1} {3, 2} {3, 4} {4, 1} {4, 2} {4, 3} 의 12가지다. $$ nPr = n*(n-1) * ... (n-r+1) $$ 순열을 구하기 위해서는 dfs를 활용한다. static void dfs(int N, int M, int cn..

[알고리즘] 조합론 - 이항 계수 (자바/Java)

목차 조합론 이항계수 https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients 정의 이항 계수는 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 의미한다. 즉 nCr을 구하는 알고리즘이다. 구현 1: 팩토리얼 이용 $$ nCk = \frac{n!}{{n-k}!*k!} $$ 첫 번째 정의는 팩토리얼 재귀함수를 이용하여 알고리즘으로 구현할 수 있다. public class MyBinoCo { public static void main(String[] args) { int N = 10; int K = 3; // 팩토리얼 System.out.println(fact(N) / fact(N - K) / fact(K))..

[알고리즘] 삽입 정렬 Insertion Sort (자바/Java)

목차 삽입 정렬 0번째부터 i번째까지 정렬된 배열의 크기를 증가시키며 정렬하는 알고리즘 이미 정렬된 i개짜리 배열에 하나의 원소를 더하여 정렬된 i+1개짜리 배열 만들기! 시간 복잡도: $O(n^2)$ 과정 i번째 원소를 정렬할 차례 i-1번째까지의 원소들은 정렬되어 있음 i-1부터 0까지의 원소들과 i번째 원소(key)를 비교하며, i번째 원소보다 작은 원소를 만나면 break, i번째 원소보다 크다면 해당 원소를 오른쪽으로 한 칸씩 shift break한 원소 다음 자리에 i번째 원소를 삽입 1부터 마지막 원소까지 반복 1 0번째 원소는 정렬된 상태 i=1, 10 10..

[알고리즘] 카운팅 정렬(Counting Sort) (자바/Java)

목차 카운팅 정렬 데이터끼리 비교 없이 데이터의 개수를 세어 정렬하는 알고리즘 제한 정수나 정수로 표현할 수 있는 자료에 대해서만 한정 데이터의 입력 범위가 제한적인 경우에 효율적 데이터의 수는 적지만, 데이터 값의 범위가 큰 경우(ex. 1~10억) count 배열이 메모리를 과다하게 사용하여 비효율적! 시간복잡도 O(n+k) n: 배열의 길이 k: 정수의 최대값 과정 정렬할 배열에서 가장 큰 정수를 크기로 하는 count 배열을 선언한다.. 데이터 값이 i인 경우, count[i]를 1씩 증가시킨다. count가 모두 끝나면, 앞에서부터 누적합하여 count배열을 수정한다. 기존 배열의 맨 마지막 index부터 정렬을 시작한다. arr[n-1]이 k일 경우, count[k]의 값을 찾아, 그 값을 1..

[알고리즘] 완전 검색, Baby-Gin (자바/Java)

목차 완전 검색 가능한 모든 경우의 수를 확인하는 기법 Brute-force, Generate-and-Test 기법 경우의 수가 작을 때 유용함 정확성은 높지만, 경우의 수가 커진다면 비효율적일 수 있음 Baby-Gin 임의의 숫자 6개를 뽑아 run과 triplet으로만 구성된 카드 = baby-gin run: 3장의 카드가 연속적인 번호를 갖는 경우 triplet: 3장의 카드가 동일한 번호를 갖는 경우 모든 경우의 수 구하기 (순열) 6개의 숫자는 6!개의 순열이 가능 먼저 6개 숫자에서 가능한 세 자리 순열(6P3)을 구하여 run 또는 triplet에 해당하는지 검사 true를 반환한다면, 다시 남은 3가지 수 중에서 순열을 구하여 run 또는 triplet에 해당하는지 검사 for (int i..

[알고리즘] 검색 Search - 순차 검색, 이진 검색 (자바/Java)

목차 검색 자료에서 원하는 항목을 찾는 작업 종류 순차 검색 이진 검색 인덱싱 순차 검색 일렬로 되어 있는 자료를 순서대로 검색 장점: 배열, 연결 리스트 등에서 유용 단점: 자료의 크기가 큰 경우에 비효율적 정렬X 첫 번째 원소부터 마지막 원소까지 키 값이 같은 원소가 있는지 검색 동일한 원소를 찾으면 검색을 중지하고 그 인덱스를 반환 마지막 원소까지 키를 찾지 못하면 실패 시간 복잡도: O(n) 정렬O 첫 번째 원소부터 키 값보다 큰 원소가 나올 때까지 검색 동일한 원소를 찾으면 반환, 키 값보다 큰 원소가 나왔는데 찾지 못하면 검색 실패 시간 복잡도: O(n) 그러나 정렬되지 않았을 때보다 평균 비교 횟수가 절반으로 줄어든다. 이진 검색 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위..

[알고리즘] 정렬 - 선택 정렬(Selection Sort) (자바/Java)

목차 선택 정렬 개념 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식으로 정렬하는 알고리즘 시간 복잡도: O(n^2) 정렬 과정 첫 번째 원소를 두 번째부터 마지막 원소까지 비교하여 가장 작은 값과 자리 교환 2가 가장 작은 원소이고, 그 값의 index는 2이므로 arr[0]과 arr[1] 교환, arr[0]은 가장 작은 값으로 정렬 완료 두 번째, 세 번째 … 끝에서 두 번째 원소까지 같은 과정을 반복함 코드 package sort; import java.util.Arrays; public class SelectionSort { public static void main(String[] args) { int[] arr = { 30, 15, 2, 8, 21, 7 }; ..