[알고리즘 공부] 삽입정렬
오늘의 알고리즘은 삽입정렬입니다. 삽입정렬은 처리되지 않은 데이터를 골라 적절한 위치에 삽입합니다. 사실 오늘 포스팅하는 삽입 정렬 알고리즘을 포함해서 대다수의 정렬 알고리즘들은 아마 실무에서는 사용하는 일이 없을 거라고 생각됩니다. 그만큼 언어 내장 정렬 알고리즘이 강력하다는 의미겠죠. 하지만 정렬 알고리즘에 어떤 알고리즘이 있고, 어떻게 동작하는지 알아두는 것은 중요하다고 생각합니다. 삽입정렬 시간복잡도 삽입정렬의 시간복잡도는 2중 for문을 사용하기 때문에O(n^2)입니다. 하지만 현재 리스트의 데이터들이 거의 정렬되어 있는 상태이면 매우 빠르게 동작하며, 최선의 경우 O(n)의 시간복잡도를 가지고 있습니다. 선택정렬 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for..
2022. 10. 7.
[알고리즘 공부] 선택정렬
오늘의 알고리즘은 선택정렬입니다.선택정렬은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하여 정렬하는 정렬 알고리즘으로 버블정렬과 함께 가장 기초적인 알고리즘에 속합니다. 선택정렬 시간복잡도 선택정렬은 2중 반복문을 이용하기 때문에 O(n^2)의 시간복잡도를 가지고 있습니다. 즉, 버블정렬처럼 엄청나게 느린 정렬 알고리즘이라는 이야기입니다. 내장 정렬보다 훨씬 느리고, 그렇기 때문에 실무에서는 거의 쓰일 일이 없습니다. 선택정렬 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(array)): min_idx = i #가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[..
2022. 10. 6.
[이코테-구현] 상하좌우
상하좌우 문제는 이코테 책에 수록된 구현문제이다. 그리디 알고리즘은 이전 포스팅에서 끝나고 이제는 구현 문제로 넘어온 것이다. 문제 설명 여행가 A는 N x N ㅋ크기의 정사각형 공간에 서있다. 이 때, 시작 좌표는 항상 1, 1이고, L, R, U, D 중 하나의 문자가 반복적으로 주어진다. LRUD는 각각 왼쪽으로 한 칸, 오른쪽으로 한 칸, 위쪽으로 한 칸, 아래쪽으로 한 칸 움직인다는 의미이다. 정사각형 공간을 벗어나는 움직임은 무시된다. 입출력 조건은 각각 n의 크기와 이동할 계획서가 주어지면 도착할 지점의 좌표를 공백으로 구분하여 출력하는 것이다. 문제 해결 아이디어 나는 이번 문제를 다음과 같이 풀었다. 입력받은 배열만큼 반복해서, 계획이 정사각형을 벗어나는지 확인한다. 만약 벗어나지 않으면..
2022. 10. 4.