JAVA - 백준 [BAEK JOON]
[백준] 2108번 : 통계학 - JAVA [자바]
[백준] 2108번 : 통계학 - JAVA [자바]
2020.06.01www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 그리 어렵지 않은 문제지만 약간의 함정이 있으니 주의해야한다. ※ 주의할 점 동일한 최빈값이 있을경우 '두 번째로 작은 값'을 출력해야 한다. 알고리즘 [접근 방법] 기본적으로 이 문제를 풀기 위해서는 Counting Sort(카운팅 정렬)을 사용할 것이다. 물론 정렬을 쉽게 하기 위해 Arrays.sort 로 풀 수도 있지만 최빈값을 구하는 과정에 있어 '두 번째로 작은 값'을 출력해야하다보니 조금 복잡해진다. (사실상 중앙값 때문에 정렬..
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]
2020.05.31www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 드디어 그동안의 기본정렬을 끝맺는 끝판왕 문제다! ※ 주의할 점 Java 의 시간 제한은 3초다. (원래 자바의 경우 언어 보너스가 있어 주어진 시간의 ×2 + 1 초가 주어지지만 이번에는 3초를 넘길 수 없다) (2021. 01. 10 기준 Java → Java8로 명칭이 바뀌었다.) Java 의 메모리 제한은 512MB 이다. 알고리즘 [접근 방법] 이전의 수 정렬하기 문제 포스팅을 보셨다면 이 문제는 쉽게 풀 수 있을..
[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]
[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]
2020.05.30www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 수 정렬하기에 이은 두 번째 문제다. 차이점이라면 데이터도 이전 문제에 비해 1000배 많아졌고, 수의 범위도 1000배 넓다. ※ 주의할 점 Java기준 Arrays.sort 로 쓰면 시간초과가 날 가능성이 높다. (2021.01.11 Java → Java8 명칭이 변경됨) 알고리즘 [접근 방법] 이 문제를 풀기 전에 참고했으면 하는 글 두 개를 넣겠다. 문제를 푸는데 있어 매우 도움이 될 ..
[백준] 2750번 : 수 정렬하기 - JAVA [자바]
[백준] 2750번 : 수 정렬하기 - JAVA [자바]
2020.05.29www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 정렬의 가장 기초적인 문제다! 9가지 방법을 이용하여 풀이한다. 먼저 정렬 방법은 여러가지가 있지만 가장 쉽게 쓸 수 있는 방법은 크게 3가지가 있다. 먼저, 선택정렬이다. 첫 번째 인덱스부터 시작하여 뒤의 인덱스들의 값들과 비교하여 최솟값들을 차곡차곡 쌓아나가는 방법이다. 가장 구현하기 쉽다는 장점이 있으나 시간복잡도가 O(n2) 으로 그리 좋은 성능의 알고리즘은 아니다. 아마 정렬을 구현해보거나 접해본 분들..
[백준] 1436번 : 영화감독 숌 - JAVA [자바]
[백준] 1436번 : 영화감독 숌 - JAVA [자바]
2020.05.27www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 문제 매우 간단한 문제지만 예외의 상황을 잘 고려해야 하는 문제다. 알고리즘 [접근 방법] 이 문제의 경우 브루트포스를 사용할 수도, 사용하지 않을 수도 있는 문제다. 두 가지 접근법을 살펴보도록 하자. [방법 1] 일단 N 번째 ( 1 ≤ N ≤ 10000 ) 로 큰 "666" 이 들어가는 수를 찾아야 한다. 가장 간단하게 브루트포스를 사용하는 방법은 N 의 최솟값은 1 이니 결국 666부터 시작하여, 1 ..
[백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]
[백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]
2020.05.26www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 매우 간단한 문제다! ※ 주의할 점 어떤 크기로 주어지던, 최소로 칠할 수 있는 8×8 크기를 찾아내야 한다. 알고리즘 [접근 방법] 어려운 문제는 아니다. 체스판을 만들기 위해서는 한 칸이 상하좌우의 색과 다르면 된다. 또한 체스판이 잘못 칠해져 있는 경우 '최소'의 개수로 칠 할 수 있는 부분을 찾아야 한다. 경우의 수는 (가로 칸 개수 - 7) × (세로 칸 개수 - 7) 이다. 그림으로 본다..
[백준] 7568번 : 덩치 - JAVA [자바]
[백준] 7568번 : 덩치 - JAVA [자바]
2020.05.21www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩� www.acmicpc.net 문제 매우 간단한 문제다! ※ 주의할 점 키와 몸무게가 모두 클 때에만 '덩치가 크다' 라고 정의하고 있다. 알고리즘 [접근 방법] 이번에도 역시 브루트포스를 이용하여 푸는 문제다. 먼저 문제를 보면 '덩치가 크다'는 기준은 키와 몸무게가 모두 비교하려는 대상보다 클 때이다. 즉, 어느 한 쪽이라도 만족 못할 경우 덩치가 크다고 할 수 없다. 그럼 브루트포스로 어떻게 풀 수 있을까? 일단 키와 몸무..
[백준] 2231번 : 분해합 - JAVA [자바]
[백준] 2231번 : 분해합 - JAVA [자바]
2020.05.20www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 문제 이번 문제도 브루트포스를 이용하여 푸는 문제다! 알고리즘 [접근방법] 문제가 그리 어렵지 않다. 198 = 198 + 1 + 9 + 8 = 216 예로들어 198 이라는 생성자가 주어졌을 때 198 의 분해합은 198 + 1 + 9 + 8 = 216 이다. 반대로 216 의 생성자는 여러가지가 있다. 예로들어 앞선 예제처럼 198 이 될 수도 있고 207 이 될 수도 있다. 즉, ..
[백준] 2798번 : 블랙잭 - JAVA [자바]
[백준] 2798번 : 블랙잭 - JAVA [자바]
2020.05.19www.acmicpc.net/problem/2798 2798번: 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 �� www.acmicpc.net 문제 문제가 그리 어렵지 않다! 알고리즘 [접근 방법] 브루트 포스 (Brute Force) 카테고리의 첫 문제다. 브루트 포스.. 난폭한(무식한) 힘이라는 의미 그대로 어떤 값을 찾아내기(또는 목적을 달성하기) 위해 무차별적으로 대입해보는 방법이다. 말 그대로 무식한 방법이다. (일명 노가다..) 이 알고리즘의 가장 큰 특징은 가능한 모든 경우의 수를 대입해보며 조건에 만족하는 값만을 찾아낼 수 있다는 점이다. ..
[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]
[백준] 11729번 : 하노이 탑 이동 순서 - JAVA [자바]
2020.05.16www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 백준 단계별로 풀어보기의 재귀 문제 중 마지막 문제다. 알고리즘 [접근 방법] 이전의 재귀 문제를 그동안 풀어봤다면 이번 문제는 그리 어렵지 않은 문제다. 직전 문제인 별찍기 10 에서도 볼 수 있듯이 재귀를 통해 '가장 작은 단위' 가 될 때 까지 재귀호출을 하고, 가장 작은 단위까지 호출이 되었으면, 거기서 구현한 연산을 실행하면 된다. 이 문제도 같은 원리다. 하노이탑 개수와 상관없이, ..