알고리즘 풀이 - 동적계획법(백준-1003 피보나치 함수)

이전 포스팅에 이어서 백준 알고리즘의 동적계획법 카테고리에 있는 알고리즘 문제를 풀고 있습니다. 이번 문제도 동일하게 동적계획법을 통해서 해결 할 수 있습니다. 문제 - 피보나치 함수 (백준 알고리즘 - 1003) 문제 링크 : https://www.acmicpc.net/problem/1003 풀이 피보나치 함수 처리 메소드에서 동적 계획법을 추가 하여 검색 효율 증가 시켜야지 시간 초과를 해결 할...

알고리즘 풀이 - 동적계획법(백준-2748 피보나치 수 2)

이전 포스팅에서 알고리즘 문제중 재귀 문제 4가지를 확인 했습니다. 이번에는 동적 계획법을 통해서 어떻게 더 효율적으로 결과를 출력 할 수 있는지에 대해서 확인 해보겠습니다. 동적 계획법이란? DP(Dynamic Programming) 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법입니다. 이 알고리즘은 이미 계산된 값을 메모리에...

알고리즘 풀이 - 하노이 탑 이동(백준 알고리즘-재귀)

2020년 첫 알고리즘 풀이. 백준 알고리즘 문제의 재귀 카테고리에 있는 4가지 유형의 문제입니다. 재귀 알고리즘은 매우 기초적이지만 자주 헤깔릴 수 있는 알고리즘으로 아래 4가지 유형의 문제 풀이를 보고 되뇌여 보겠습니다. 문제4 - 하노이 탑 이동 순서 문제 링크 : https://www.acmicpc.net/problem/11729 풀이 하노이의 탑은 퍼즐을 일종으로 세 개의 기둥에 N개의 원판이...

알고리즘 풀이 - 백준 알고리즘(별찍기)

2020년 첫 알고리즘 풀이. 백준 알고리즘 문제의 재귀 카테고리에 있는 4가지 유형의 문제입니다. 재귀 알고리즘은 매우 기초적이지만 자주 헤깔릴 수 있는 알고리즘으로 아래 4가지 유형의 문제 풀이를 보고 되뇌여 보겠습니다. 문제3 - 별찍기 문제 링크 : https://www.acmicpc.net/problem/2447 풀이 별찍기 문제는 주어진 별 그림을 보고 패턴을 분석 하여 결과를 출력 하는...

알고리즘 풀이 - 백준 알고리즘(팩토리얼, 피보나치의 수)

2020년 첫 알고리즘 풀이. 백준 알고리즘 문제의 재귀 카테고리에 있는 4가지 유형의 문제입니다. 재귀 알고리즘은 매우 기초적이지만 자주 헤깔릴 수 있는 알고리즘으로 아래 4가지 유형의 문제 풀이를 보고 되뇌여 보겠습니다. 문제1 - 팩토리얼 문제 링크 : https://www.acmicpc.net/problem/10872 풀이 팩토리얼 알고리즘은 주어진 정수의 모든 원소를 곱한 값을 출력하는 문제입니다. 주어진 정수...

알고리즘 풀이(JAVA) - 백준 알고리즘_5430(AC)

문제 문제 링크 : https://www.acmicpc.net/problem/5430 풀이 이 문제는 앞뒤로 입출력이 가능한 자료 구조인 덱(deque) 을 활용 하여 풀이하면 쉽게 풀 수 있다. R : 방향을 변경할때 배열을 돌리려고 하면 시간초과가 뜨기 때문에 변수(dir)를 선언 하여 방향을 저장 한다. D : 방향(dir) 에 따라서 firstPoll(), LastPoll() 을 활용하여 앞 뒤로 큐를...

알고리즘 풀이(JAVA) - 백준 알고리즘_1966(프린터 큐)

문제 문제 링크 : https://www.acmicpc.net/problem/1966 풀이 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만) 이 무엇을 의미 하는지 이해하는데 한참이 걸렸다. M 은 예제로 주어진 우선순위 문서의 위치 값을 나타낸다. 예) 1 1 9 1 1 1 우선순의에서 M : 0 을 주었때에 가장 첫번째 있는 1을 말하는 것이다. 입력 :...

