greentea31's Note

https://greentea31.tistory.com/36

풀이 과정

https://greentea31.tistory.com/36

위의 연속합 문제에서 수열에서 수를 하나 제거할 수 있다는 조건이 추가된 문제이다. 

d[i]를 i번째 원소를 마지막으로 하는 가장 큰 연속합이라 하고, d2[i]를 i번째 원소에서 시작하는 가장 큰 연속합이라 하자. 그렇다면 i번째 원소를 제거했을 경우의 연속합을 구하면 d[i-1] + d2[i+1] 임을 알 수 있다.

d[i]의 점화식은 위의 문제를 풀어봤다면,

d[i] = d[i-1] + a[i] (d[i-1] > 0)

       = A[i] (d[i-1] <= 0) 임을 알 수 있고,

d2[i]의 점화식은 위의 점화식을 조금 변형한

d2[i] = d2[i+1] + a[i] (d2[i+1] >= 0)

         =  a[i] (d2[i+1] < 0) 임을 알 수 있다.

수열의 모든 원소 i에 대해 d[i], d[i-1] + d2[i+1]을 구해보고 구한 값들 중 가장 큰 값을 정답으로 출력해주면 된다.

소스 코드

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

d = [i for i in A]
d2 = [i for i in A]

for i in range(1, n):
    d[i] = max(d[i-1] + A[i], A[i])

for i in range(n-2, 1, -1):
    d2[i] = max(d2[i+1] + A[i], A[i])

max1 = max(d)
max2 = -1001

for i in range(1, n-1):
    max2 = max(max2, d[i-1] + d2[i+1])

print(max(max1, max2))

https://www.acmicpc.net/problem/11054

풀이 과정

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라 한다.

그렇다면 Sk를 기준으로 하는 바이토닉 수열의 길이는 Sk를 마지막으로 하는 증가하는 부분 수열의 길이 + Sk를 시작으로 하는 감소하는 부분 수열의 길이 - 1임을 알 수 있다.

따라서 주어진 수열의 모든 원소 K에 대해 K를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 + K를 시작으로 하는 가장 긴 감소하는 부분수열의 길이 - 1을 구한 뒤, 가장 긴 값이 바로 가장 긴 바이토닉 부분 수열의 길이이다.

https://greentea31.tistory.com/34

https://greentea31.tistory.com/62

이 문제는 위의 2문제의 풀이법을 합쳐서 해결할 수 있는 문제이고 각 문제의 풀이를 위한 점화식은 위의 두 글을 참고하면 된다.

소스 코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

d = [1 for _ in range(N)]
d2 = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            d[i] = max(d[i], d[j] + 1)

for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if A[j] < A[i]:
            d2[i] = max(d2[i], d2[j] + 1)

d3 = [d[i] + d2[i] - 1 for i in range(N)]

print(max(d3))

https://www.acmicpc.net/problem/11722

풀이 과정

https://greentea31.tistory.com/34

가장 긴 증가하는 부분 수열 -> 가장 긴 감소하는 부분 수열임을 제외하면 위의 문제의 해결법과 풀이과정이 일치한다.

가장 긴 증가하는 부분 수열을 구하는 점화식

D[i] = max(D[J]) + 1 (j < i, A[j] < A[i])

에서 부등호만 다음과 같이 바꿔주고 코드로 구현하면 문제를 해결할 수 있다.

D[i] = max(D[J]) + 1 (j < i, A[j] > A[i])

소스 코드

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

d = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] > A[i]:
            d[i] = max(d[i], d[j] + 1)

print(max(d))

https://www.acmicpc.net/problem/11055

풀이 과정

https://greentea31.tistory.com/34

11053번 문제와 비슷한 점화식을 세워서 문제를 해결할 수 있다.

sum[i] -> i번째 원소를 마지막으로 하는 합이 가장 큰 증가 부분수열 이라고 하면 다음과 같은 점화식이 성립한다.

sum[i] = max(sum[j]) + A[i] (j < i, A[j] < A[i])

소스 코드

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
sum = [x for x in A]

for i in range(n):
    for j in range(i):
        if A[j] < A[i]:
            sum[i] = max(sum[i], sum[j] + A[i])

