CodingTest/Algolithm

자바에서 Heap 사용하는 방법

Java에서 Heap 사용하기 Java에서는 Collection으로 Heap이 없다. 하지만 Max-Heap과 Min-Heap을 Primary Queue를 활용하여 구현할 수 있다. 이번 시간에는 Primary Queue를 활용해 Heap을 구현하는 방법을 알아보고자 한다. Heap이라는 자료구조는 값들이 모여있는 자료구조를 트리로 구현하였다고 할 때, 루트에 위치하는 값이 최대 혹은 최소값이 되는 자료구조를 의미한다. 최소 힙 사용하기 최소힙을 사용하는 것은 Primary Queue를 그대로 사용해주면 된다. PriorityQueue minHeap = new PriorityQueue(); 이렇게 사용하여 컬렉션에 데이터를 넣으면 remove되는 peek의 값이 minHeap의 최소값이 된다. Prim..

BFS로 최소비용 문제 해결하기

도입 BFS 알고리즘의 목적은 그래프에서 모든 정점을 한번씩만 확인하기 위한 것입니다. BFS가 너비우선탐색조건이라는 성질 때문에 몇가지 조건만 성립하면 최소비용 문제를 해결할 수 있습니다. BFS란? BFS 그래프 설명 참고하기 [Algorithm] 그래프란? 그래프 탐색알고리즘(DFS,BFS) 도입 그래프는 정점과 간선으로 구성되는 중요한 자료구조입니다. 이번 시간에는 그래프에 대한 용어와 그래프를 표현하는 방법 그리고 그래프를 탐색하는 알고리즘을 알아보겠습니다. 그래프 cnu-jinseop.tistory.com BFS는 그래프의 탐색에서 사용되는 알고리즘입니다. DFS와 동일하게 모든 정점을 한번씩만 확인할 때 사용합니다. BFS는 너비를 우선으로 탐색하는 기능을 수행하기 때문에 최소비용 문제를 해..

그래프란? 그래프 탐색알고리즘(DFS,BFS)

도입 그래프는 정점과 간선으로 구성되는 중요한 자료구조입니다. 이번 시간에는 그래프에 대한 용어와 그래프를 표현하는 방법 그리고 그래프를 탐색하는 알고리즘을 알아보겠습니다. 그래프란? 그래프는 정점과 간선으로 구성되는 자료구조입니다. 정점은 하나의 객체를 의미하며 Vertex혹은 노드라고 표현합니다. 간선은 정점과 정점을 이어주는 선을 의미합니다. 따라서 그래프를 구현하여 서로 연결되어있는 객체들의 관계를 표현해줄 수 있습니다. 위는 그래프의 예시입니다. A,B,C,D,E를 정점이라하며 각각을 연결하고 있는 선을 간선이라고 합니다. 그래프 용어 그래프의 용어를 정리하도록 하겠습니다. 정점 Vertex라고 하며 하나의 점을 의미합니다. 하나의 객체라고 생각하면 됩니다. 간선 edge라고 부르며 정점과 정점..

Queue와 Deque(큐와 덱)