알고리즘 풀이(JAVA) - 백준 알고리즘_11866(조세퍼스 문제O)

문제 문제 링크 : https://www.acmicpc.net/problem/11866 풀이 두개의 큐를 생성하여 풀이 진행 K 번째 의 수를 queue에서 빼서 rQueue 로 이동 시키면서 반복 처리. 소스 조세퍼스(11866) public class Baekjoon_11866 { public static Queue<Integer> queue = new LinkedList<>(); public static Queue<Integer> rQueue = new LinkedList<>(); public static void main(String[] args) throws IOException...

알고리즘 풀이(JAVA) - 백준 알고리즘_2164(카드2)

문제 1 문제 링크 : https://www.acmicpc.net/problem/2164 풀이 큐를 이용해서 쉽게 풀이가 가능 소스 카드2(2164) public class Baekjoon_2164 { public static Queue<Integer> queue = new LinkedList<>(); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); for(int i = 1; i <= N; i++) { queue.add(i);...

알고리즘 풀이(JAVA) - 백준 알고리즘_1780(종이의 개수)

문제 문제 링크 : https://www.acmicpc.net/problem/1780 풀이 앞선 쿼드 트리 문제는 배열을 반으로 계속 잘라 가며 숫자를 비교 했다면 이 문제는 배열을 1/3 로 잘라가면서 비교를 하는 방식이다. 쿼드 트리의 이해와 배열의 이해가 있으면 쉽게 풀이가 가능 하다. 종이의 갯수을 카운트 하기 위한 3개의 int 변수 선언(int minus, zero, one) 종이를...

알고리즘 풀이(JAVA) - 백준 알고리즘_1992(쿼드 트리)

문제 문제 링크 : https://www.acmicpc.net/problem/1992 풀이 이 문제는 앞선 색종이 자르기https://parkhyeokjin.github.io/algorithm/2019/08/22/baekjoon-2630.html 를 풀어 보았다면 쿼드 트리를 이용해서 쉽게 해결 할 수 있다. 쿼드 트리는 4개의 자식 노드를 가지는 트리 구조이다. 영상 입력 처리 readData(reader, N) 재귀 함수(cut()) 를 이용 하여 4부분으로 반복적으로 자른다. 잘려진 영역의 문자열이 동일할 경우 압축 한다....

알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-1300(K번째 수)

문제 문제 링크 : 이분탐색-K번째 수 https://www.acmicpc.net/problem/1300 풀이 이 문제는 어떻게 이분 탐색으로 접근을 해야 할지 아무리 머리를 굴려도 모르겠어서 문제 풀이를 좀 살펴 보고 이해를 해야 했다. 배열을 정렬 해서 K 번째 배열 값을 출력 하면 될 문제인데 … 이 문제가 어떻게 이분 탐색으로 되지??? 풀이 시작 첫번째. 배열의...

알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-2110(공유기 설치)

문제 문제 링크 : 이분탐색-공유기 설치 https://www.acmicpc.net/problem/2110 풀이 이 문제는 어떻게 이분 탐색으로 접근을 해야 할지 한참을 생각 해야 했다. 첫번째로 주어진 갯수 만큼 공유기를 설치해야 하고. 두번째로 공유기가 설치 된 집간의 거리를 구해서 거리를 측정해야한다… 문제를 해결 할 수 있었던 방법은 이분탐색의 mid 값을 집간의 거리 로 생각 하고...

알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-2805(나무 자르기)

문제 문제 링크 : 이분탐색-나무 자르기 https://www.acmicpc.net/problem/2805 풀이 이 문제는 랜선자르기(https://parkhyeokjin.github.io/algorithm/2019/10/09/baekjoon-1654.html) 에서 고민을 많이 한 덕에 조금 쉽게 접근을 하였으나 문제를 정확히 분석 하지 못한 탓에 수자례 실패를 맛봐야 했다. 실수1. 상근이는 항상 나무를 가져갈 수 있다. 필요한 나무가 M 이지만 더 많이 가져 갈 수 있고 딱 맞게 가져갈...

알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘-1654(랜선 자르기)

