[백준] 2630번 : 색종이 만들기 - JAVA [자바]
[백준] 2630번 : 색종이 만들기 - JAVA [자바]
2021.03.17www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 분할 정복의 첫 문제다. 원리만 이해한다면 그리 어렵진 않으니 차근차근 살펴보도록 하자. 알고리즘 [접근 방법] 여러분이 분할 정복 문제를 풀기 전에 기본적으로 알고있어야 할 지식이 있다. 1. 재귀에 대한 이해 2. 탐색(search)에 대한 이해 위 두 개의 기본 이해를 바탕으로 분할 정복을 풀이할 수 있다. 기본적으로, 분할 정복의 과정은 3단계로 나뉜다. 1. 현재 상태의..
자바 [JAVA] - 힙 정렬 (Heap Sort)
자바 [JAVA] - 힙 정렬 (Heap Sort)
2021.03.14[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) - [현재 페이지] 7. 합병(병합) 정렬 (Merge Sort) 8. 퀵 정렬 (Quick Sort) 9. 이진 삽입 정렬 (Binary Insertion Sort) 10. 팀 정렬 (Tim Sort) Heap Sort [힙 정렬] 힙 정렬은 기본적으로 힙 자료구조를 기반으로 하기 때문에 만약 힙을 모르신다면 이 글을 읽기 전에 반드시 '힙 자료구조'를 보고 오시길 바란다. 바로 위에서 말했듯 힙 정렬은 힙 자료구조를 기반으..
[백준] 5430번 : AC - JAVA [자바]
[백준] 5430번 : AC - JAVA [자바]
2021.03.07www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 덱의 원리만 이해한다면 매우 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 이 문제는 그렇게 어려운 문제는 아니다. 이 번 문제는 덱(Deque) 자료구조를 이용하여 푸는 문제이므로 가능하다면 아래 덱(Deque) 자료구조에 대해 어떻게 구현되고 원리는 무엇인지 이해하고 오시면 좋을 것 같다. 배열 덱 자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기 •자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collecti..
자바 [JAVA] - Priority Queue (우선순위 큐) 구현하기
자바 [JAVA] - Priority Queue (우선순위 큐) 구현하기
2021.03.04자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중 연결리스트 (Doubly LinkedList) 5. 스택 인터페이스 (Stack Interface) 6. 스택 (Stack) 7. 큐 인터페이스 (Queue Interface) 8. 배열 큐 (Array Queue) 9. 연결리스트 큐 (LinkedList Queue) 10. 배열 덱 (Array Deque) 11. 연결리스트 덱 (LinkedList Deque) 12. 배열 힙 (Heap) 13. 우선순위 큐 (Priority..
[백준] 1021번 : 회전하는 큐 - JAVA [자바]
[백준] 1021번 : 회전하는 큐 - JAVA [자바]
2021.02.27www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 알고리즘 [접근 방법] 이 문제는 덱(Deque)에 대한 이해만 있다면 크게 어렵지 않다. 혹여 덱(Deque)에 대해 자세하게 알고싶다면 다음 글을 참고하면 도움이 될 것이다. st-lab.tistory.com/185 자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기 •자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) ..
[백준] 10866번 : 덱 - JAVA [자바]
[백준] 10866번 : 덱 - JAVA [자바]
2021.02.19www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 자료구조 덱을 이해하고 있는지를 확인하는 문제다. 기존의 덱 자료구조 원리를 이해하고 있다면 매우 쉽게 풀 수 있다. 알고리즘 [접근 방법] 이러한 문제는 자료구조 구현 문제로 이미 덱(Deque)에 대해 알고 있다면 크게 어렵지 않은 문제다. 일단, 덱(Deque)은 무엇인지 한 번 알아보자. 앞서 우리는 Queue(큐)를 다뤘었다. 큐는 '단방향'이면서 '선입선출(先入先出)' 즉, 먼저..
자바 [JAVA] - 셸 정렬 (Shell Sort)
자바 [JAVA] - 셸 정렬 (Shell Sort)
2021.02.18[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) 5. 셸 정렬 (Shell Sort) - [현재 페이지] 6. 힙 정렬 (Heap Sort) 7. 합병(병합) 정렬 (Merge Sort) 8. 퀵 정렬 (Quick Sort) 9. 이진 삽입 정렬 (Binary Insertion Sort) 10. 팀 정렬 (Tim Sort) Shell Sort [셸 정렬] 셸 정렬은 기본적으로 삽입 정렬을 기반으로 하기 때문에 만약 삽입 정렬을 모르신다면 이 글을 읽기 전에 '삽입 정렬'을 보고 오시는 것을 추천드린다. 바로 위에서 말했듯 셸 정렬은 삽입 정렬을 ..
자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기
자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기
2021.02.10자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중 연결리스트 (Doubly LinkedList) 5. 스택 인터페이스 (Stack Interface) 6. 스택 (Stack) 7. 큐 인터페이스 (Queue Interface) 8. 배열 큐 (Array Queue) 9. 연결리스트 큐 (LinkedList Queue) 10. 배열 덱 (Array Deque) 11. 연결리스트 덱 (LinkedList Deque) 12. 배열 힙 (Heap) - [현재 페이지] 13. 우선순위 ..
[백준] 1966번 : 프린터 큐 - JAVA [자바]
[백준] 1966번 : 프린터 큐 - JAVA [자바]
2021.02.03www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 알고리즘 [접근 방법] 이 번 문제는 위에서 말한 내용을 그대로 큐로 구현만해주면 되는 문제라 그리 어렵지 않게 풀 수 있을 것이다. 문제를 이해해보자면 이렇다. 큐에 프린트 할 문서들이 배치되어있을 때, '중요도'가 높은 것 부터 뽑아야한다는 것이다. 즉, 맨 앞의 문서보다 중요도가 높은 문서가 있을 경우 맨 앞의 문서를 맨 뒤로 보내고, 이를 반복하면서 가장 중요도가 높은 문서가 맨 앞에 배치되도록 해야한..
[백준] 10757번 : 큰 수 A+B - JAVA [자바]
[백준] 10757번 : 큰 수 A+B - JAVA [자바]
2021.02.01www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 Java로 풀 경우 매우 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 참고로 일반적으로 큰 수를 쓸 때 쓰는 long형은 264-1으로 약 1844경 정도 된다. 하지만 이 번 문제의 경우 입력 범위가 최대 1010000 이므로 long형을 아득히 넘는다. 그러면 이를 어떻게 풀어야 할까? 크게 두 가지 방식이 있다. 먼저 덧셈 과정을 직접 구현하는 방법이 있다. 그리고 Java에서 제공하는 BIgInteger 클래스를 이용하는 방법이 있다. 이 번에는 이 두 방식 모두 보여주려고 한다. 먼저 덧셈을 구현하는..