1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

www.acmicpc.net

 

<내 코드>

 

n = input().split('-')
result = 0

for i in n[0].split('+'):
    result += int(i)

for j in n[1:]:
    for k in j.split('+'):
        result -= int(k)

print(result)

 

적절한 괄호를 쳐서 최솟값을 만드는 문제다. 최솟값을 만들려면 -의 값이 커야 하기에 - 사이에 +로 연결된 값들을 다 더한 후 마지막 빼주면 최솟값을 만들 수 있다. 어떤 점에서 그리디 문제인지는 감이 오지 않는 문제다...

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 2839] 설탕 배달 - Python (그리디 알고리즘)  (0) 2020.08.27
[백준 1931] 회의실 배정 - Python (그리디 알고리즘, 정렬)  (0) 2020.08.26
[백준 1932] 정수 삼각형 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 1149] RGB 거리 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 9461] 파도반 수열 - Python(다이나믹 프로그래밍)  (0) 2020.08.24

 

 

1932번: 정수 삼각형

문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최�

www.acmicpc.net

 

<내 코드>

n = int(input())
tri = [list(map(int, input().split())) for _ in range(n)]
k = 2
for i in range(1, n):
    for j in range(len(tri[i])):
        if j == 0:  # 가장 왼쪽값일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][j] + tri[i][j]
        elif j == len(tri[i])-1:    # 가장 오른쪽일 경우 현재 값이랑 바로 위랑 더함
            tri[i][j] = tri[i-1][-1] + tri[i][j]
        else:  # 양 끝값이 아닌, 중간일 경우, 대각선 왼쪽과 오른쪽 중 큰 값과 더함
            tri[i][j] = max(tri[i-1][j-1], tri[i-1][j]) + tri[i][j]
    k += 1
print(max(tri[n-1]))

 

규칙을 찾아서 재귀 형태의 점화식을 찾아내는 것이 중요했다. 삼각형의 가장 왼쪽과 오른쪽 값은 위의 값과 바로 더해주면 되고, 중간의 값들은 대각선 왼쪽과 오른쪽의 값 중 최댓값과 더해줬다. 

 

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 1931] 회의실 배정 - Python (그리디 알고리즘, 정렬)  (0) 2020.08.26
[백준 1541] 잃어버린 괄호 - Python (그리디 알고리즘)  (0) 2020.08.26
[백준 1149] RGB 거리 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 9461] 파도반 수열 - Python(다이나믹 프로그래밍)  (0) 2020.08.24
[백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍)  (0) 2020.08.23

 

 

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

 

<내 코드>

n = int(input())
costs = [0 for _ in range(n+1)]
for i in range(1, n+1):
    costs[i] = list(map(int, input().split()))

for i in range(2, n+1):
    costs[i][0] = costs[i][0] + min(costs[i-1][1], costs[i-1][2])
    costs[i][1] = costs[i][1] + min(costs[i-1][0], costs[i-1][2])
    costs[i][2] = costs[i][2] + min(costs[i-1][0], costs[i-1][1])
   
print(min(costs[n][0], costs[n][1], costs[n][2]))

처음에 생각했을 때는 맨 처음 요소에서 최솟값을 구하면 최소가 되는 줄 알았는데, 그게 아니고 어떤 값을 선택했을 때 최소가 될지는 다 따져줘야 하는 문제였다. 다른 사람의 풀이를 참고하기 전까지는 쓸데없이 어렵게 풀고 헤맸다...

 

1. 첫 요소는 고정이므로 인덱스를 2번째부터 돌리면 된다. 

2. 현재 인덱스 요소의 값과 앞 요소에서 같은 색을 제외한 2가지 중에 최소를 더해준다.

3. 같은 방식으로 마지막까지 3가지 색에 대해 계산을 한다.

4. 마지막 요소의 3가지 값 중 최솟값을 선택하면 최소 비용값을 구할 수 있다.

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 1541] 잃어버린 괄호 - Python (그리디 알고리즘)  (0) 2020.08.26
[백준 1932] 정수 삼각형 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 9461] 파도반 수열 - Python(다이나믹 프로그래밍)  (0) 2020.08.24
[백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍)  (0) 2020.08.23
[백준 2805] 나무 자르기 - Python(이분탐색)  (0) 2020.08.21

 

 

9461번: 파도반 수열

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 �

www.acmicpc.net

 

<내 코드>

n = int(input())
memo = [0 for _ in range(101)]

for i in range(0, 4):
    memo[i] = 1
for j in range(4, 6):
    memo[j] = 2

for _ in range(n):
    m = int(input())
    for k in range(6, m+1):  # 6 ~ m-1
        memo[k] = memo[k-1] + memo[k-5]

    print(memo[m])

 

피보나치 수열과 비슷한 맥락으로 규칙을 찾아 점화식을 세우면 간단하게 풀 수 있었다.

인덱스 0번 ~ 4번까지는 1과 2로 넣어주고 그 다음부터는 점화식을 통해 값을 구해나가는 구조였다. 인덱스 값을 0번째 부터 설정해서 뒤에서 조금 헷갈린거 말고는 크게 어렵지 않았다.

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 1932] 정수 삼각형 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 1149] RGB 거리 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍)  (0) 2020.08.23
[백준 2805] 나무 자르기 - Python(이분탐색)  (0) 2020.08.21
[백준 1920] 수 찾기 - Python (이분탐색)  (0) 2020.08.18

 

 

2748번: 피보나치 수 2

문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)��

www.acmicpc.net

 

<내 코드>

n = int(input())
memo = [0 for i in range(n+1)]
memo[1] = 1
for i in range(2, n+1):
    memo[i] = memo[i-1]+memo[i-2]

print(memo[-1])

처음에 재귀호출을 통해 풀었을 때, 예상대로 시간초과가 났다. 

Bottom-up은 바닥에서 올라오는 것, 즉, 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. 첫 번째 피보나치 수를 구하는 문제와 두 번째 피보나치 수를 구하는 문제를 풀면 세 번째 피보나치 수를 구하는 문제를 풀 수 있다. 두 번째 피보나치 수를 구하는 문제와 세 번째 피보나치 수를 구하는 문제를 풀면 네 번째 피보나치 수를 구하는 문제를 풀 수 있다....이걸 반복하면 n번째 피보나치 수를 구할 수 있다.

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 1149] RGB 거리 - Python (다이나믹 프로그래밍)  (0) 2020.08.24
[백준 9461] 파도반 수열 - Python(다이나믹 프로그래밍)  (0) 2020.08.24
[백준 2805] 나무 자르기 - Python(이분탐색)  (0) 2020.08.21
[백준 1920] 수 찾기 - Python (이분탐색)  (0) 2020.08.18
[백준 11866] 요세푸스 순열 - Python  (0) 2020.08.18

동적 계획법이란?

어떤 문제를 풀기 위해 그 문제를 더 작은 문제들로 나누고, 작은 문제들에서 구한 해를 어딘가에 저장한 다음 활용해 문제를 해결하는 알고리즘 설계 기법이다. DP는 이름처럼 다이내믹한 프로그래밍이라는 거리가 멀다. 단순히 붙여진 이름일 뿐이라고 한다.

 

 

 

분할 정복 방식과 차이점

DP의 문제 접근 방식은 기본적으로 '분할 정복 알고리즘(Divide and Conquer)'과 비슷하다. 두 경우 모두 문제를 부분으로 나누어 각 부분 문제의 답을 계산하고, 이 값을 이용해 원래 문제를 해결하는 과정이다. DP와 분할 정복의 차이는 부분 문제로 나누는 방식에 차이가 있다. DP는 작은 문제들이 반복적으로 사용되며 (즉, 답이 바뀌지 않음) 반대로 동적 계획법은 작은 문제가 중복이 발생하지 않고 단순히 나누어 푸는 방법이다.

 

 

DP 문제의 해결 순서

  1. 큰 문제를 작은 문제로 나눈다.

  2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다.

  3. 작은 문제의 도출 값을 메모하고, 큰 문제를 풀어나갈 때 작은 문제가 반복되면 메모한 값을 이용한다. (Memoization방식)

 

 

DP의 조건

  1. 작은 문제가 반복, 중복이 일어나는 경우

  2. 같은 문제의 값은 매번 같다.

 

여기서 반복적으로 중복이 일어난 부분이 있다. 원으로 표시한 부분만 아니라 F(4)와 F(3)을 구하기 위해 모두 F(2)를 계산해야한다. 이런 식으로 매번 다 계산을 하면 시간적으로 비효율적이다. 그래서 DP방식을 이용해 메모이제이션을 통해 값을 활용해서 문제를 해결하면 훨씬 빠른 계산이 가능해진다.