문제 문제 링크 : 이분탐색-랜선 자르기 https://www.acmicpc.net/problem/1654 풀이 이 문제는 정말정말 매우 어려웠다. 두가지 문제점때문에 몇번을 틀리고 시간을 소모 했다. 첫번째 int 선언 -> 랜선의 최대 길이가 N <= 2³¹-1 이므로 전체 길이를 더했을 때 int 최대 범위를 벗어 날 수 있음. 두번째 문제에서 주어진 n 개만큼만 구하면 되는줄 알고...

알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘(숫자 카드2)

문제 문제 링크 : 이분탐색-숫자 카드2 https://www.acmicpc.net/problem/10816 풀이 첫번째. 입력 데이터를 배열 처리 두번째. 이분 탐색을 위해 카드뭉치 정렬(Arrays.sort(cards)) 세번째. 정렬된 카드 뭉치(cards) 에서 찾고자 하는 숫자(num)가 시작 되는 배열의 index를 찾는다(findLeft()) 네번째. 정렬된 카드 뭉치(cards) 에서 찾고자 하는 숫자(num) 보다 처음 큰수가 나오는 index를 찾는다(findRight()) 다섯째. findRight - findLeft...

알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘(수 찾기)

문제 문제 링크 : 이분탐색-수 찾기 https://www.acmicpc.net/problem/1920 풀이 이 문제를 풀기 전에 이분탐색에 대해서 알아보자. 이분 탐색 설명 : https://parkhyeokjin.github.io/algorithm/2019/10/01/binarySearchAlgorithm.html 이 문제는 이분 탐색을 알면 쉽게 풀 수 있다. 숫자들의 집합 (aLen) 찾아야 되는 숫자의 집합 (bLen) 이분탐색은 정렬되어있는 배열 에서 찾는 탐색 방법으로 aLen을 오름 차순으로 정렬한다. bLen 의...

이진 검색 알고리즘(Binary Search Algorithm)

1. 이진 검색 알고리즘(Binary Search Algorithm) 이진 검색 알고리즘은 이미 정렬 되어 있는 배열에서 특정한 값의 위치를 찾는 알고리즘 이다. 탐색 방법 예) int[] arr = new int[] {9, 7, 2, 1, 5, 8, 3, 6, 4} 탐색 조건 : 3번 숫자 찾기 1) 배열을 오름 차순으로 정렬한다. 2) 정렬된...

알고리즘 풀이(JAVA) - 백준 알고리즘(가운데를 말해요)

문제 문제 링크 : (가운데를 말해요) https://www.acmicpc.net/problem/1655 수빈이는 동생에게 “가운데를 말해요” 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 수빈이가 동생에게 1, 5, 2,...

알고리즘 풀이(JAVA) - 백준 알고리즘(절댓값 힙)

문제 문제 링크 : (절대값 힙) https://www.acmicpc.net/problem/11286 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게...

알고리즘 풀이(JAVA) - 백준 알고리즘(최대힙, 최소힙)

문제 문제 링크 최대힙 : https://www.acmicpc.net/problem/11279 최소힙 : https://www.acmicpc.net/problem/1927 풀이 풀이) 이번 문제는 여러 가지로 도전을 하였으나 속도 제한에 걸려서 조금 고민을 하였다. 정렬을 하는 부분에 있어서 힙정렬 퀵정렬을 메소드 등을 이용하여 정렬을 해서 처리하려고 했으나 결국에는 PriorityQueue 자료 구조를 이용해서 처리를 해서 성공을 하였다. 소스 최대힙 import java.io.BufferedReader; import...

알고리즘 풀이(JAVA) - 백준 알고리즘_1436(브루트포스-영화감독 숌)

브루트포스(brute-force) 브루트포스란? brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식. 특징 조합...

알고리즘 풀이(JAVA) - 백준 알고리즘_1018(브루트포스-체스판 다시 칠하기)

브루트포스(brute-force) 브루트포스란? brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식. 특징 조합...

알고리즘 풀이(JAVA) - 백준 알고리즘_7568(브루트포스-덩치)

브루트포스(brute-force) 브루트포스란? brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식. 특징 조합...

알고리즘 풀이(JAVA) - 백준 알고리즘_2231(브루트포스-분해합)

