소소한필통

Problem https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net About Problem 문제에서 첫번째로 list의 수 N이 주어지고 두번째 줄에 list가 주어지고 세번째에 목표값이 주어진다. 리스트에서 두 수합이 tartgetnum인 것을 찾아야한다. 완탐으로 할 경우 100000 * 99999 이므로 10억번을 찾아야 하므로 제한시간이 1초이므로 timeover가 될것이다. 그러므러 ..

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)이므로 입력 값을 고려해서 쓰는 ..