반응형
저작자표시 비영리 변경금지

'알고리즘 & 자료구조' 카테고리의 다른 글

[알고리즘] DFS, BFS  (0) 2024.10.02
[알고리즘] 그리디 알고리즘 (Greedy Algorithm)  (0) 2020.09.05
[알고리즘] 이분 탐색 - Binary Search  (0) 2020.08.18
[알고리즘] 삽입정렬  (0) 2020.08.17
[알고리즘] 재귀호출  (0) 2020.08.17

 

 

2805번: 나무 자르기

문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고,

www.acmicpc.net

 

 

<내 코드>

 

def binarySearch(M, tree):
    start = 1
    end = max(tree)

    while start <= end:
        leng = 0
        mid = (start + end) // 2

        for i in tree:
            if i >= mid:
                leng += i - mid

        if leng >= M:
            start = mid + 1
        else:
            end = mid - 1

    return end


N, M = map(int, input().split())
tree = list(map(int, input().split()))

sortTree = sorted(tree)
print(binarySearch(M, sortTree))

이분 탐색 알고리즘을 이용해서 푸는 문제다. 알고리즘만 알고 있으면 생각보다 간단한 문제였다. 같은 코드로 채점 했는데 pypy3는 588ms가 걸리고 python3는 2984ms 가 걸리면서 다소 큰 차이가 있었다. 

반응형
저작자표시 비영리 변경금지

'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글

[백준 9461] 파도반 수열 - Python(다이나믹 프로그래밍)  (0) 2020.08.24
[백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍)  (0) 2020.08.23
[백준 1920] 수 찾기 - Python (이분탐색)  (0) 2020.08.18
[백준 11866] 요세푸스 순열 - Python  (0) 2020.08.18
[백준 1966] 프린터 큐 - Python  (0) 2020.08.17

- Advice Slip API

: 세계적인 명언이나 조언들을 보여주는 API로 간단하게 웹앱을 만들어봤다. 앞전에 만든 Numbers API 사용한 것과 같은 맥락이라 크게 어려운 것 없고, 다시 한번 간단하게 공부하기 좋았다. 

 

 

Advice Slip JSON API

In the event of an error occuring, a message object is returned, containing relevant information about the request. A slip object is a simple piece of advice. A search object contains the results of a slip search query. A messages object contains informati

api.adviceslip.com

 

 

<코드>

- index.html

<body class="bg-secondary">
    <div class="container">
      <div class="row">
        <div class="col-md-6 mx-auto">
          <div class="card p-4 mt-5">
            <h1>Advice Slip</h1>
            <span>버튼을 클릭하면 랜덤 advice가 나타납니다.</span>
            <button
              class="btn btn-primary mt-3"
              style="outline: none; border: none;"
            >
              Click
            </button>
            <div class="card-body">
              <div class="mt-2" id="advice-area">
                <h3 class="card-title">Random advice</h3>
                <p class="text card-text"></p> <!--명언이 나타나는 부분-->
              </div>
            </div>
          </div>
        </div>
      </div>
    </div>
    <script src="main.js"></script>
  </body>

 

- main.js

const adviceText = document.querySelector('.text');
const btn = document.querySelector('.btn');
const adviceArea = document.getElementById('advice-area');

btn.addEventListener('click', advice);

function advice() {
  fetch("https://api.adviceslip.com/advice")
    .then(response => response.json())
    .then(data => {
      adviceArea.style.display = 'block';
      adviceText.innerHTML = data.slip.advice;
    })
    .catch(err => console.log(err));
}

 

<결과>

반응형
저작자표시 비영리 변경금지

'JavaScript' 카테고리의 다른 글

[JavaScript] Jest를 사용한 테스트 코드 짜기!  (0) 2021.07.04
[JavaScript] 객체, 배열 자료 다루기 - JSON 데이터  (0) 2020.09.24
[JavaScript] Numbers API를 이용한 프로젝트 - AJAX, Fetch  (0) 2020.08.10
[JavaScript] AJAX 란 무엇인가?  (0) 2020.07.17
[JavaScript] Event - addEventListener, 이벤트 객체  (0) 2020.05.14

+ Recent posts

티스토리툴바