java
자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)
자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)
2021.03.31[정렬 알고리즘 모음] 더보기 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) Merge Sort [합병/병합 정렬] 이 번에 다뤄볼 정렬은 합병(병합) 정렬이다. 아마 대부분 합병, 혹은 병합이라는 단어를 알고있을 것이다. 왜 합병(병합)이라고 할까? 기본적으로 합병정렬은 '문제를 분할하고, 분할한 문..
[백준] 1992번 : 쿼드트리 - JAVA[자바]
[백준] 1992번 : 쿼드트리 - JAVA[자바]
2021.03.23www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 이전 문제인 색종이 만들기 문제를 풀어보셨다면 매우 쉽게 풀 수 있는 문제다. 잘 모르겠는 경우 위 링크를 통해 한 번 풀어보고 오는 것을 추천한다. 알고리즘 [접근 방법] 이진 트리(Binary Tree)는 자식 노드를 2개씩 갖는 트리였다면 쿼드 트리(Quad Tree)는 쉽게 말해서 자식 노드가 4개인 트리 자료구조를 의미한다. 이전의 문제인 색종이 문제와 접근 방식 자체는 같은 구조로 ..
[백준] 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] - 배열을 이용한 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 문제 알고리즘 [접근 방법] 이 번 문제는 위에서 말한 내용을 그대로 큐로 구현만해주면 되는 문제라 그리 어렵지 않게 풀 수 있을 것이다. 문제를 이해해보자면 이렇다. 큐에 프린트 할 문서들이 배치되어있을 때, '중요도'가 높은 것 부터 뽑아야한다는 것이다. 즉, 맨 앞의 문서보다 중요도가 높은 문서가 있을 경우 맨 앞의 문서를 맨 뒤로 보내고, 이를 반복하면서 가장 중요도가 높은 문서가 맨 앞에 배치되도록 해야한..