greentea31's Note

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

풀이 과정

리스트에서 연속적으로 나오는 숫자를 제거한 리스트를 반환해주면 된다. 파이썬의 리스트에서 중복을 제거하는 방법은 list를 set 자료형으로 바꿨다가 다시 list로 바꾸는 방법이 널리 알려져 있지만, 이러면 list의 순서가 보존되지 않으므로 다른 방법을 이용해야 한다.

list내의 숫자를 하나하나씩 살펴보면서 이전에 살펴봤던 숫자와 같은 숫자이면 정답 list에 넣지 않고, 다른 숫자이면 정답 list에 넣는 방식으로 문제를 해결하였다.

소스 코드

def solution(arr):
    answer = []
    check = -1
    for number in arr:
        if check != number:
            answer.append(number)
            check = number
    return answer

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

풀이 과정

파이썬의 내장함수 bin()을 이용해서 십진수 숫자를 이진수 문자열로 바꿔주었다

ex) bin(9) -> '0b1001'

      bin(9)[2:] -> '1001'

지도의 한 변의 길이가 n이어야 하므로 문자열의 길이가 n 미만이면 문자열의 맨 앞에 0을 추가로 붙여준다

ex) '1001' -> '01001' (n = 5)

첫 째 지도, 둘 째 지도에서 위와 같은 방법으로 십진수를 이진수로 전환해주고, 양쪽 지도를 모두 살펴보면서 양쪽 지도 모두가 0이면 실제 지도에는 공백, 하나라도 1이면 실제 지도에는 '#'을 채워주면서 지도를 완성하고 출력해주면 된다.

소스 코드

def solution(n, arr1, arr2):
    answer = []
    arr1map = []
    arr2map = []

    for number in arr1:
        temp = bin(number)[2:]
        while len(temp) < n:
            temp = '0' + temp
        arr1map.append(temp)

    for number in arr2:
        temp = bin(number)[2:]
        while len(temp) < n:
            temp = '0' + temp
        arr2map.append(temp)

    for outer in range(n):
        temp_answer = []
        for inner in range(n):
            if arr1map[outer][inner] == '0' and arr2map[outer][inner] == '0':
                temp_answer.append(' ')
            else:
                temp_answer.append('#')
        answer.append(temp_answer)

    answer2 = []

    for array in answer:
        answer2.append(''.join(array))


    return answer2

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

풀이 과정

탑승시 필요한 금액 = 기본 금액 * 탑승 횟수 임을 생각하면서 탑승 횟수에 따른 필요 금액의 누적 합과 보유 금액을 비교해주고 모자란 금액을 출력하거나 0을 출력해주면 된다.

소스 코드

def solution(price, money, count):
    answer = 0
    need_money = 0
    for ride_count in range(1, count+1):
        need_money += price * ride_count
    if need_money > money:
        answer = need_money - money
    return answer

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

풀이 과정

n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 구하시오

1. n을 2부터 n-1까지 나눠보면서 나머지가 1이 될 때의 값을 출력해주면 된다.

2. n-1의 약수중 가장 작은 값을 출력해주면 된다. n-1이 소수이면 n-1을 출력해야 한다.

문제를 읽고 위의 2가지 방법이 떠올랐고 2번째 방법으로 문제를 해결하였다. 어떤 수 n의 약수를 구하려면 n을 2부터 rootn까지 나눠보고 나누어 떨어지면 약수라고 판정하면 된다.

소스 코드

def solution(n):
    n -= 1
    answer = n
    for i in range(2, int(n**(1/2)) + 2):
        if n % i == 0:
            answer = i
            break;
    return answer

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

풀이 과정

모든 명함을 담을 수 있는 가장 작은 지갑을 만들어야 하는데 명함은 회전해서 담을 수 있다.

4개의 명함이 있다고 하면 1 2 3 4, 12 13 14 23 24 34, 123 124 134 234, 1234 번째 명함을 회전시켜본 뒤 넓이를 구하고 가장 작은 값을 답으로 내는 방법을 떠올려봤지만 sizes의 길이가 10,000까지 들어오므로 이건 너무 시간이 오래 걸린다.

명함은 회전해서 담을 수 있으므로 가로, 세로 길이는 중요하지 않다. 긴 쪽의 길이와 짧은 쪽의 길이를 한 곳에 몰아넣은 다음, 긴 쪽의 길이 중에서 가장 큰 값 * 짧은 쪽의 길이 중에서 가장 큰 값을 해주면 답이 도출할 수 있다. 또한 이렇게 풀면 O(N)의 시간복잡도로 문제를 해결할 수 있다.

소스 코드

