greentea31's Note

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;
}

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

소스 코드

파이썬

def solution(participant, completion):
    answer = ''
    dictionary = {}
    for name in participant:
        if name not in dictionary: # 딕셔너리에 없는데 if dictionary[name]으로 조건문 주면 오류 남
            dictionary[name] = 1
        else:
            dictionary[name] += 1

    for name in completion:
        dictionary[name] -= 1

    for name in dictionary:
        if dictionary[name] != 0:
            answer = name

    return answer

자바스크립트

function solution(participant, completion) {
    var answer = '';
    var dictionary = {}

    for (name of participant) { // 배열의 값 for of로 순회
        if (dictionary[name] >= 0) { // dictionary[name]이 이미 존재한다면
            dictionary[name] += 1
        } else {
            dictionary[name] = 1
        }
    }

    for (name of completion) {
        dictionary[name] -= 1
    }

    for (name in dictionary) { // 딕셔너리의 key 값 for in으로 순회
        if (dictionary[name] != 0) {
            answer = name
            break
        }
    }

    return answer;
}

풀이 과정

{참가자 이름 : 해당 이름으로 미완주한 사람의 수} 딕셔너리를 활용해서 문제를 해결하였다.

completion 배열로 딕셔너리를 순회하며 해당 이름으로 미완주한 사람의 수를 1씩 줄여주고, 다시 딕셔너리를 순회하면서 해당 이름으로 미완주한 사람의 수가 1명 이상이면 그 사람의 이름을 정답으로 출력하면 된다.

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

풀이 과정

에라토스테네스의 체를 이용하여 3000이하의 수에 대해 소수판정을 한 뒤, 배열에서 3개의 수를 뽑는 모든 수에 대해 합이 소수인지 판정하여 answer 값을 1 추가할지 말지 결정하였다.

에라토스테네스의 체

특정 수 n이하의 모든 소수를 구할 때 사용하는 방법이다.

check = [False for _ in range(3001)]

for i in range(2, 3001):
    if check[i] == False:
        for j in range(2*i, 3001, i):
            check[j] = True

check 배열을 하나 선언해두고

1. 2는 체크되지 않았으니 소수 => 2의 배수는 전부 2로 나누어지므로 소수가 아니니 True로 체크해준다

2. 3은 체크되지 않았으니 소수 => 3의 배수는 전부 3으로 나누어지므로 소수가 아니니 True로 체크해준다

3. 4는 체크되었으니 소수가 아님

4. 5는 체크되지 않았으니 소수 => 5의 배수는 전부 5로 나누어지므로 소수가 아니니 True로 체크해준다

...

위와 같은 방법을 이용하여 3000까지의 모든 자연수에 대해 소수 판정을 했다. 

소스 코드

파이썬

check = [False for _ in range(3001)]

for i in range(2, 3001):
    if check[i] == False:
        for j in range(2*i, 3001, i):
            check[j] = True


def solution(nums):
    answer = 0

    for i in range(len(nums) - 2):
        for j in range(i+1, len(nums) - 1):
            for k in range(j+1, len(nums)):
                if not check[nums[i] + nums[j] + nums[k]]:
                    answer += 1

    return answer

자바스크립트

function solution(nums) {
    var check = []
    let answer = 0
    for (var i = 0; i < 3001; i++) {
        check.push(false)
    }

    for (var i = 2; i < 3001; i++) {
        if (check[i] === false) {
            for (var j = 2 * i; j < 3001; j += i) {
                check[j] = true
            }
        }
    }

    for (var i = 0; i < nums.length - 2; i++) {
        for (var j = i+1; j < nums.length - 1; j++) {
            for (var k = j+1; k < nums.length; k++) {
                if (!check[nums[i] + nums[j] + nums[k]]) {
                    answer += 1
                }
            }
        }
    }

    return answer;
}