도입 기본 자료구조인 Queue와 Dequeue에 대하여 알아보자. Queue Queue는 선입 선출의 자료구조이다. 데이터를 넣는 부분과 빼는 부분이 다르다. push(x) : 데이터를 넣는 연산 pop(x) : 데이터를 빼는 연산 C++은 STL의 queue를 Python은 collections의 deque를 사용하면 된다. 자바를 사용하는 경우 java.util.Queue의 Queue를 사용하면 된다. 삽입과 삭제 Queue에서 삽입을 한 경우이다. Queue의 뒷 부분에 20이 삽입되는 것을 알 수 있다. Queue에서 pop을 수행한 경우는 앞 부분에 43가 나오는 것을 알 수 있다. 위 삽입과 삭제 과정에서 주목해야할 점은 데이터가 들어가는 방향과 나오는 방향이 다르다는 점이다.(Queue의 ..

다이나믹 프로그래밍

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누고 효율적으로 푸는 방법이다. 효율적으로 풀기 위해서는 중복되는 작은문제에 대한 처리를 Memorization을 통해 간단히 해결할 수 있다. 다이나믹 프로그래밍 다이나믹 프로그래밍은 큰 문제를 작은문제로 바꾸어 푸는 것이다. 다이나믹 프로그래밍으로 문제를 해결하기 위해서는 Overlapping Subproblem과 Optimal Substructure라는 두가지 조건을 만족해야한다. 그리고 위의 조건에 의해 불필요하게 중복처리해야하는 문제들이 있다. 이를 해결하기 위해 Memorization을 사용한다. 다이나믹 프로그래밍의 대표적인 예로 피보나치 수열이 있으며 다이나믹 프로그래밍의 두가지 조건과 효율적으로 해결하기 위한 Memoriation을 알아보도록..

비트마스크 알고리즘

도입 비트마스크 알고리즘은 비트연산자를 활용해 간단하게 집합을 표현하는 알고리즘이다. 비트마스크를 사용하면 하나의 정수로 여러가지 집합을 표현할 수 있다. 하지만 여러가지 제약사항이 있으므로 사용에 있어 주의해야하며 주로 다이나믹 프로그래밍에서 주로 사용한다. 비트연산 | 연산 : or연산으로 둘 중 하나가 1이면 1이다. &연산 : and연산으로 둘 다 1이어야 1이다. ^연산 : xor연산으로 두개의 연산자가 서로 다른 값이어야 1이다. ~연산 : not연산으로 1을 0으로 0을 1로 변경하여준다. -shift연산- >> 연산은 비트를 오른쪽으로 미는 연산으로 2의 n승을 나누는 것과 동일한 결과가 나온다.

브루트포스(3) 순열

순열 순열(Purmutation)은 숫자를 사전순으로 나열한 것을 의미한다. 더보기 Ex) 1,2,3 순열 1 2 3 -> 시작 순열(오름차순) 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 -> 끝 순열(내림차순) 순열은 시작지점, 끝지점, 다음 순열,이전 순열로 표현할 수 있다. 시작순열과 끝 순열을 각각 오름차순과 내림차순으로 구성된다. 다음 순열 순열의 다음을 구하는 방법이다. 끝순열을 구해서 그 다음 구해주어 해결한다. private boolean nextPermutation(int[] numbers){ int prevIndex; int n = numbers.length; int nextIndex = n-1; int changeIndex = -1; for(int i = n-2; i >= ..

브루트포스(2) 재귀

재귀를 쓰면 재귀를 쓰면 모든 경우의 수를 확인하도록 만들 수 있다. 재귀를 써서 모든 경우를 확인하는 경우는 두가지이다. 1. 순서가 있는 경우(P) n개의 수를 나열하는 방법의 수이다.(중복가능) -> O(n!) /** * index -> 현재 수를 놓는 위치 * arr -> 확인하려고 만드는 배열 */ public void recursive1(int index, int[] arr){ if(index == arr.length){ //종료 조건 } for(int i = 1; i O(2^n) /** * index -> 현재 수를 놓는 위치 * arr -> 확인하려고 만드는 배열 */ public void recursive2(int cnt, int[] arr, int value, int n){ if(ind..

브루트포스(1) - 무작정 해보기

브루트 포스 알고리즘 모든 경우의 수를 해보는 알고리즘이다. 무작정 반복문을 돌려 구할 수도 있다. 브루트포스 알고리즘 예시 문제 : n이 주어졌을때, 1부터 n 중에 2의 배수의 수는? (1

최대, 최소공배수 그리고 소수

최대공약수(GCD) 두 수 a,b의 공통된 약수중 가장 큰 수 - 구하는 방법 1. 2부터 시작해서 a,b로 공통되게 나누어 떨어지는 것중 최대값을 구한다. O(n) -> n은 a,b중 최소값 2. 유클리드 호제법을 사용하기 // 나는 주로 재귀를 사용하는 편 public int gcd(int a, int b){ if(a%b == 0) return b; return gcd(a,a%b); } //반복문을 사용하여 구할수도 있음 public int gcd(int a, int b){ int temp; while(true){ if(a%b == 0) return b; temp = a % b; a = b; b = temp; } } 위 코드는 유클리드 호재법을 사용해서 구현해본 코드이다. 최소공배수(LCM) - 최소..

약수

약수를 구하는 방법 1. 1부터 n까지 %연산을 활용하여 구하기 2. 1부터 루트n까지 %연산을 활용하여 구하기 루트n까지만 비교해도 되는 이유는 약수는 짝을 지어 있기 때문이다. 약수의 개수가 홀수일 경우 root를 씌어준 값이 약수가 된다.(루트n까지 확인해야한다.) 시간복잡도 1번 방법 : O(n) 2번 방법 : O(√n) // 1번 방법 O(n) int n = 121; for(int i = 1; i

수학 - Mod연산

Mod 연산 나머지 연산의 특징 (A + B) % C == ((A % C) + (B % C)) % C (A * B) % C == ((A % C) * (B % C)) % C (A - B) % C == ((A % C) - (B % C) + C) % C 나누기 연산을 제외하고는 분배법칙 처럼 Mod를 처리하고 사용 가능하다. (주의사항) '-' 연산일 경우 범위는 -C