본문 바로가기

파이썬 관련 문법15

파이썬 코딩 테스트를 위한 시간 복잡도 이해하기 코딩 테스트를 공부하다 보면 시간 복잡도라는 말이 자주 나오는데요. 파이썬의 시간 복잡도는 알고리즘이나 프로그램의 실행 시간을 분석하는 중요한 개념입니다. 하지만 저희가 궁금한 건 시간 복잡도를 분석하는 방법이기에 다른 건 생략하겠습니다. 시간 복잡도 분석 방법파이썬에서 시간 복잡도를 분석하는 방법에는 여러 가지가 있습니다.이론적 분석: 알고리즘의 구조를 분석하여 Big O 표기법으로 복잡도를 표현하는 방법입니다.실험적 분석: 말 그대로 다양한 입력 크기를 주고 그에 따른 실행 시간을 측정하고 그래프로 표현하는 방법입니다.코드 프로파일링: 파이썬의 내장 도구를 사용하여 코드의 실행 시간을 측정하는 방법입니다. 일반적으로 자주 사용할 분석 방법은 Big O 표기법 입니다. O(1): 상수 시간상수 시간 복.. 2024. 12. 9.
선택 정렬(Selection Sort)이란 무엇인가? 선택 정렬은 데이터를 정렬하기 위한 간단하고 직관적인 알고리즘이며, 입력 배열을 정렬된 부분과 정렬되지 않은 부분의 두 부분으로 나누어 작동합니다.  작동 방식을 알아보겠습니다.최솟값(또는 최댓값) 찾기정렬되지 않은 부분에서 가장 작은(혹은 가장 큰) 요소를 찾습니다.교체찾은 최솟값(혹은 최댓값)을 정렬되지 않은 부분의 첫 번째 요소와 교체합니다.경계 이동정렬된 부분의 경계를 오른쪽으로 한 위치 이동합니다.반복배열이 완전히 정렬될 때까지 1~3단계를 반복합니다. 예를 들어, 배열 [7, 5, 6, 4, 9, 2]를 오름차순으로 정렬하는 경우:첫 번째 반복: 최솟값 2를 찾고, 첫 번째 요소 7과 교체합니다. → [2, 5, 6, 4, 9, 7]두 번째 반복: 최소값 4를 찾고, 두 번째 요소 5와 교체합.. 2024. 12. 9.
sys.stdin.readline()으로 입력 속도 높이기: 개행문자 처리부터 주의사항까지 코딩 테스트 문제를 풀다 보면import sysinput = sys.stdin.readline이런 코드를 작성해서 input을 재정의 하는 일이 종종 발생합니다.  왜 input을 다시 정의하는 걸까요?사실 이런 코드는 알고리즘 문제 풀이에서 시간 초과를 피하기 위해 자주 사용됩니다. sys.stdin.readline()이 input() 함수보다 훨씬 빠르며 대량의 데이터를 입력받을 때 특히 유용하기 때문입니다.    하지만, 주의사항도 있습니다. input() 함수를 재정의 하는 만큼 달라지는 점이 존재하는데요. sys.stdin.readline()은 사용자가 입력한 그대로의 데이터를 읽는 반면, input() 함수는 자동으로 개행문자를 제거합니다.    여기서 개행문자란 텍스트에서 줄 바꿈을 나타내는.. 2024. 12. 8.
최적화된 버블 정렬(Optimized Bubble Sort)이란 무엇인가? 이전 글에서 버블 정렬에 대해 알아보았습니다. 2024.12.08 - [코딩 테스트] - 버블 정렬(Bubble_Sort)이란 무엇인가? 버블 정렬(Bubble_Sort)이란 무엇인가?버블 정렬(Bubble SortSort)은 간단하지만 효율성이 떨어지는 정렬 알고리즘입니다. 버블 정렬을 한 마디로 정의하자면 “맨 뒤부터 정리하는 정렬” 혹은 “옆과 비교하여 왼쪽이 더 크면 좌우 교arctis7p.tistory.com 여기서 한 단계 더 들어가서 최적화된 버블 정렬에 대해 알아보기 전에 버블 정렬을 다시 생각해 보겠습니다. 버블 정렬 코드는 모든 패스에서 전체 배열을 비교하여 정렬합니다. 즉, 이미 정렬된 부분도 다시 비교한다는 단점이 있습니다.   하지만 최적화된 버블 정렬은 이미 정렬된 부분을 다시 .. 2024. 12. 8.
버블 정렬(Bubble_Sort)이란 무엇인가? 버블 정렬(Bubble SortSort)은 간단하지만 효율성이 떨어지는 정렬 알고리즘입니다. 버블 정렬을 한 마디로 정의하자면 “맨 뒤부터 정리하는 정렬” 혹은 “옆과 비교하여 왼쪽이 더 크면 좌우 교환하는 정렬”이라고 할 수 있겠습니다.  버블 정렬은 인접한 두 요소를 비교하여 그 순서가 맞지 않으면 교체하는 방식으로 작동합니다.   첫 번째 반복 배열의 첫 번째 요소와 두 번째 요소를 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소를 교체합니다. 이 과정을 배열의 마지막 요소까지 반복합니다. 배열의 맨 마지막 요소는 가장 큰 요소가 됩니다.남은 반복 위의 과정을 반복합니다. 예를 들어, 두 번째 반복에서는 두 번째로 큰 요소가 배열의 두 번쨰 위치에 배치됩니다.  이러한 과정을 배열의.. 2024. 12. 8.

티스토리툴바