반응형 Programming/Algorithm29 백준 1780 종이의 개수 알고리즘 자바 JAVA 백준 1780 종이의 개수 알고리즘 문제 백준 1780 종이의 개수 문제는 분할정복 알고리즘 방법으로 풀수 있는 문제다. 주어진 숫자들을 비교해서 -1,0,1 세 가지 경우의 수를 판별해서 종이의 개수를 카운팅 하는 문제다. 기본적인 논리는 백준 1992번 쿼드트리 문제와 동일하다. 다만 다른점은 색종이의 갯수가 N/3 단위로 쪼개진다는 것이다. 입력값 맨 처음 주어지는 숫자 N은 3의 지수승으로 만들어진 숫자다. N(1 ≤ N ≤ 37, N은 3k) 동일한 알고리즘으로 구현하되, 색종이를 쪼개는 분기를 9번씩 돌아가면서 진행해야 한다는 점이 유일한 차이점이다. 백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바 백준 1992번 쿼드트리 알고리즘은 분할정복 알고리즘 시리즈다. 전체의 문제를 작은 단.. 2022. 3. 2. 백준 1992번 쿼드트리 분할정복 알고리즘 JAVA 자바 백준 1992번 쿼드트리 알고리즘은 분할정복 알고리즘 시리즈다. 전체의 문제를 작은 단위로 쪼개는 작업이 첫번째로 고려되어야 한다. 백준 1992번에서 제시된 쿼드트리는 압축 알고리즘으로 사용되는 방법 중 하나다. 동일한 점들이 모여있는 곳을 압축해서 간단하게 표현하는 방법이다. 쿼드 트리는 4개의 자식노드를 가진 트리구조다. 주어진 문제에서 흑과 백으로 이루어진 N*N 정사각형이 있다고 하면, 동일한 값으로만 이뤄진 N*N 정사각형으로 분해를 하는 것이다. 만약 값이 다른 정사각형이 발견되면 4등분을 하게 되고 분할된 정사각형에서 동일한 작업을 이어가게 되는 것이다. 위에서 흑과 백이 동시에 존재하는 정사각형을 4등분하게 되면 왼쪽 위부터 1사분면, 오른쪽 위를 2사분면, 왼쪽 아래를 3사분면, 오른쪽.. 2022. 3. 1. 백준 알고리즘 2630번 분할정복 색종이 만들기 자바 JAVA 백준 알고리즘 2630번 문제는 분할 정복 방법으로 풀어보는 알고리즘이다. 분할정복(Divide and Conquer) 알고리즘은 큰 문제 자체로 해결할 수 없는 문제를 효율적으로 문제를 풀 수 있는 작은 단위로 나누는 하향식(Top-Down) 방식이다. 작은 단위에서 얻은 결과값을 합쳐서 전체 문제의 값을 구해내게 된다. 분할 정복법 알고리즘을 구현하는 방법은 일반적으로 재귀 호출 방식을 사용한다. 하지만 재귀방식의 경우 오버헤드 문제(결과값을 얻기 위한 시간, 메모리 등 자원사용이 지나치게 많이 소요되는 문제)가 발생되기 때문에, 스택 혹은 큐 자료구조로 풀어내는 경우가 있다. 입력값으로 주어지는 N은 N*N으로 구성된 정사각형을 만들게 된다. N=2k, k는 1 이상 7 이하의 자연수로 2,4,8,.. 2022. 2. 28. 백준 알고리즘 2798번 블랙잭 문제 JAVA 백준 알고리즘 2798번은 모든 경우의 수를 생각하는 브루트 포스 문제다. 자바로 알고리즘을 만들어보자. 입력값은 n과 m이 주어진다. n은 카드의 갯수이며, m은 카드의 조합으로 가장 가까운 수를 맞춰야 하는 수다. 문제의 핵심은 모든 경우의 수를 생각한다는 것이다. 문제에서는 카드를 3장 뽑을 수 있게 되어 있다. 처음 선택가능한 카드는 n장이다. 두번째 선택 가능한 카드는 n-1장이다. 마지막으로 선택 가능한 카드는 n-2장이다. 먼저 입력값을 받아와서, 3번의 for문을 순회하면서 모든 경우의 수를 조회해보는 것이다. 3장의 카드값을 뽑아서, max값을 구하는 로직을 계속 순회한다. for문이 종료되면 max값에는 m값과 가장 근사한 값이 할당되어 있다. 출력하면 로직은 끝이난다. JAVA COD.. 2022. 2. 25. 알고리즘 설계기법 알고리즘이란? 알고리즘이란 문제를 해결하기 위해 수행해야 할 기능의 집합을 의미한다. 알고리즘과 데이터 구조를 결합해야 프로그램이 완성되는 것이다. 순서도(Flow Chart), 의사코드(Pseudo Code)를 통해 알고리즘을 설계하고 프로그래밍이 진행된다. 알고리즘은 입력값이 존재하지 않을 수 있다는게 특징이다. 하지만 출력은 반드시 1개 이상 존재해야 한다. 모든 기능은 명확한 의미와 완벽한 구성을 갖추고 있어야 한다. 모든 기능은 지정한 횟수만큼 반복된 뒤에 종료되어야 한다. 모든 기능은 실제로 연산이 가능한 로직이어야 한다. 알고리즘이 제대로 구성되었는지 확인하는 방법은 특정 입력에 대해서 기대 출력값이 동일한지 판단한다. 알고리즘의 표현이 간단하고 이해가 용이한지 판단한다. 입력 데이터에 비례.. 2022. 2. 25. 백준 알고리즘 7615번 해싱 탐색 자바 JAVA 메모리 초과 문제 백준 알고리즘 7615번은 해싱탐색 알고리즘으로 풀어보는 문제다. t,a,b,x,n,c,d,m 총 8개의 입력값이 주어지는데, t번 순회를 돌면서 a부터 m까지 입력된 변수들을 토대로 해싱함수를 정의하게 된다. 해시탐색(Hash Search) 해싱함수를 사용해서 데이터를 검색하는 방법이다. 기존의 탐색법과는 다르게 데이터의 내용과 인덱스를 미리 연결해서 짧은 시간안에 탐색이 가능한 알고리즘이다. 적절한 해싱 함수를 이용해서 데이터의 저장 위치를 결정한다. 결정된 저장 위치가 중복 혹은 충돌 되는 경우 다른 조치를 필요로 한다. 해시탐색 알고리즘의 시간복잡도는 n(1)이다. 입력값에 따라 연산의 횟수가 증가하지 않고 일정하다. 해싱함수는 6가지 종류로 나뉜다. 제산법(Division) : 키를 특정 값으로.. 2022. 2. 24. 이전 1 2 3 4 5 다음 반응형
