728x90 투포인터14 [python] 백준 13144 List of Unique Numbers https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 문제 해결 투포인터 (start, end)를 이용해 수열 시작점과 끝점을 잡는다. start==end가 될 수 있다. 한개의 수도 경우의 수에 포함되기 때문이다. end를 +1씩 해가면서 문장 안에 있는 수와 같은 것이 없으면 계속 나아간다. 만약 같은 것이 생기면 start지점을 하나씩 옮겨 가며 같은수를 만날 때 까지 start지점을 이동시킨다. 그래서 중복된 수가 없도록 수열을 만들어나가며 경우의 .. 2023. 5. 6. [python] 백준 7453 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 해결 먼저 n행이면 배열의 크기가 n이라는 것이고 열은 각각 A,B,C,D를 나타낸다는 것을 알아야한다. A,B,C,D를 각각 원소를 찾기에는 (O($n^{4}$))의 시간복잡도가 나오기 때문에 가급적 줄여야한다. 따라서 AB원소의 합을 ab에 CD원소의 합을 cd에 넣어서 줄일려고 하였다.(O($n^{2}$)) 그리고 원소를 각각 오름차순으로 배열을 하고 ab는 인덱스0부.. 2023. 4. 25. [python] 백준 2473 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 해결 전형적인 이분탐색 문제 (세 원소의 합이 C(상수) 일때 세 원소를 구하는 문제) 가장 작은 수를 고정시키고 나머지 두 수를 이분탐색으로 구하는 문제 그런데 python3에서는 시간초과가 난다...ㅜㅜ(pypy3에서는 잘 풀림) 근데 다른 분들도 이렇게 많이 푼듯? CODE import sys input = sys.stdin.readline INF =sys.maxs.. 2023. 4. 24. [python] 백준 3151 합이 0 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 문제 해결 3개의 수를 고르는 문제는 전형적으로 A[i] + A[j] + A[k] = c 에서 A[j] + A[k] = c - A[i]로 바꾼다. c= 0이므로 A[j]+A[k] = -A[i]를 찾는 문제 그러면 A[i]를 고정시키고 j와 k를 찾는 것이 편하다. 처음에 j= i+1 k=n-1으로 정하고 A[j]+A[k] >A[i]면 k를 내리고 A[j] + A[k] < A[i]이면 j를 올리는 식으로.. 2023. 4. 24. 이전 1 2 3 4 다음 728x90
