K

# DNA 비밀번호 # 첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000) # 두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다. # 세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. # 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다. # 첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라. checkList = [0] * 4 # 부분문자열에 포함되어야 할 최소 개수 myList = [0] * 4 # 부분문자열 문자의 개수 checkS..

투 포인터를 활용한 문제 이 문제의 핵심은 본인을 제외했는가 인 것 같다. 예를 들어, 0 3 5 8 11이 주어졌을 때 답은 2(8, 11)이다. 그러나 본인을 제외하는 예외처리를 하지 않는다면, 0 + 3 = 3, 0 + 5 = 5 등 0이 카운팅 되어서 답안에 중복이 생긴다. 그렇기 때문에 if num[i] + num[j] == num[k] 안에서 if i != k and j != k를 통해 한 번 더 거르는 작업이 필요하다. # 좋다 # N개의 수 중 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있으면 그 수를 '좋다'고 한다. # N개의 수 중 몇 개가 좋은 수인지 출력하시오. 수가 같아도 위치가 다르면 다른 수이다. # 첫째 줄에는 수의 개수 N, 둘째 줄에는 N개의 수가 주어진다. impo..

투 포인터를 활용한 문제 제한시간은 2초지만 N의 범위가 15,000까지기 때문에 O(nlogn)의 시간복잡도 내에 풀면 된다. 파이썬의 정렬 라이브러리인 sort를 이용할 수 있다. 파이썬의 정렬 라이브러리는 병합정렬 기반으로 O(nlogn)의 시간복잡도를 가진다. 정렬 후 맨 앞과 맨 끝 인덱스를 기준으로 비교를 시작한다. 둘의 합이 M이 됐다면 cnt++ 후 각 값을 1씩 옮긴다. 둘의 합이 M보다 작다면 시작 인덱스 i++를 한다. 둘의 합이 M보다 크다면 끝 인덱스 j--를 한다. # 주몽 # 두 숫자를 합쳐 M이 되어야 한다. N개의 숫자와 M이 주어졌을 때 몇 개의 조합이 만들어지는지 구하시오. # 첫째 줄에는 숫자의 개수N이 주어진다. 두 번재 줄에는 M이 주어진다. 세 번째 줄에는 N개의..

투 포인터를 활용한 문제 start와 end 포인터를 이용해서 문제를 해결했다. 합이 n과 같다면 cnt++을 한 후 end++ 합이 n보다 크다면 합에서 start 값을 빼준 후 start++ 합이 n보다 작다면 end++ 후 sum에 값 더하기 sum에 더하는게 먼저인지 end++이 먼저인지 판단하는게 중요한 듯하다. # 수들의 합 5 # 어떠한 자연수 N은 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 이 N에 대해서 몇 개의 연속된 자연수의 합으로 나타낼 수 있는지 가지수를 알고 싶다. # 첫 줄에 정수 N이 주어진다. 가지수를 출력하시오. n = int(input()) start = 1 end = 1 sum = 1 cnt = 1 while end != n: if sum == n: cnt +=..

나머지가 같은 수를 고른다면, 그 둘 사이의 값은 나머지가 0이 된다는 게 메인 포인트같다. 예를 들어.. 1 2 3 1 2 의 숫자가 주어진다면, 구간합은 1 3 6 7 9가 된다. 1 3 6 7 9 를 3으로 나눈 값은 1 0 0 1 0 이 된다. 만약 구간을 A[0] ~ A[3] 으로 정했다면, 7(1,2,3,1) - 1 = 6이 되고, 나머지는 0이 된다. # 나머지가 같은 경우 중 2개를 뽑는 경우의 수 계산 에서 if문 범위를 > 1 로 한 이유는 범위로 뽑는 수는 시작과 끝 2개인데, 나머지가 같은 수가 2개 이상 존재해야 2개를 뽑을 수 있기 때문이다. # 나머지 합 # N개의 수가 주어진다. 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. # ..

문제 이해가 너무 안됐다. 글을 모호하게 써둔 것 같음..;; (2,2) ~ (3,4)의 합을 구할 때 (3,1)이 빠지는 이유를 .. 흠 그래서 처음엔 구간 합을 총 누적으로 계산했었다. n, m = map(int, input().split()) origin = list() z = 0 result = list() # 원본 배열 입력 for i in range(0, n): a = list(map(int, input().split())) origin.append(a) # 합배열 생성 sum = [[0]*(n+1)] for i in range(0, n): a = list() for j in range(0, n): z += origin[i][j] a.append(z) sum.append(a) # 합배열 각 행..

# 구간 합 구하기 4 # 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오: # 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. # 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. # 1

Do it! 알고리즘 코딩 테스트 - 파이썬 편 (김종관) 책을 이용하여 알고리즘 공부 중입니다 😃 https://youtu.be/O514yiWg8YE?si=2U5WPE1m75BjhSHN 리스트 A가 있을 때 합 배열 S의 정의 : S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ... + A[ i - 1 ] + A[ i ] 합 배열 S를 만드는 공식 : S[ i ] = S[ i - 1 ] + A[ i ] A[ i ] ~ A[ j ] 구간 합을 구하는 공식 : S[ j ] - s [ i - 1 ] S[ j ] = A[0] + A[1] + ...+ A[ i - 1 ] + A[ i ] + ... + A[ j ] S[ i ] = A[0] + A[1] + ...+ A[ i - 1 ] + A[ i..

# 평균 # 자기 점수의 최댓값을 고른 후, 모든 점수에 점수/최댓값*100 을 한다. # 첫째 줄에 시험 본 과목의 개수 N(

# 숫자의 합 # N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. # 첫째 줄에 숫자의 개수 N(1~100), 둘째 줄에 숫자 N개가 공백 없이 주어진다. # 입력으로 주어진 숫자 N개의 합을 출력한다. n = input() num = input() total = 0 for i in range(0, int(n)): b = num[i] total += int(b) print(total) 거의 4년만에 하는 파이썬이라 문법이 하나도 기억나지 않는다.. ;; for문부터 검색해가며 차근차근..