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

 이분 탐색 알고리즘 - 파이썬

 

이분 탐색은 값을 비교할 때마다 찾는 값이 있을 범위를 절반씩 좁히면서 탐색하는 효율적인 알고리즘이다. 이분 탐색에서 중요한 것은 '이미 정렬된 데이터'에서 값을 비교하면 찾는다는 것이다. 따라서 순차 탐색처럼 처음부터 하나씩 하는 것이 아니라 정렬된 데이터에서 기준점을 잡고 반으로 줄여나가며 찾는 것이기에 훨씬 효율적이고 빠른 알고리즘이다.

 

이분 탐색은 실생활에서 '책'을 떠올리면 쉽게 이해할 수 있다. 우리는 책을 이용해 원하는 것을 찾을 때 첫 페이지부터 찾는 것이 아니라, 중간쯤 쪽수를 찾아 펼친 다음 범위를 좁혀나가며 계속 찾아나간다. 원하는 페이지가 펼친 페이지보다 뒤에 있다면 앞쪽은 찾을 필요 없이 바로 뒤쪽부터 찾게 된다.

 

 

예제

def binary_search(a, x):
    start = 0
    end = len(a)-1

    while start <= end:
        mid = (start + end) // 2
        if(x == a[mid]): 	# 원하는 값 발견!
            return mid 
        elif (x > a[mid]): 	# 찾는 값이 더 크면, 오른쪽으로 범위를 좁혀 탐색
            start = mid + 1
        else:			# 찾는 값이 더 작으면, 왼쪽으로 범위를 좁혀 탐색
            end = mid - 1
            
    return -1			# 찾지 못했을 때

a = [1, 4, 9, 25, 36, 49] # 정렬된 자료
print(binary_search(a, 36)) # 5
print(binary_search(a, 12)) # -1

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[알고리즘] 그리디 알고리즘 (Greedy Algorithm)  (0) 2020.09.05
[알고리즘] 동적 계획법 - Dynamic Programming  (0) 2020.08.23
[알고리즘] 삽입정렬  (0) 2020.08.17
[알고리즘] 재귀호출  (0) 2020.08.17
[알고리즘] 선택 정렬  (0) 2020.07.19

 

 

1920번: 수 찾기

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안��

www.acmicpc.net

 

<내 코드>

n = int(input())
A_num = list(map(int, input().split()))
sorted_A = sorted(A_num)

m = int(input())
M_num = list(map(int, input().split()))


def binary_search(M, sorted_A):
    start = 0
    end = len(sorted_A)-1

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

        if(m == sorted_A[mid]):
            return print(1)
        elif (m > sorted_A[mid]):
            start = mid + 1
        else:
            end = mid - 1
    return print(0)


for m in M_num:
    binary_search(m, sorted_A)

 

이분 탐색 알고리즘 문제다. 이분 탐색은 미리 정렬된 리스트에서 값을 찾아나가는 알고리즘이다. 정렬된 자료에서 중앙값을 찾은 다음 찾으려는 값과 비교한다. 중앙값이 더 크면 찾으려는 값이 오른쪽에 있는 것이기에 오른쪽으로 범위를 좁히고, 중앙값이 더 작다면 왼쪽으로 범위를 좁혀 찾아나간다. 비교하는 값이 존재한다면 1을 프린트하고, 없다면 0을 프린트한다.

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[백준 2748] 피보나치 수 - Python(다이내믹 프로그래밍)  (0) 2020.08.23
[백준 2805] 나무 자르기 - Python(이분탐색)  (0) 2020.08.21
[백준 11866] 요세푸스 순열 - Python  (0) 2020.08.18
[백준 1966] 프린터 큐 - Python  (0) 2020.08.17
[백준 2164] 카드 2 - Python  (0) 2020.07.25

 

 

11866번: 요세푸스 문제 0

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

www.acmicpc.net

 

 

<내 코드>

n, k = map(int, input().split())
people = [i for i in range(1, n+1)]
key = 0
temp = k - 1
order = []
while people:
    key = (key+temp) % len(people)
    order.append(people.pop(key))