print(max(sum))

https://programmers.co.kr/learn/courses/30/lessons/68935

풀이 과정

45(10) = 1200(3)

10진수 자연수를 입력받고 뒤집은 3진수로 변환하려면 3보다 작아질때 까지 나눠가면서 나머지를 문자열에 붙이고, 3보다 작아진 몫을 문자열에 또 붙여주면 된다.

이제 그 문자열을 다시 3진법의 자릿수를 고려하면서 10진수로 바꾼 후 출력해주면 된다.

나는 자릿수를 계산하면서 '0021' = 2*(3^1) + 1*(3^0) 이런식으로 해결하였으나 파이썬에서는

int('n진수 문자열', n)으로 n진수 문자열을 10진수 정수로 바꿀수 있다.

ex) int('ABCD', 16) = 43981

      int('101010111101', 2) = 2749

소스 코드

def solution(n):
    answer = 0
    temp_string = ''
    while n >= 3:
        temp_string += str(n % 3)
        n //= 3
    temp_string += str(n)
    
    for digit in range(len(temp_string)):
        answer += int(temp_string[digit]) * (3 ** (len(temp_string) - (digit + 1)))
    
    return answer​

https://programmers.co.kr/learn/courses/30/lessons/77884

풀이 과정

문제에서 주어진 입출력 예를 보다 보면 제곱수에서만 약수의 개수가 홀수가 됨을 깨달을 수 있다.

left <= N <= right인 모든 N에 대하여 제곱근이 정수이면 약수의 개수가 홀수, 정수가 아니면 약수의 개수가 짝수라고 판단할 수 있다.

소스 코드

def solution(left, right):
    answer = 0
    for number in range(left, right+1):
        if number ** (1/2) == int(number ** (1/2)):
            answer -= number
        else:
            answer += number
    return answer

https://programmers.co.kr/learn/courses/30/lessons/1845

풀이 과정

폰켓몬을 가장 많이 고르는 경우 몇가지를 고를 수 있냐를 리턴해주면 된다.

모두 다른 종류의 폰켓몬이 들어왔다 해도 N/2개 만큼의 폰켓몬만 고를 수 있고, 폰켓몬의 종류가 3가지 밖에 안들어왔다면 5000개의 폰켓몬이 들어왔다 하더라도 3가지의 폰켓몬 밖에 고를수 없음을 알 수 있다.

따라서 답은 min(폰켓몬의 종류, N/2)이다.

소스 코드

