java
[백준] 11444번 : 피보나치 수 6 - JAVA [자바]
[백준] 11444번 : 피보나치 수 6 - JAVA [자바]
2021.05.27https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 알고리즘 [접근 방법] 이 번 문제는 단계별로 차근차근 풀었었다면 여러 번에 걸쳐 피보나치 수를 구하는 문제들을 풀어왔기 때문에 그렇게 어렵지는 않았을 것이다. 그동안 풀어왔던 피보나치 수와 관련된 문제들은 다음과 같다. 피보나치 수 5 (재귀) 피보나치 수 2(동적계획법) 다만 문제는 똑같더라도 주어지는 입력의 범위는 엄청 다르다. 이 번 문제의 경우 n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이기 때문에 동적계획법으로 풀이하더라도 그동..
[백준] 10830번 : 행렬 제곱 - JAVA [자바]
[백준] 10830번 : 행렬 제곱 - JAVA [자바]
2021.05.24https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 알고리즘 [접근 방법] 이 번 문제는 이전에 분할정복 카테고리에서 풀었었던 1629번 : 곱셈 문제를 풀어보았다면 그리 어려운 문제는 아니다. 만약 풀어보지 않으셨다면 위 문제부터 풀고 오신다면 수월하게 이 문제도 풀 수 있으니 한 번 보고오시는 것을 추천드린다. 위 곱셈문제 풀이와 같게 행렬의 지수(exponential)를 절반으로 잘라가면서 분할정복을 해주면 된다. 좀 더 자세하게 말하자면 다음과 같다..
자바 [JAVA] - 퀵 정렬 (Quick Sort)
자바 [JAVA] - 퀵 정렬 (Quick Sort)
2021.05.19[정렬 알고리즘 모음] 더보기 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) Quick Sort [퀵 정렬] 이 번에 다뤄볼 정렬은 퀵 정렬이다. 이름에서도 보이듯이 빠른(Quick) 정렬이다. 아마 다른 블로거 혹은 책에서 본 적이 있다면 느끼실 수 있겠지만, 퀵 정렬의 경우 그 구현방법이 정말 다양..
[백준] 2740번 : 행렬 곱셈 - JAVA [자바]
[백준] 2740번 : 행렬 곱셈 - JAVA [자바]
2021.05.05www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 문제 이 문제가 원래 생각없이 일반적인 행렬 곱셈 방식으로 풀어서 통과했지만.. 분할 정복 카테고리에 들어있어서 어떻게 분할정복으로 풀이해야 할지 많이 고민했던 문제다. 알고리즘 [접근 방법] 문제 자체는 어렵지 않을 것이다. 행렬 곱셈을 그대로 구현해주어도 통과가 되니... 근데 이를 어떻게 분할정복으로 풀지? 라는 고민으로 찾아오신 분들도 꽤 많을 것이다. 필자도 똑같은 고민을 했는데, 알..
자바 [JAVA] - Comparable 과 Comparator의 이해
자바 [JAVA] - Comparable 과 Comparator의 이해
2021.04.29아마 이 글을 찾아 오신 분들 대개는 Comparable과 Comparator의 차이가 무엇인지 모르거나 궁금해서 찾아오셨을 것이다. 사실 알고보면 두 개는 그렇게 어렵지 않으나 아무래도 자바를 학습하면서 객체, 클래스, 인터페이스 등을 배우면서 같이 학습하다보니 혼란스럽게 느껴지기도 하고, 도대체 무엇이 다른지에 대한 이해를 하기가 어렵기도하다. 안그래도 필자의 경우 자료구조와 백준 문제를 풀이하며 포스팅을 하고 있는데, 자료구조의 경우 Heap(PriorityQueue), 백준에서는 정렬문제에서 많이 받은 질문 중 하나여서 이 참에 한 번 정리하고 가는 것이 여러분이 필자가 올리는 글을 이해하는데 더욱 수월할 것 같아 포스팅을 해보고자 한다. 일단 글은 다음과 같은 순서로 진행 할 것이다. 먼저 Co..
[백준] 11401번 : 이항 계수 3 - JAVA [자바]
[백준] 11401번 : 이항 계수 3 - JAVA [자바]
2021.04.23www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 이 전에 풀었었던 정수론 및 조합론 카테고리의 이항 계수 2 문제를 풀었다면 크게 어려움 없이 풀었을 것이다. 알고리즘 [접근 방법] 이 문제는 이 전에 이미 설명해줬기 때문에 내용이 거의 중복될 것이다. 일단 문제를 풀이하기 전에 아래 글을 읽고 오시는 것을 추천드린다. st-lab.tistory.com/162 [백준] 11051번 : 이항 계수 2 - JAVA [자바] www.acmicpc.net/problem/11051 1..
자바 [JAVA] - Hash Set (해시 셋) 구현하기
자바 [JAVA] - Hash Set (해시 셋) 구현하기
2021.04.14자료구조 관련 목록 링크 펼치기 더보기 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..
자바 [JAVA] - Set Interface (셋 인터페이스)
자바 [JAVA] - Set Interface (셋 인터페이스)
2021.04.09•자료구조 관련 목록 링크 펼치기 더보기 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. 우선순위 큐 (Priorit..
[백준] 1629번 : 곱셈 - JAVA [자바]
[백준] 1629번 : 곱셈 - JAVA [자바]
2021.04.07www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 알고리즘 [접근 방법] 이 문제는 얼핏보면 B번 거듭제곱 해주면 될 것 같지만... 왜 분할정복 카테고리에 있겠는가.. A, B, C는 각각 최대 2,147,483,647을 갖을 수 있다는 것이고, 2,147,483,647번 거듭제곱 하는 것 부터 많은 수행 과정과, C로 모듈러 연산까지 해주어야 하기 떄문에 시간초과가 날 것이 너무나 뻔하다. 하지만 문제는 그리 어렵지 않다. 우리가 모두가 배웠던 간단한 '지수 법칙'과 '모듈러 성질'만 알고 있으면 된다. 일단 지수법..
[백준] 1780번 : 종이의 개수 - JAVA [자바]
[백준] 1780번 : 종이의 개수 - JAVA [자바]
2021.04.05www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 색종이 만들기 문제와 매우 유사한 문제다. 알고리즘 [접근 방법] 이 문제는 결코 어렵지 않다. 이전에 색종이 만들기 문제를 풀어보았다면 매우 쉽게 풀 수 있었을 것이다. 기본적인 쿼드트리 방식 문제를 변형한 것인지라 혹시 접근 방법을 모르곘다면 아래 두 문제를 먼저 풀이 방법을 보고 오는 것을 추천드린다. st-lab.tistory.com/227 [백준] 2630번 : 색종이 만들기 - JAV..