백준38 6. Array(배열) - Quick Select 1. Quick Select란? - 정렬되지 않은 배열에서 N번째로 크거나 작은 수를 찾을 때 사용되는 알고리즘 - N번째 수를 찾기 위해서는 다음과 같은 방법을 사용할 수 있다. 1) 전체 요소를 오름차순으로 정렬한 후, N번째 수를 찾는 방법 - O(N log N)의 시간복잡도 2) Heap 정렬 - O(n log k)의 시간복잡도 - 1)의 방법보다 빠르다. 3) Quick Select - O(n)의 시간복잡도 - 가장 빠른 방법이다. - 이 중에서 가장 빠른 Quick Select에 대해서 알아보자. 2. Quick Select 개념 - Quick Select는 Partitioning(파티셔닝)을 이용한 알고리즘이다. ▶ Partitioning 이란? - Pivot 이라는 하나의 숫자를 기준으로 .. 2021. 9. 2. 백준 2750 파이썬 - 수 정렬하기(선택정렬) 1. 문제 링크 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 나는 어떻게 생각했는가? # 백준 단계별 풀이 12단계 - 수 정렬하기 # https://www.acmicpc.net/problem/2750 # 선택정렬을 사용해서 풀어보자. from typing import List from sys import stdin input = stdin.readline def selection_sort(case: List[int]) -> List[int]:.. 2021. 8. 24. 백준 2750 파이썬 - 수 정렬하기(삽입정렬) 1. 문제 링크 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 나는 어떻게 생각했는가? # 삽입정렬을 사용해서 풀어보자. from typing import List from sys import setprofile, stdin input = stdin.readline def insertion_sort(case: List[int]) -> List[int]: for idx in range(1, len(case)): current = case[idx] .. 2021. 8. 24. 파이썬 - 알고리즘 Tips(8/23 업데이트) - 본 포스팅은 알고리즘 문제를 풀면서 배우게 된 Tip을 정리한 포스팅입니다. - 일종의 오답노트이며, 최근순으로 정리됩니다. 9. 함수의 매개변수 타입을 지정하는 방법 - 만약 어떤 함수를 작성할 때, 매개변수를 지정하고 싶다면 어떻게 할까? - 아래의 예시 코드를 우선 살펴보자. from typing import List def bubble_sort(List[int]) -> List[int]: #함수내용작성 - 위의 코드는 다음과 같은 방식으로 구조를 갖는다. def 함수명(매개변수명: 자료형) -> 반환자료형: #함수내용작성부 - 매개변수 다음 콜론을 적는다. - 콜론 다음에 매개변수의 자료형을 적는다. - 화살표 기호 다음에 작성되는 자료형은 해당 매개변수를 return 할 때 적용할 자료형을 .. 2021. 8. 23. 백준 2750 파이썬 - 수 정렬하기(버블정렬) 1. 문제 링크 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 2. 나는 어떻게 생각했는가? - 이번 문제는 사실 간단한 풀이가 존재한다. - 하지만 풀기 간단한 만큼 버블정렬을 연습하기 좋은 문제다. - 버블정렬을 사용한다면, 다음과 같이 풀 수 있다. from typing import List from sys import stdin input = stdin.readline def bubble_sort (case: List[int]) -> List[.. 2021. 8. 23. 백준 11729 파이썬 - 하노이 탑 이동 순서 1. 문제 링크 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 2. 나는 어떻게 생각했는가? - 문제도 이해했고, 손으로 직접 그려가면서 풀이도 해보았다. - 그러나 규칙성을 찾고, 규칙을 코드로 구현하는 능력이 많이 부족하다는 것을 다시한번 깨닫게 하였다. - 사실 해답코드를 읽고도, 저런 규칙성으로 이 문제가 풀린다는 것이 완벽하게 이해가 가지 않는다. 3. 정답 코드 n = int(input()) def hanoi(n, st.. 2021. 8. 17. 백준 2447 파이썬 - 별 찍기 10 1. 문제 링크 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 2. 나는 어떻게 생각했는가? - 문제는 이해했지만, 풀이가 잘 이해가 안간다. - 수학적 사고력이 많이 부족하다는 것을 느끼게하는 문제 - 지금 당장 이해가 안가는 문제를 붙잡고 있으려니, 시간이 아깝다고 생각해서 패스한다. 3. 정답 코드 def draw_star(n) : global Map if n == 3 : Map[0][:3] = Map[2][:.. 2021. 8. 17. 백준 10870 파이썬 - 피보나치 5 1. 문제 링크 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 2. 나는 어떻게 생각했는가? def fibonacci(n): if n 2021. 8. 17. 백준 10872 파이썬 - 팩토리얼 1. 문제 링크 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 2. 나는 어떻게 생각했는가? def factorial(n): result = 1 while n > 0: result *= n n -= 1 factorial(n) return result n = int(input()) print(factorial(n)) - 내가 작성한 코드는 재귀적이다 라는 느낌이 없다. - 재귀적이기 보다는 콜백의 느낌이 가까운 것 같다. 3. 정답 코드 def factorial(n): if n == 0: return 1 else: return n * factori.. 2021. 8. 17. 이전 1 2 3 4 5 다음