def solution(sizes):
    max_width, max_height = 0, 0
    for a, b in sizes:
        if a > b:
            a, b = b, a
        max_width = max(max_width, a)
        max_height = max(max_height, b)
    answer = max_width * max_height
    return answer

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

풀이 과정

1월 1일과 a월 b일이 몇 일 차이가 나는지 계산 후 나머지 연산을 통해 어떤 요일인지 출력해주면 된다. 각 월의 일수와 요일을 리스트에 저장하여 문제를 해결하였다.

소스 코드

def solution(a, b):
    wol = [0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    week = ["FRI", "SAT", "SUN", "MON", "TUE", "WED", "THU"]

    answer = b - 1
    subwol = a - 1

    for i in range(subwol + 1):
        answer += wol[i]

    answer %= 7
    answer = week[answer]

    return answer

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

풀이 과정

2중 for문으로 list를 순회하면서 리스트의 요소를 2개 더한 값들을 answer에 저장해주자. 만약 a라는 배열이 3개의 원소를 가지고 있다면

a[0] + a[1], a[0] + a[2], a[1] + a[2]를 다 answer에 더해주는 방식이다.

파이썬에서 set 자료형은 중복을 허용하지 않으므로 answer를 set 자료형으로 바꿔줘서 중복을 없앤 후, 다시 list 자료형으로 바꿔주고 sort() 메써드를 활용해서 오름차순으로 정렬하고 출력해주면 된다.

소스 코드

def solution(numbers):
    answer = []

    for number in range(len(numbers)):
        for number2 in range(number+1, len(numbers)):
            answer.append(numbers[number] + numbers[number2])

    answer = set(answer)
    answer = list(answer)
    answer.sort()
    return answer

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

풀이 과정

최대한 많은 부서의 물품을 구매해 주려면 가장 적은 예산을 제출한 부서부터 결제해주면 된다.

그리디 방식으로 가장 작은 예산을 제출한 부서부터 결제해주면서 budget값을 체크해주고 answer를 늘려나가자.

소스 코드

def solution(d, budget):
    answer = 0
    d.sort()
    for department in d:
        if budget - department >= 0:
            answer += 1
            budget -= department
        else:
            break

    return answer

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

풀이 과정

9명중에 진짜 난쟁이를 7명 찾아야 하고 7명의 키의 합이 100이라 한다.

-> 모든 난쟁이의 키의 합을 구하고 9명중에 2명의 난쟁이의 키의 합을 뺐을 때 100이 나오면 그 2명은 진짜 난쟁이가 아니다

루프 2번 돌면서 9명중에 2명의 난쟁이를 고르는 수인 36번 돌다 보면 가짜 난쟁이 2명이 걸러진다 브루트 포스 방법으로 2명 뺐을 때 키의 합이 100이 나올때까지 다 찾아보면 된다.

키의 합을 구하는 연산 O(N), 가짜 난쟁이 2명을 찾는 연산 O(N^2)으로 총 O(N^3)의 시간복잡도를 갖고, N이 9이므로 그냥 다 해봐도 시간제한 내로 문제를 해결하는데 문제가 없다.

소스 코드

import sys
height = []

for i in range(9):
    height.append(int(sys.stdin.readline()))

height.sort()

sumHeight = sum(height)

fake1 = 0
fake2 = 0

for i in range(8):
    for j in range(i+1, 9):
        if sumHeight - height[i] - height[j] == 100:
            fake1 = i
            fake2 = j

for i in range(9):
    if i != fake1 and i != fake2:
        print(height[i])

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

풀이 과정

https://greentea31.tistory.com/26

위와 비슷하게 DP로 풀기 위해 점화식을 세워서 문제를 해결할 수 있다.

문제를 보고 생각을 하다보면 3x2 블록을 채우는 경우의 수는 3개가 있으니 3x4는 3x2 블록 2개 붙이면 되겠고... 이런 생각이 들겠지만 밑에 힌트를 보면 3x2 블록 채우는 경우의 수를 2개 조합한게 아닌 3x4 블록을 채우는 방법이 존재함을 알게 된다.

3xi 에서 i가 2씩 늘어날 수록 기존의 방법의 조합이 아닌 새로운 방법이 2개씩 더 추가된다.

따라서 d[i]를 3xi 블록을 채우는 방법의 경우의 수라고 하면

d[i] = 3 * d[i-2] + 2 * d[i-4] + 2 * d[i-6] + ... + 2 * d[0]이 성립한다.

d[0]은 1로 초기값을 설정해놔야 정답을 얻을 수 있다.

소스 코드

import sys

N = int(sys.stdin.readline())
d = [1, 0, 3, 0, 11]
for i in range(5, 31):
    d.append(3*d[i-2])
    for j in range(4, i+1, 2):
        d[i] += 2*d[i-j]

print(d[N])