Altiora Petamus

2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 🤔생각해보기 모든 경우의 수를 구한 후, 조건을 초과하지 않는 가장 큰 합을 출력하면 되는 간단한 문제이다. for 문을 돌면서 3가지 카드 '조합'을 구해도 되겠지만, 파이썬 모듈 itertools 를 활용하면 복잡한 과정을 생략할 수 있다. 코드 from itertools import combinations n, m = map(int, input().split()) cards = list(map(int, input().spli..

2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 🤔생각해보기 이 문제는 사실상 최빈값을 구하라는 문제. 나머지는 단순한 연산으로도 구할 수 있다. 최빈값을 구하기 위해 여러가지 방법을 썼지만, 시간초과로 해결하지 못했었는데 Counter를 쓰면 갯수를 세야할 때 아주 편리하다는 것을 알게 되었다. 시간초과 # 최빈값(mode) ; N개의 수들 중 가장 많이 나타나는 값 modes = sorted(numbers, key=lambda x: numbers.count(x), reverse=True) if len(modes) == ..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 🤔생각해보기 지금까지 시작 지점이 하나인 그래프 탐색은 비교적 간단하게 해결할 수 있었다. 하지만 이 문제는 동시에 여러 지점에서 탐색을 진행해야해서 어떻게 해야할까 고민이였는데, 잘 생각해보니 그냥 BFS 알고리즘에다가 시작지점만 여러개를 넣어주면 되는 것이였다. 익은 토마토의 좌표를 찾아서 root 배열에 담아놓는다. BFS 탐색을 위해 queue 에 root 들을 담은 상태로 초기화한다. 미로 탐색 과정을 응용해서 전 칸의 값에 1을 증가시..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 🤔생각해보기 문제는 간단하다. 에라토스테네스의 체를 사용해서 풀면 된다. 개인적으로 소수 구하는 문제에서 자주 쓰는 방법은 제곱근까지만 약수의 여부를 검증해서 O(logN)의 시간 복잡도로 구하는 것이다. 에라토스테네스의 체는 다량의 소수를 한 번에 판별할 때 쓰면 좋은 방식으로 자세한 내용은 다음을 참고하자. 위키독스 온라인 책을 제작 공유하는 플랫폼 서비스 wikidocs.net m, n = map(int, input().split()) a = [False, False] + [True] *..

1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 🤔생각해보기 피타고라스 정리 를 활용하여 원의 교점을 구하는 문제다. 생각보다 고려해야할 조건이 많아서 성공할거라고 확신했음에도 7번 정도 실패했다... 하나씩 조건을 해결해가면 금방 풀 수 있는 문제이니 한 번 정리해보자. 우선 distance = 두 터렛 간의 거리 를 구해야 한다. 거리(distance)가 0 보다 커야 두 터렛이 같은 위치가 아니므로 아래 조건(2~4)을 적용한다. 만약 두 터렛이 각자 계산한 거리 r1, r2, 그리고 distance 중 가장 긴 값이 나머지 두 값의 합보다 크다면 만나지 ..

3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 간단 설명 세 점의 좌표가 주어졌을 때 나머지 점의 좌표를 구하는 문제이다. 🤔생각해보기 축에 평행한 직사각형을 완성하기 위한 좌표의 조건은 무엇인지 생각해보면 된다. x 좌표가 같은 점은 2개씩 있다. y 좌표가 같은 점도 2개씩 있다. 결국 입력으로 들어온 값들을 카운트해서 1개밖에 없는 각 좌표값들을 출력하면 마지막 좌표값이 된다. # 직사각형을 만들기 위해서는 같은 x 좌표가 2개, 같은 y 좌표가 2개 있어야한다. x = [] y = [] for _ in range(3): p1, p2 = map(int, input().split..

1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 🤔생각해보기 이 문제를 요약하면 다음과 같다. 컨테이너 안에 지정된 값(M)이 존재하는지 검사하라. 평소 파이썬을 자주 사용했다면 in 연산자를 사용해볼 법하다. 실제로도 in 만 사용해도 해결할 수 있다. 하지만 이 문제는 이진탐색에 관한 문제이므로 in 연산자를 아는지 묻는 문제는 아닐 것이라 판단하고, 이진탐색에 초점을 맞춰서 문제를 해결하도록 한다. 이진탐색을 하기 위해서는 보통 3가지 인덱스를 활용한다. ..

4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고,..