print('<'+', '.join(map(str, order))+'>')

 

순열 규칙을 찾으면 간단하게 해결되는 문제였다. 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[백준 2805] 나무 자르기 - Python(이분탐색)  (0) 2020.08.21
[백준 1920] 수 찾기 - Python (이분탐색)  (0) 2020.08.18
[백준 1966] 프린터 큐 - Python  (0) 2020.08.17
[백준 2164] 카드 2 - Python  (0) 2020.07.25
[백준 18258] 큐 2 - Python  (0) 2020.07.25

 

Python Code

def insert_sort(x):
    for i in range(1, len(x)):
        j = i - 1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1] = x[j]  # 비교 값을 오른쪽으로 이동
            j = j - 1 # 앞쪽 값을 비교하기 위해 -1
        x[j+1] = key
    return x

 

삽입 정렬은 현재 값을 기준으로 앞쪽의 값들과 비교해 자기 자리에 삽입하는 정렬 알고리즘이다. 

삽입 정렬의 구체적인 알고리즘은 다음과 같다.

 

- 삽입 정렬은 두 번째 자료부터 알고리즘을 수행한다.

- 두 번째 자료(인덱스)부터 시작해 그 앞쪽의 값들과 비교해 삽입될 자리를 찾는다.

- 자리를 찾은 후 현재 값을 넣은 다음 나머지 값들은 한 칸씩 이동시킨다.(오른쪽)

- 세 번째 자료가 현재 값이 되고, 앞쪽 값인 첫 번째, 두 번째 값과 비교해 자리를 찾는다.

- 자리를 찾아 삽입되고 다른 값들은 옆으로 이동시킨다.

- 네 번째 값도 마찬가지로 왼쪽의 값들(1,2,3번째 값)과 비교해 삽입될 자리를 찾는다.

- 나머지 값들도 같은 방식으로 알고리즘이 수행된다.

 

 

위의 코드에서 보면 key가 선택된 값이 되고 j 인덱스가 왼쪽의 비교하는 값들이 된다.

j 번째 비교 값과 key 값을 비교했을 때 key가 작다면 j 번 값을 +1(즉 오른쪽으로 하나씩 이동) 시킨다. 계속 앞쪽의 값들과 비교해 비교 값들을 한 칸씩 오른쪽으로 이동시킨다.

만약 key 값이 더 크거나, 젤 앞의 값까지 비교가 끝나면 그 자리에 현재 값(key)을 넣어준다. 

 

 

삽입 정렬의 시간 복잡도

 

- 두 번째 값으로 시작 시 첫 번째 값과 비교 -- 1번

- 세 번째 값은 첫 번째, 두 번째랑 비교 -- 2번

- n-1 번째 값은 1, 2, 3,... , n-2 번째 비교 -- (n-2)번

- n 번째 값은 -- (n-1)번

 

즉, 1 + 2 + 3 + ... + n-2 + n-1 = n(n-1) /2 가 돼서, 시간 복잡도가 최악의 경우 O(n^2)가 된다. 최선의 경우는 자료가 다 정렬된 경우이고 이때는 시간 복잡도가 O(n)이 된다. 왜냐하면 각 자리의 값마다 왼쪽의 값 하나만 비교하면 되기 때문이다. 따라서 삽입 정렬은 n값이 커질수록 복잡도가 커져 알고리즘 성능이 떨어진다.

 

 

출처:위키피디아

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[알고리즘] 동적 계획법 - Dynamic Programming  (0) 2020.08.23
[알고리즘] 이분 탐색 - Binary Search  (0) 2020.08.18
[알고리즘] 재귀호출  (0) 2020.08.17
[알고리즘] 선택 정렬  (0) 2020.07.19
[알고리즘] 순차탐색(선형탐색)  (0) 2020.07.19

 

 

1966번: 프린터 큐

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료��

www.acmicpc.net

 

<내 코드>

