선택 정렬(selection sort)
선택 정렬은 모든 $i$에 대해 $A[i…N-1]$에서 가장 작은 원소를 찾은 뒤, 이것을 $A[i]$에 넣는 것을 반복합니다. 찾는 과정이 inner for loop, 시간 복잡도는 $O(N)$이기 때문에 선택 정렬은 최악의 경우와 최선의 경우 모두 $O(N^2)$의 시간 복잡...
Recent posts
삽입 정렬(insertion sort)
삽입 정렬은 전체 배열 중 정렬되어 있는 부분 배열에 새 원소를 끼워넣는 일을 반복하는 방식으로 동작합니다. 삽입 정렬의 최선의 경우는 처음부터 이미 정렬된 배열이 주어지는 경우입니다. 모든 원소는 처음부터 제자리에 있기 때문에 j에 대한 while문은 매번 즉시 종료하게 됩니다...
[알고리즘 문제해결전략] 알고리즘 설계 패러다임
무식하게 풀기 ‘무식하게 푼다(brute-force)‘는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부...
[알고리즘 문제해결전략] 알고리즘 분석
알고리즘(Algorithm)이란? 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 한 가지 방법을 명료하게 써 놓은 것 알고리즘을 평가하는 두 가지의 큰 기준은 알고리즘이 사용하는 시간과 공간입니다. 시간: 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작...
[백준 BOJ_7568] 덩치 Python 풀이
출처: 백준 온라인 저지 문제 풀이 몸무게와 키의 정보를 tuple로 이루어진 list로 받아줍니다. 등수는 1부터 시작하니 1로 초기화된 N의 크기의 list를 준비합니다. 이중 for loop으로 각각의 몸무게와 키를 비교한 뒤 비교 대상보다 작을 경우 해당 inde...