def solution(nums):
    answer = 0
    dictionary = {}
    for i in nums:
        if i not in dictionary:
            dictionary[i] = 1
        else:
            dictionary[i] += 1
    
    min_value = min(len(dictionary), len(nums) // 2)
    answer = min_value
        
    return answer

https://programmers.co.kr/learn/courses/30/lessons/42862

소스 코드

파이썬

def solution(n, lost, reserve):
    real_lost = set(lost) - set(reserve)
    real_reserve = set(reserve) - set(lost)
    answer = n - len(real_lost)

    for people in real_lost:
        if people - 1 in real_reserve:
            answer += 1
            real_reserve.remove(people - 1)
            continue
        if people + 1 in real_reserve:
            answer += 1
            real_reserve.remove(people + 1)

    return answer

자바스크립트

function solution(n, lost, reserve) {
    var answer = 0;
    let students = {}
    for (let i = 1; i <= n; i++) {
        students[i] = 1
    }

    lost.forEach(number => students[number] -= 1)
    reserve.forEach(number => students[number] += 1)

    for (let i = 1; i <= n; i++) {
        if (students[i] === 2 && students[i-1] === 0) {
            students[i-1] += 1
            students[i] -= 1
        } else if  (students[i] === 2 && students[i+1] === 0) {
            students[i+1] += 1
            students[i] -= 1
        }
    }

    for (let keys in students) {
        if (students[keys] >= 1) {
            answer += 1
        }
    }

    return answer;
}

풀이 과정

파이썬: set의 차집합 연산을 사용하여 lost, reserve에 둘 다 포함되어 있는 학생은 두군데에서 다 제외하고, 답의 초기값을 학생수 - 체육복을 도난 당한 학생수로 설정하였다. 그리고 lost에 속한 학생 번호의 왼쪽, 오른쪽을 순서대로 보면서 reserve에 포함되어 있는 학생이 있으면 체육복을 빌려오고 답의 개수를 1 증가시켰다.

자바스크립트: 일단 학생들이 체육복을 하나씩 갖고 있다고 가정하고, lost와 reserve 배열을 보면서 체육복의 개수를 하나 줄이거나 늘렸다. 그 후 2개 가지고 있는 사람의 왼쪽, 오른쪽을 순서대로 보면서 체육복이 없는 사람에게 체육복을 하나 빌려주었고, 체육복을 하나 이상 갖고 있는 학생의 수를 답으로 도출했다.

https://programmers.co.kr/learn/courses/30/lessons/42748

소스 코드

파이썬

def solution(array, commands):
    answer = []
    for command in commands:
        temp_list = array[command[0] - 1 : command[1]]
        temp_list.sort() # 재할당 필요없이 그냥 리스트가 정렬됨
        answer.append(temp_list[command[2] -1])
    return answer

자바스크립트

function solution(array, commands) {
    var answer = [];
    for (command of commands) {
        temp_array = array.slice(command[0] - 1, command[1])
        temp_array.sort((a, b) => a - b) // sort() 입력시 문자열 형태로 정렬됨에 유의
        answer.push(temp_array[command[2] - 1])
    }
    return answer;
}

풀이 과정

문제에서 시키는 대로 문자열을 자르고, 정렬하고, k번째 원소를 answer 배열에 넣으면 된다.

파이썬에서는 name = list[a:b] 시 list의 a ~ b-1번째 원소가 name에 들어가고

자바스크립트에서는 var name = list.slice(a, b)로 동일한 동작을 수행할 수 있다.

숫자의 정렬은 파이썬에서는 list.sort()로 그냥 list의 원소를 오름차순으로 정렬할수 있지만

자바스크립트에서는 array.sort() 사용시 문자열로 처리되어 정렬이 되기 때문에 원하는 대로 숫자의 대소관계로 정렬이 되지 않으므로, array.sort((a, b) => a - b)를 사용하였다.

https://programmers.co.kr/learn/courses/30/lessons/42840

풀이 과정

1, 2, 3번째 사람의 정답의 규칙성을 배열에 담았다. 1번은 5번째마다, 2번은 8번째마다, 3번은 10번째 마다 규칙이 반복되므로, 문제 번호를 5, 8, 10으로 나눠서 문제의 정답과 배열에 들어있는 수가 일치한지 확인해서 정답 여부를 판단하였다.

파이썬에서는 max(배열)

자바스크립트에서는 Math.max(...배열)을 통해서 배열에서의 최대값을 얻어낼 수 있고, 이를 통해 가장 높은 점수를 받은 사람을 판별하였다.

소스 코드

파이썬

def solution(answers):
    answer = []
    correct = [0, 0, 0]
    people1 = [1, 2, 3, 4, 5]
    people2 = [2, 1, 2, 3, 2, 4, 2, 5]
    people3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]

    for question in range(len(answers)):
        if answers[question] == people1[question % 5]:
            correct[0] += 1
        if answers[question] == people2[question % 8]:
            correct[1] += 1
        if answers[question] == people3[question % 10]:
            correct[2] += 1

    high_score = max(correct)

    for i in range(len(correct)):
        if correct[i] == high_score:
            answer.append(i+1)

    return answer

자바스크립트

function solution(answers) {
    var answer = [];
    correct = [0, 0, 0]
    people1 = [1, 2, 3, 4, 5]
    people2 = [2, 1, 2, 3, 2, 4, 2, 5]
    people3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]

    for (var question = 0; question < answers.length; question++) {
        if (answers[question] == people1[question % 5]) {
            correct[0] += 1
        }
        if (answers[question] == people2[question % 8]) {
            correct[1] += 1
        }
        if (answers[question] == people3[question % 10]) {
            correct[2] += 1
        }
    }

    high_score = Math.max(...correct)

    for (var i = 0; i < correct.length; i++) {
        if (correct[i] == high_score) {
            answer.push(i+1)
        }
    }

    return answer;
}