case = int(input())
for _ in range(case):
	# n : 자료 개수 , m : 찾고자 하는 자료 위치
    n, m = map(int, input().split())
    imp = list(map(int, input().split()))
    temp = [0 for _ in range(n)] #리스트 표현식으로 0인 리스트 생성
    temp[m] = 1 # 찾고자 하는 m번째를 1로 표시
    cnt = 0

    while imp:
        if imp[0] == max(imp):
            cnt += 1
            if temp[0] == 1:
                print(cnt)
                break
            else:
                imp.pop(0)
                temp.pop(0)
        else:
            imp.append(imp[0])
            temp.append(temp[0])
            del(imp[0])
            del(temp[0])

 

- 중요도를 표시하는 imp 입력을 리스트로 만든다.

- imp 리스트와 비교하기 위한 temp 리스트를 만든다.

- imp[0]이 젤 큰 값인지 판단해, 아니라면 imp, temp 첫 요소를 뒤로 보내고 한 칸씩 땡긴다.

- imp[0]이 최댓값이면서 찾고자 하는 값이면 cnt 값을 출력하고 종료한다. 만약 찾고자 하는 값이 아니면 지우고 한 칸씩 땡긴다.

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[백준 1920] 수 찾기 - Python (이분탐색)  (0) 2020.08.18
[백준 11866] 요세푸스 순열 - Python  (0) 2020.08.18
[백준 2164] 카드 2 - Python  (0) 2020.07.25
[백준 18258] 큐 2 - Python  (0) 2020.07.25
[백준 1874] 스택 수열 - Python  (0) 2020.07.24

재귀 호출은 함수가 자기 자신을 다시 호출하는 것을 뜻한다. 알고리즘 공부에 있어서 중요한 개념이므로 확실하게 공부해야 한다. 재귀 호출에서 중요한 것이 반드시 '종료 조건'이 있어야 한다는 것이다. 만약 종료 조건이 없으면 무한루프에 빠지기 때문이다.

 

재귀 호출의 일반적인 형태

def func(입력):
	if 입력 값이 충분히 작으면: #종료 조건
    	return 결과
    ...
    func(더 작은 입력 값)  	# 더 작은 값으로 재귀 호출
    ...
    return 결과

 

재귀 호출의 세 가지 요건

  1. 함수 안에서 자기 자신을 다시 호출한다.
  2. 재귀 호출할 때 인자로 주어지는 입력 크기가 작아진다.
  3. 특정 종료 조건이 만족되면 재귀 호출을 종료한다. 즉, 종료 조건이 있어야 한다.

 

[예 제]

1. 1부터 n까지 더하기

def call_sum(n):
    if n <= 1:
        return n

    return n + call_sum(n-1)


print(call_sum(100))

함수 안에서 자기 자신을 계속해서 호출하는 방식으로 1부터 n까지 합을 구한다. 

 

 

2. 팩토리얼 구하기

def fact(n):
    if (n <= 1):
        return 1

    return n * fact(n-1)


print(fact(1))  # 1
print(fact(10))  # 10! = 3628800

종료 조건으로 n이 1과 같거나 작아지면 1을 리턴하게 해 마지막으로 1이 곱해지면서 결과를 리턴한다.

 

 

3. 최댓값 찾기

def find_max(nums, n):
    if n == 1:
        return nums[0]

    max_num = find_max(nums, n-1)

    if (max_num > nums[n-1]):
        return max_num
    else:
        return nums[n-1]


a = [17, 92, 18, 24, 35]
print(find_max(a, len(a)))  # 92

사실 리스트에서 최댓값, 최솟값을 구할 때 max(), min() 함수를 사용하면 쉽게 구할 수 있다.

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[알고리즘] 동적 계획법 - Dynamic Programming  (0) 2020.08.23
[알고리즘] 이분 탐색 - Binary Search  (0) 2020.08.18
[알고리즘] 삽입정렬  (0) 2020.08.17
[알고리즘] 선택 정렬  (0) 2020.07.19
[알고리즘] 순차탐색(선형탐색)  (0) 2020.07.19

+ Recent posts

티스토리툴바