본문 바로가기

알고리즘연습90

[백준] 이분 탐색 - 2110번 공유기 설치 java 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사.. 2021. 8. 22.
[백준] 이분 탐색 - 10816번 숫자카드2 java 문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 풀이 이전 문제와 달리 이 문제는 중복되는 값의 개수를 구해야한다. 구하는 방법은, 상한(찾고자하는 값을 초과하는 값이 처음으로 나타나는 위치) - 하한.. 2021. 8. 20.
[Epper] 정수삼각형 java 자바 문제 풀이 문제에서 힌트를 줬듯이..ㅋㅋㅋㅋ dp를 이용하여 풀면 된다. dp를 초기화해주어야 하는데 가장 밑의 층을 입력받은 배열 값들로 초기화해준 후 시작한다. solution 함수에서는 인덱스 값 i, j를 파라미터로 받고 해당 인덱스의 dp 값이 0일 경우에 연산을 진행한다. 이때 아직 의문인 게.. i==n-1일 경우에 dp[i][j]를 return해주도록 작성을 해야 정답이 맞다고 나오는데 이미 초기화를 해주어서 상관 없는 거 아닌가 했는데.... 아닌가보다...... 모범 답안 나오면 그때 다시 확인해보는 걸로... 코드 package Level3; import java.util.Scanner; public class E14No9_정수삼각형 { static int[][]dp; static i.. 2021. 8. 18.
[Epper] 백준 1074번 Z java 자바 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 2^2 × 2^2 크기의 배열.. 2021. 8. 16.

티스토리툴바