Programming/Algorithm
-
[Java] 백준 11728 배열 합치기Programming/Algorithm 2021. 3. 5. 19:48
문제 정렬되어 있는 배열 A와 B가 주어질 때, A와 B를 합친 새로운 배열을 정렬된 형태로 출력하는 문제이다. A와 B의 가장 작은 값을 비교하여 더 작은 값을 새로운 배열에 추가하고 인덱스를 하나 증가시키는 방식을 사용한다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader..
-
[Java] 프로그래머스 징검다리Programming/Algorithm 2021. 3. 5. 01:39
문제 바위들의 위치가 담긴 배열이 있고, 제거할 바위 수 n가 있다. 바위 배열에서 n개를 제거한 이후 각 지점사이 거리 최솟값 중 가장 큰 값 리턴해라. - distance : 도착지점까지의 거리 1~10억 - rocks 요소 개수 : 1~5만 - n 제거할 바위 개수 : 1 ~5만 1) 조합 처음엔 단순하게 n개의 숫자 중 n개를 고르는 시행 만든 뒤 최댓값을 비교하는 방식이 떠올랐다. 하지만 input 값이 커진다면 조합의 경우의 수가 매우 커지기 때문에 효율적인 방식이 아니다. 2) 이진탐색 최소거리를 탐색기준으로 설정한 뒤 추정한 거리로 바위 개수를 세고, '추정한 바위 개수' >= '바위 총개수 - n' 가 남아있어야 최소거리 조건을 만족한다. 조건을 만족한 값들 중 최댓을 구해서 리턴하면 된..
-
[Java] 백준 10815 숫자 카드Programming/Algorithm 2021. 3. 3. 21:06
문제 상근이가 가진 숫자카드 N개가 주어지고, 각각의 카드에는 -10,000,000 이상 10,000,000 이하의 정수가 적혀있다. 그 다음 M개의 정수가 주어질 때 상근이가 가지고 있는 숫자인지를 판별해서 출력하는 문제이다. 2가지 방식으로 풀이했다. 1) 배열로 방문체크 - 카드가 가질 수 있는 숫자의 범위만큼 boolean배열을 만든다. - 상근이가 가지고 있는 숫자라면 해당 인덱스의 값을 true로 초기화한다. - M개의 카드 인덱스를 받아와서 boolean배열의 값이 true인지 확인한다. 2) 이진탐색 - 상근이가 가진 카드 배열을 오름차순 정렬한다. - M개의 카드 값을 받아와서 상근이의 카드배열을 이진탐색한다. 코드 import java.io.BufferedReader; import ja..
-
[Java] 백준 2110 공유기 설치Programming/Algorithm 2021. 3. 3. 20:57
문제 집 N개에 공유기 C개를 설치한다. 공유기가 설치된 거리가 가장 가까운 두 집을 골라 두 집의 거리 차를 구한 뒤에 거리의 차이가 최대가 되는 경우의 거리차를 출력하는 문제이다. 1) 브루트포스 방식 (X) 문제를 곧이곧대로 생각한다면 다음과 같이 풀이할 수 있다. - N개의 집 중 공유기를 설치할 C개를 고른다 => nCc (조합) - 모든 경우의 수에서 가장 인접한 집 2채의 거리차를 구하여 거리차의 최댓값을 리턴한다. 하지만 N과 C 범위의 최댓값(N:20만, C:20만)으로 입력이 주어진다면 시간 제한을 통과하지 못하게 된다. (20만 팩토리얼..) 따라서 해당 방식으로 문제를 풀 수 없다. 2) 이진탐색 방식 문제를 살짝 다르게 생각하면 이진탐색방식으로 논리를 설계할 수 있다. 문제에서 요..
-
[알고리즘 이론] 이진 탐색 알고리즘Programming/Algorithm 2021. 3. 2. 12:03
이진 검색 알고리즘이란? : 오름차순으로 정렬된 리스트에서 특정한 값(X)의 위치를 찾는 알고리즘 가장 쉬운 예시로 책 페이지를 찾는 경우를 생각할 수 있다. 선생님이 168페이지를 피라고 말씀하신다면, 우리는 우선 가지고 있는 책을 반으로 갈라 페이지를 확인할 것이다. 펼친 페이지가 168페이지보다 크다면 더 앞의 페이지를 확인할 것이고, 168페이지보다 적다면 더 뒤의 페이지를 확인할 것이다. 이런 방식으로 임의의 중간값을 설정하여 목표값보다 큰지 작은지 판별하며 범위를 줄여나가는 탐색방법을 이진 탐색이라고 한다. - 장점: 탐색할 때마다 범위가 1/2로 줄어들기 때문에 선형 탐색보다 훨씬 빠르다. (선형탐색 : O(N^2), 이진탐색: O(NlogN)) - 단점: 탐색할 리스트가 오름차순으로 정렬된..