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] *..

OddOccurrencesInArray coding task - Learn to Code - Codility Find value that occurs in odd number of elements. app.codility.com 🤔생각해보기 Arrays 관련 문제다보니 여러 풀이 방법이 있을 것이다. 그 중에 필자가 가장 먼저 떠오른 방법은 문제의 마지막에 적혀있는 조건과 관련이 있다. all but one of the values in A occur an even number of times. "A 의 값 중 하나를 제외한 모든 값은 짝수로만 발생한다" 단 하나를 제외한 모든 값이 짝수로 발생한다면, 홀수로 발생하는 그 하나를 집어낼 수 있으면 되는 것 아닌가? 개수를 세는 알고리즘은 여러가지가 있지만..

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가지 인덱스를 활용한다. ..