본문 바로가기
728x90

알고리즘339

[python] 백준 12891 DNA 비밀번호 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 문제 해결 긴 문자열에서 정해진 문자열 개수 p로 자른 다음 개수를 확인하는 문제이다. 왼쪽부터 한 칸씩 문자열을 p개씩 슬라이싱 했을 때 주어진 조건을 만족시키면 가능한 경우의 수이므로 정답 +1씩 올린다. 문자열은 한칸씩 이동하므로 한번 0~p-1까지 문자를 확인한다음 가장 왼쪽 인덱스의 문자를 제외시키고 오른쪽에 한칸 씩 문자를 추가시킴으로써 계산을 최소화 시킬 수 있.. 2023. 2. 19.
[python] 백준 1253 좋다 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 해결 리스트 안의 서로 다른 두 수의 합이 리스트 안의 다른 수가 되는 경우의 수를 구하는 문제이다. 리스트 안의 서로 다른 두 수의 합을 비교하는 것이므로 리스트를 올림차순으로 정렬하고 투포인터 이용하는 것이 좋아 보인다. 두 수의 합이 리스트 안에 있어도 3 + 0 = 3 등 다른 수가 되지 않으면 그 경우는 경우의 수로 계산하지 않는다. CODE import sys input = sys.stdin.readline .. 2023. 2. 18.
[python] 백준 2018 수들의 합 5 https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 해결 n = n 이므로 최소 1개는 있다. 연속된 수의 합을 고려 투 포인터를 이용하여 첫 번째 수와 마지막 수에 포인터를 두어 연속된 수의 합을 구할 수 있다. 왼쪽 포인터에서 오른쪽 포인터까지 합을 s라고 정의하자. 연속된 수의 합이 n보다 작으면 오른쪽 포인터를 오른쪽으로 이동시키고 s에 오른쪽 포인터 값을 더한다. 연속된 수의 합이 n보다 크면 s에서 왼쪽 포인터.. 2023. 2. 18.
[python] 백준 1940 주몽 https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 해결 두 수의 합이 특정한 수(m)이 되야함. 리스트를 올림차순으로 정렬하고 투포인터를 이용해 두 수의 합을 구한다. 두 수의 합이 m보다 크면 오른쪽 포인터를 왼쪽으로 옮긴다. 두 수의 합이 m보다 작으면 왼쪽 포인터를 오른쪽으로 옮긴다. 두 수의 합이 m과 같으면 정답 ans를 1을 올리고 왼쪽 포인터를 오른쪽으로 한 칸, 오른쪽 포인터를 왼쪽으로 한 칸 옮겨서 .. 2023. 2. 18.
728x90