본문 바로가기
728x90

Algorithm

[백준알고리즘] 2143번: 두 배열의 합 -Python [백준알고리즘] 2143번: 두 배열의 합 -Python https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다. www.acmicpc.net 이제 이런 문제는 간단한 것 같다... 나중에 또 시간이 지나서 풀려하면 어렵겠지만.. 문제에서 요구하는 것은 두 개의 배열 A, B에서.. 더보기
[백준알고리즘] 2632번: 피자판매 -Python [백준알고리즘] 2632번: 피자판매 -Python https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n≤1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기 www.acmicpc.net 두 가지 방법으로 문제를 풀었다. 첫 번째 방법은 기존에 이런 유형의 문제를 풀기 위.. 더보기
[백준알고리즘] 7453번: 합이 0인 네 정수 -Python [백준알고리즘] 7453번: 합이 0인 네 정수 -Python https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 예제 입력 1 복 www.acmicpc.net 이번 문제를 풀기 전에 1208번 부분수열의 합 2를 먼저 풀어.. 더보기
[백준알고리즘] 1208번: 부분수열의 합 2 -Python [백준알고리즘] 1208번: 부분수열의 합 2 -Python 1208번: 부분수열의 합 2 (acmicpc.net) 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 기존의 풀었던 1182번 부분수열의 합과 요구하는 것은 같다. 아래는 기존에 풀었던 코드다. 물론 이번 문제에서는 절대 통과되지 않는다. import sys from itertools import combinations n, s = map(int, sys.stdin.readline().split()) arr .. 더보기
[백준알고리즘] 1806번: 부분합 -Python [백준알고리즘] 1806번: 부분합 -Python https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길 www.acmicpc.net 이번 문제는 저번에 풀었던 2003번 수들의 합 문제와 유사했다. 다만, 여기서는 주어진.. 더보기
[백준알고리즘] 2003번: 수들의 합 2 -Python [백준알고리즘] 2003번: 수들의 합 2 -Python https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 두 가지 방법으로 문제를 해결했다. 쉽게 봤다가 시간제한이 0.5 임을 나중에 보고 Python으로 포기하기도 했었다.. 결국 Python으로도 통과하긴 했다. 연속합을 직접 구해준 방법 더블 포인터를 사용해 값을 찾아간 방법 1번 방법 처음에는 1부터 I까지의 합에서 1부터 J까지의 합을 빼서 J부터 K까지의 값.. 더보기
[백준알고리즘] 1182번: 부분수열의 합 -Python [백준알고리즘] 1182번: 부분수열의 합 -Python https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 뻘짓했당 부분 수열이라고만 했는데 연속된 부분 수열인 줄 알고 계속 시도했었다.. 반례도 찾아가면서... 그러다가 아래의 반례를 찾고는.. 그냥 아무렇게나 뽑아서 만든 부분 수열이란 것을 알았다. 5 0 0 0 0 0 0 output:31 바로 combinations 메서드 써서 통과했다. 1 2 3 4 .. 더보기
[백준알고리즘] 1987번: 알파벳 -Python [백준알고리즘] 1987번: 알파벳 -Python https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 20200404. 새로 풀었다. 이번에도 PyPy로만 통과가 가능했다. 처음에는 모양이 달.. 더보기
728x90

티스토리툴바