브루트포스(brute-force) 브루트포스란? brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식. 특징 조합...

알고리즘 풀이(JAVA) - 백준 알고리즘_2798(브루트포스-블랙잭)

브루트포스(brute-force) 브루트포스란? brute는 “짐승같은, 난폭한”이라는 뜻이고, brute-force는 “난폭한 힘, 폭력”이라는 뜻이다. 암호학 용어로는 brute-force attack 또는 exhaustive key search, 우리말로는 노가다 또는 무차별 대입 공격이라 부른다. 주로 암호학에서도 쓰이는 방법이긴 하지만, 굳이 암호학만의 문제는 아니고 다른 알고리즘 분야에서도 사용되고 있다. 간단하게 말하자면 노가다와 다굴을 논리적이고 과학적으로 하는 방식. 특징 조합...

알고리즘 풀이(JAVA) - 백준 알고리즘_2630(색종이 만들기)

백준 알고리즘_2630(색종이 만들기) 문제 링크 : https://www.acmicpc.net/problem/2630 주어진 네모 배열을 재귀함수를 활용 하여 반복적으로 잘라서 동일한 색깔의 종이가 나올때까지 반복 수행 하는 문제 이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Baekjoon_2630 { private static int whiteCnt = 0; private static int blueCnt = 0; public static void main(String[]...

정렬 알고리즘 기초5 - 계수 정렬(Counting Sort)

1. 계수 정렬 알고리즘(Counting Sort) 현재까지 개발이 된 정렬 알고리즘은 O(n log n) 의 속도를 가지고 있는 퀵정렬, 힙정렬, 병합 정렬이 가장 빠르다. 하지만 어떠한 특정한 조건 이 된다면 O(n) 의 속도를 보이는 정렬이 바로 계수정렬이다. 어떠한 조건에 의해 정렬이 되는지 알아보자. 정렬 방법 이전의 정렬 방법들은 전부 위치를 교환...

정렬 알고리즘 기초4 - 병합 정렬(Merge Sort)

1. 병합 정렬 알고리즘(Merge Sort) 병합정렬은 분할 정복 알고리즘이다. 병합 정렬 알고리즘은 정확히 반씩 나누어 계산을 하기 때문에 최악의 경우에도 O(n log n)의 동일한 속도를 보장 한다. 정렬 순서 예1) 3,5,1,2,4,8,6,9,7,10 배열을 오름차순으로 정렬 하려고 할 경우 1) 병합 정렬은 항상 반으로 쪼개어 정렬을 수행 한다. (2의 배수) 0 1...

정렬 알고리즘 기초3 - 힙 정렬(Heap Sort)

1. 힙정렬 알고리즘(Quick Sort) 우선 힙정렬을 이해하기 위해서는 이진트리 구조를 이해해야 한다. 이진트리 이진트리란 루트(root) 노드 부터 시작해서 최대 두개의 자식 노드를 가지는 트리 구조를 말한다. 힙(Heap) 이란 최소값이나 최대값을 빠르게 찾아내기위한 완전 이진트리를 기반으로 하는 트리입니다. 힙에는 최대 합과 최소합이 존재하는대 최대 합은 부모노드가 자식노드보다 큰합이라고 할 수 있습니다....

정렬 알고리즘 기초2 - 퀵 정렬(Quick Sort)

1. 퀵정렬 알고리즘(Quick Sort) 퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 일반적인 상황에서 최고의 정렬 성능을 보인다. 프로그래밍에 가장 많이 구현된 정렬 알고리즘 중 하나이다. 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 정렬 순서는 아래와 같다. 리스트...

정렬 알고리즘 기초(선택정렬, 버블정렬, 칵테일정렬, 삽입정렬)

1. 선택정렬 알고리즘(Selection Sort) 선택 정렬 알고리즘은 제자리 정렬 알고리즘의 하나로, 선택한 수를 가장 작은 수와 자리를 교체 하는 방법으로 정렬을 한다. 선택 정렬 알고리즘은 다음의 순서로 이루어진다. 예) 3,5,1,2,4,8,6,9,7 배열을 오름차순으로 정렬 하려고 할 경우 1) 3 5 1 2 4 8 6 9 7     3─1─────┤ 3을 선택 하여...