본문 바로가기

Algorithm120

백준 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.
4. Array(배열) - Selection Sort(선택정렬) 1. Selection Sort란? - 가장 왼쪽의 수(index 0)을 기준으로 최소값을 찾아 swap하여 정렬하는 알고리즘 - 한번 탐색을 할 때마다, 기준 index값이 1씩 증가한다. a) 예제를 통한 선택정렬의 이해 2. 선택정렬의 시간복잡도 - 선택정렬은 버블정렬과 삽입정렬과 동일한 O(n^2)의 시간복잡도를 갖는다. 3. Selection Sort의 안정성 - 선택정렬은 불안정(unstable)한 알고리즘이다. 4. Selection Sort 직접 구현해보기 - 선택정렬의 개념을 배웠으니, 직접 코드로 구현해보자. from typing import List def selection_sort(case: List[int]) -> List[int]: for idx in range(1, len(ca.. 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.
3. Array(배열) - Insertion Sort(삽입정렬) 1. Insertion Sort란? - 삽입 정렬은 버블정렬과 동일하게 O(n^2)의 시간복잡도를 갖는 정렬 알고리즘이다. - 조건에 맞는 적절한 곳에 배열의 요소를 삽입하여 정렬하는 방법이다. a) 예제를 통한 삽입정렬의 이해 b) 삽입정렬의 시간복잡도 → O(n^2) c) 삽입정렬의 안정성(Stability) - 삽입 정렬은 안정적인 알고리즘이다. - 아래의 코드구현 예시를 통해 살펴보자. d) 삽입정렬 구현하기 from typing import List def insertion_sort(case: List[int]) -> List[int]: for idx in range(1, len(case)): current = case[idx] # 기준 값과 비교될 요소 flag = idx - 1 # 기준 값의.. 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.
2. Array(배열) - Bubble Sort(버블정렬) 1. 버블정렬 - 가장 직관적이지만, 사용을 추천하지 않는 정렬 알고리즘 a) 버블이란? - 배열의 2개 요소를 묶은 단위를 의미한다. b) 버블 스왑(swap)이란? - 버블로 묶인 배열 요소 2개의 index 값을 서로 바꾸는 것을 말한다. array[1], array[2] = array[2], array[1] 2. 버블정렬의 동작방식 - 버블정렬은 배열의 요소를 정리하는 정렬 알고리즘 중 하나다. - 배열의 요소를 2개씩 비교해서, 서로의 위치(index)를 교환(swap)하여 정리하는 방식이다. a) 예제를 통한 버블정렬의 이해 - 위의 예제는 오름차순으로 배열의 요소를 정리하는 버블정렬이다. - 요소 2개씩 비교를 진행한다. - 요소의 크기를 비교하여 작은 수를 앞으로, 큰수를 뒤로 가도록 위치.. 2021. 8. 21.
1. Array(배열) - 기본 개념 1. Array(배열) - 배열은 가장 기본적이면서, 많이 사용되는 자료구조다. a) 배열의 형태 - 배열은 동일한 자료형을 가진 데이터의 연속적인 나열로 이루어져 있다. - 배열의 요소는 연속적인 메모리 주소를 할당받는다. - 배열은 index를 사용하여 해당 요소의 메모리에 직접 접근이 가능하다. b) 배열은 정렬(Sorting)과 이어진다. - 정렬에는 다양한 알고리즘이 있는데, 배열을 효율적으로 사용하기 위함이다. - 대부분의 정렬 알고리즘은 O(n log n)의 시간복잡도를 갖는다. - 정렬 알고리즘은 안정적(stable)인가, 불안정적(unstable)인가로 분류된다. c) 배열은 탐색(Search)과 이어진다. - 배열을 이용한 알고리즘 문제를 풀다보면, 배열의 특정 요소를 찾는 경우가 있다.. 2021. 8. 20.
백준 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.

티스토리툴바