[ BOJ / Python ] 1181 - 단어정렬

문제출처https://www.acmicpc.net/problem/1181 걸린시간: 16분 47초 문제분석문자열이 여러개 주어졌을 때 중복되는 문자열은 제거하고 길이가 짧은 순부터 단어가 정렬하되 동일한 길이의 경우, 사전 순으로 정렬해야하는 문제다.최대 2초 내에 최대 20000개의 데이터를 처리해야하므로 알고리즘의 시간복잡도는 O(N^2)을 넘어서는 안된다.  문제접근내 접근from sys import stdininput = stdin.readlinen = int(input())my_words = [input().strip() for x in range(n)]# 사전순으로 정렬하기my_words.sort() # 문자열인 경우 사전순으로 정렬하는 듯 하다.# 길이순으로 정렬하기my_words.sort(..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 12.

[백준/Python] 2751 - 수 정렬하기 2

문제출처https://www.acmicpc.net/problem/2751개요N개의 수가 주어졌을 때 오름차순으로 정렬하는 알고리즘을 짜는 문제다.문제접근시간복잡도알고리즘이 2초 안에 최대 1,000,000(백만)개의 데이터를 정렬할 수 있어야한다. 시간복잡도가 최대 O(2NlogN)이면 백만개의 데이터를 2초 안에 처리할 수 있다. 알고리즘: 병합정렬데이터를 2NlogN 안에 정렬을 해야한다. 정렬 중에 힙정렬, 병합정렬이 NlogN의 시간복잡도를 가진다. 버블정렬, 선택정렬은 구현하기 편하나 시간복잡도가 N^2이기 때문에 배제한다.  코드구현파이썬from sys import stdininput = stdin.readlinen = int(input())my_list = [int(input()) for x..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 11.

알고리즘의 성능측정

성능측정을 해야하는 이유알고리즘이 창의적이거나 좋더라도 실행시간이 느리다면 사용하기가 어렵다. 따라서 알고리즘을 만들고 나면 성능을 측정해야한다.성능측정방법알고리즘의 성능을 분석하는 방법은 지표가 시간이냐, 공간이냐에 따라 달라진다. 시간복잡도알고리즘이 문제를 해결하는 데에 걸리는 시간을 시간복잡도라고 한다. 시간을 기준으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 시간복잡도를 측정한다. 시간복잡도는 빅오표기법으로 표현한다.  공간복잡도알고리즘이 문제를 해결하는 데에 사용하는 메모리량을 공간복잡도라고 한다. 시간을 공간으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 공간복잡도를 측정한다. 공간복잡도도 또한 빅오표기법으로 표현한다. 원본데이터를 기준으로 알고리즘이 문제를 해결하는데 필요한 추가적인..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 11.

이진탐색

목적과 특징💡 조사범위를 절반씩 줄여가며 원하는 원소를 찾는 전략두개의 포인터(left, right)를 활용해 조사범위를 설정한다찾고자하는 원소와 middle 값의 크기를 비교해서 조사범위를 조정한다middle 값이 찾고자하는 원소보다 큰 경우, 왼쪽 조사를 위해 right의 인덱스를 내려서 갱신middle 값이 찾고자하는 원소보다 작은 경우, 오른쪽 조사를 위해 left의 인덱스를 올려서 갱신찾고하는 값이 있는 경우에 해당 원소의 인덱스를, 없으면 -1을 반환한다.구현코드C++int BinarySearch(int *arr, int n, int x) // 이진 탐색{ int left = 0; int right = n - 1; while (left x) { // REVIEW: 찾고자하는..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 10.

선형탐색

정의💡 한쪽 끝에서 시작하여 원하는 요소를 찾을 때까지 목록의 각 요소를 조사하는 알고리즘요소를 찾지 못하는 경우에는 데이터셋의 끝까지 간다.효용배열, 연결리스트의 정렬여부와 무관하게 원소를 탐색할 수 있음그러나 배열이 정렬되어 있고 원소가 배열 내에 존재하는 경우에 탐색 성능이 올라감절차1. 시작: 컬렉션의 첫번째 원소에서부터 시작2. 비교: 현재의 원소와 찾고자하는 원소와 비교3. 확인: 현재 원소가 찾고자하는 원소인 경우 true 또는 현재 원소의 인덱스를 반환4. 이동: 찾고자 하는 원소가 아닌 경우에는 컬렉션의 다음 원소로 이동5. 반복: 컬렉션의 끝에 도달할 때까지 2에서 4의 과정을 반복6. 찾지 못한 경우: 컬렉션의 끝에 도달해도 원소를 찾을 수 없는 경우에는 찾을 수 없음 반환구현Hor..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 7.

버블정렬

정의💡 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘버블 정렬은 다른 정렬과 다르게 모든 원소를 비교하는 것이 특징이다. 구현#include using namespace std;int main(){ int arr[] = {3,2,4,1,5}; int n = sizeof(arr) / sizeof(int); for(int i = 0; i arr[j+1]){ swap(arr[j], arr[j+1]); } } } for(int i = 0; i

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 4.