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

 

코딩테스트 연습 - 같은 숫자는 싫어

배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은

programmers.co.kr


풀이 과정

리스트에서 연속적으로 나오는 숫자를 제거한 리스트를 반환해주면 된다. 파이썬의 리스트에서 중복을 제거하는 방법은 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

 

코딩테스트 연습 - [1차] 비밀지도

비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다

programmers.co.kr


풀이 과정

파이썬의 내장함수 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

 

코딩테스트 연습 - 부족한 금액 계산하기

새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이

programmers.co.kr


풀이 과정

탑승시 필요한 금액 = 기본 금액 * 탑승 횟수 임을 생각하면서 탑승 횟수에 따른 필요 금액의 누적 합과 보유 금액을 비교해주고 모자란 금액을 출력하거나 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

 

코딩테스트 연습 - 나머지가 1이 되는 수 찾기

자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다. 제한사항 입

programmers.co.kr


풀이 과정

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

 

코딩테스트 연습 - 최소직사각형

[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133

programmers.co.kr


풀이 과정

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

 

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

 

코딩테스트 연습 - 2016년

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까

programmers.co.kr


풀이 과정

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 

 

코딩테스트 연습 - 두 개 뽑아서 더하기

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한

programmers.co.kr


풀이 과정

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/

 

코딩테스트 연습 - 예산

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는

programmers.co.kr


풀이 과정

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

 

그리디 방식으로 가장 작은 예산을 제출한 부서부터 결제해주면서 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

 

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

www.acmicpc.net


풀이 과정

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

 

2133번: 타일 채우기

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

www.acmicpc.net


풀이 과정

 

https://greentea31.tistory.com/26

 

백준 11726 - 2xn 타일링 [파이썬]

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지..

greentea31.tistory.com

 

 

위와 비슷하게 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])

+ Recent posts