소소한필통

Problem https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net About Problem input에서 N이 최대 100000 이고 M이 최대 100000이므로 결국 Output을 0 또는 1로 판단하기 위해서는 M에 들어 있는 숫자를 다 찾아야한다. 하지만 둘다 최대일 때는 100억번을 반복해야 하므로 완전 탐색으로 찾을 수 없다. 그래서 정렬을 하고 빅오를 줄 일 수있는 이분탐색을 통해서 ind..

Problem https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net About Problem 가장 중요한 부분이 N장의 카드에서 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력을 해야한다. 세장의 카드 밖에 없으므로 input에 범위에 따라서 어떤 알고리즘을 쓸지 결정한다 Input N이 100이므로 최대로 했을 때 100 * 99 * 98 이므로 10만정도 된다. 그러므로 dfs, 브루투포스 알고..

Problem https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr About Problem 1. 과녁은 0 ~ 10점까지 총 11개의 종류로 구분된다 2. k(k는 1~10사이의 자연수)점을 어피치가 a발을 맞혔고 라이언이 b발을 맞혔을 경우 더 많은 화살을 k점에 맞힌 선수가 k 점을 가져갑니다. 3. a = b = 0 인 경우, 즉, 라이언과 어피치 모두 k점에 단 하나의 화살도 맞히지 못한 경우는 어느 누구도 k..

문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net About Problem 이 문제는 학생수와 비교 횟수를 주면서, 비교할 수 있는 사람 번호를 주기 때문에 간선 아래와 같이 간선 번호로 나타 낼 수 있다. 여기서 출려을 자신의 키가 몇 번째 인지 알 수 있는 학생들을 모두 구하라고 했으니 모든 정점에서 다른 모든 정점까지 최단 경로를 구할 수 있는 알고리즘인 플로이드 와샬을 썼다. 플로이드 와샬은 O(N^3)이므로 입력 값을 고려해서 쓰는 ..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net About Problem 문제의 핵심은 저 두줄이다. 간선의 정보를 주고 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 구하는 것이다. 간선의 비용이 양수이며 다르고 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘이다. 간선의 최단경로를 구하는 알고리즘은 다음과 같다 Code 코드 설명은 코드 주석으로 적었다. from sys import stdin..