본문 바로가기

알고리즘/백준122

[백준/자바] 11050 이항 계수 구하기 1 [백준/자바] 11050 이항 계수 구하기 1 📌 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N/K)를 구하는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N) 📣 출력 💎 문제분석하기 조합론 이항계수의 기본 문제 2차원 배열에 value를 채워넣어 최종적으로 D[5][2]를 구하면 된다 이때 두 가지 규칙을 사용한다 i) 기본 특성 - iC1 = i = i개 중 1개를 뽑는 경우의 수는 i개 - iC0 = 1 = i개 중 1개도 선택하지 않는 경우의 수는 1개 - iCi = 1 = i개 중 i개를 선택하는 경우의 수는 1개 ii) 조합의 점화식 - nCk + nCk+1 = n+1Ck+1 💡 코드 구현하기 import .. 2022. 11. 27.
[백준/자바] 11404 플로이드 [백준/자바] 11404 플로이드 📌 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다.. 2022. 11. 26.
[백준/자바] 1948 임계경로 [백준/자바] 1948 임계경로 📌 문제 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라. 출발 도시는 들어오는 도로가 0개이고, 도착 도.. 2022. 11. 26.
[백준/자바] 1717 집합 표현하기 [백준/자바] 1717 집합 표현하기 📌 문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. ⚔ 입력 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합.. 2022. 11. 25.
[백준/자바] K번째 수 [백준/자바] K번째 수 📌 문제 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. ⚔ 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 10^5 보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다. 📣 출력 B[k]를 출력한다. 💎 문제분석하기 /** * 문제에서 배열은 N X N 형식의 정사각형으로 주어지고 각 요소들은 A[i][j]이기 때문에 * n의 배수 형태가 된다 * 이것을 (1) 사실로 두고 * * 다음으로 k의 성질에 대해 살.. 2022. 11. 24.

티스토리툴바