JAVA - 백준 [BAEK JOON]/기타 문제
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
2021.06.26https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 문제 이 번 문제는 분할 정복 카테고리의 마지막 문제인만큼 조금 많이 어려운 문제다. 분할 정복 방식 자체는 이전 문제인 히스토그램에서 가장 큰 직사각형과 접근 방식은 유사하나 조금 더 신경써야할 부분들이 존재하므로 같이 알아보도록 하자. 알고리즘 [접근 방법] 이 번 문제의 경우 일반적인 분할 정복 방식과 스윕 라인 방식 이렇게 두 가지 풀이 방식이 존재한다. 일..
[백준] 17298번 : 오큰수 - JAVA [자바]
[백준] 17298번 : 오큰수 - JAVA [자바]
2021.01.21www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 Stack의 원리를 이해하면 생각보다 그리 어렵지는 않다. 알고리즘 [접근 방법] 이 문제가 의외로 어떻게 스택을 활용해야할지 갈피를 못잡는 문제인 것 같다. 이중 for문을 사용하면 최대 1,000,000 * 1,000,000 = 1,000,000,000,000 (1조)으로 시간초과 날 것이 뻔하다. 스택의 기본 원리는 딱 한 가지만 기억하면 된다. '후입선출' 즉, 가장 최근에 들어온 것이 가장 먼저 나오는 것이다...
[백준] 15236번 : Dominos - JAVA [자바]
[백준] 15236번 : Dominos - JAVA [자바]
2020.11.01www.acmicpc.net/problem/15236 15236번: Dominos Dominoes are gaming pieces used in numerous tile games. Each domino piece contains two marks. Each mark consists of a number of spots (possibly zero). The number of spots depends on the set size. Each mark in a size N domino set can contain between 0 and N www.acmicpc.net 문제 오늘은 조금 특별하게 영어 문제를 들고 왔다. 어렵지 않은 문제라 쉽게 풀 수 있다. 알고리즘 [접근 방법] 해석하기 귀찮으신 분들을 위..
[백준] 11653번 : 소인수분해 - JAVA [자바]
[백준] 11653번 : 소인수분해 - JAVA [자바]
2020.10.18www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 소인수 분해 문제다. 찾아보니 중학교 교과과정에서 배운다고 하니 아마 다들 쉽게 풀 수 있을 듯 하다. 알고리즘 [접근 방법] 소인수분해 문제 자체는 어렵지 않으니 잠깐 소인수분해에 대해 알아보면 좋을 것 같다. 소인수분해가 어릴 때 부터 배우면서 약수와 배수를 구하기 위해 쓰이면서 자연스럽게 많이 쓰기 때문에 어떤 것인지는 대강 알고있으나 정확한 정의나 왜 소인수분해인지는 모르고 가는 경우가 많다. 사실 수학용어를 번역하면서 한자 뜻을 빌려와 쓰기 때문에 그렇기도 하다. 오히려 영어 뜻을 그대로 번역하는게 이해하기 쉬울 때..
[백준] 1003번 : 피보나치 함수 - JAVA [자바]
[백준] 1003번 : 피보나치 함수 - JAVA [자바]
2020.07.22www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 이전의 피보나치 수를 풀어보셨다면 쉽게 풀 수 있는 문제다. 이 문제는 피보나치 수를 구할 때, fibonacci(0)과 fibonacci(1)이 각각 몇 번 호출되는지를 묻는 문제다. 알고리즘 [접근 방법] 이 문제 또한 풀이방법은 여러가지다. 대표적으로 정석적인 방법인 재귀(Top-Down)를 이용하여 풀이하는 방법이 있고, 다른 하나는 반복문(Bottom-Up)을 사용하여 계산하는 방법이 있다. 혹여 피보나치 수를 DP로 풀이하는 방법을 모르신다면 아래 링크의 포스팅을 한 번 읽어보고 오는 것을 ..
[백준] 2748번 : 피보나치 수 2 - JAVA [자바]
[백준] 2748번 : 피보나치 수 2 - JAVA [자바]
2020.07.21www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net 문제 동적 계획법 1의 첫 문제다. 확인한바 동적계획법에서 사라졌다. (2021.01.02) 이 전 재귀 문제에서도 피보나치 수 문제를 올려둔 것이 있으니 한 번 아래 포스팅을 참고해보시는 것도 좋을 것 같다. st-lab.tistory.com/94 [백준] 10870번 : 피보나치 수 5 - JAVA [자바] st-lab.tistory.com 알고리즘 [접근 방법] 피..
[백준] 1011번 : Fly me to the Alpha Centauri - JAVA [자바]
[백준] 1011번 : Fly me to the Alpha Centauri - JAVA [자바]
2020.04.07https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 www.acmicpc.net 문제 생각보다 정답률이 낮은 문제다. 그러나 막상 규칙을 찾으면 매우매우 쉬운 문제이니 한 번..
[백준] 10996번 : 별 찍기 - 21 - JAVA [자바]
[백준] 10996번 : 별 찍기 - 21 - JAVA [자바]
2020.03.15https://www.acmicpc.net/problem/10996 10996번: 별 찍기 - 21 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 문제 위 문제는 다른 별 찍기에 비해 쉬운 편이다! 아래 알고리즘에서 한 번 차근차근 알아보자. 3가지 풀이방법을 제시한다. Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다. 또한 BufferedReader 에서 출력방법을 바꿔보며 어느 방법이 시간을 더 단축 시킬 수 있는지 한 번 보고자 한다. 알고리즘 먼저 출력 방법을 자세히 보자. 1. 먼저 N 이라는 숫자가 주어진다. 그럼 총 출력 행은 2N 개다. 이 N 이라는 숫자에 따라 1 ..
[백준] 2446번 : 별 찍기 - 9 - JAVA [자바]
[백준] 2446번 : 별 찍기 - 9 - JAVA [자바]
2020.03.13https://www.acmicpc.net/problem/2446 2446번: 별 찍기 - 9 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 문제 별 찍기 응용문제로 가장 많이 나오는 문제 중 하나다. 처음에는 어떻게 해야할지 모르더라도 막상 이해한다면 매우 쉬운 문제이니 차근차근 살펴보자. 3가지 풀이방법을 제시한다 Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다. 또한 BufferedReader 에서 출력방법을 바꿔보며 어느 방법이 시간을 더 단축 시킬 수 있는지 한 번 보고자 한다. 알고리즘 출력 행은 총 2N-1 줄 이다. 먼저 N 이라는 숫자가 주어진다. 1. 1 행..
[백준] 2523번 : 별 찍기 - 13 - JAVA [자바]
[백준] 2523번 : 별 찍기 - 13 - JAVA [자바]
2020.03.13https://www.acmicpc.net/problem/2523 2523번: 별 찍기 - 13 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 문제 문제를 유추해서 별을 찍으라고 한다. 딱히 유추할 것도 없이 보면, 숫자 N 을 입력받으면 N 까지 별을 1개씩 늘려가며 별을 찍고, 그 이후부턴 1개씩 줄여가면 찍으면 된다. 3가지 풀이방법을 제시한다. Scanner 로 입력받아 연산하는 방법과 BufferedReader 로 입력받아 연산하는 방법, 두 가지 방법을 통해 풀이해보고자 한다. 또한 BufferedReader 에서 출력방법을 바꿔보며 어느 방법이 시간을 더 단축 시킬 수 있는지 한 번 보고자 한다. 알고리즘 먼저 N 이라는 숫자가 주어진다. 1 행부터 ..