JAVA - 백준 [BAEK JOON]
[백준] 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..
[백준] 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. 현재 상태의..
[백준] 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..
[백준] 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(큐)를 다뤘었다. 큐는 '단방향'이면서 '선입선출(先入先出)' 즉, 먼저..
[백준] 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 클래스를 이용하는 방법이 있다. 이 번에는 이 두 방식 모두 보여주려고 한다. 먼저 덧셈을 구현하는..
[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바]
[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바]
2021.01.23www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 알고리즘 [접근 방법] 큐를 이용한 매우 쉬운 문제다. 예제를 이해해보자면 이렇다. 1부터 N까지 나열 된 수에서 K번째 수 마다 차례대로 뽑아 낸 수열을 출력하는 것이다. 예제를 예로 들어보자. seq {1, 2, 3, 4, 5, 6, 7}, result {} round 1 : seq {1, 2, 3, 4, 5, 6, 7}, result {3} round 2 : seq {1, 2, 4, 5, 6, 7}, result {3, 6} round 3 : seq {1, 2, 4, 5, 7}, re..