정렬 알고리즘은 단골 면접 질문이다. 최근에 본 면접에서도 특정 정렬 알고리즘에 대해 설명해 보라는 질문을 받았다. 학교 수업 때나 코테 준비를 하면서 여러 가지 알고리즘을 접해 보았고 전반적으로 이해는 하고 있지만 막상 면접 때 일목요연하게 답하려 하니 만만치 않았다. 그래서 이번에 한꺼번에 다시 정리를 하면서 면접 때 답변한 방식도 대강 정해 놓으려 한다. 1. 거품 정렬 Bubble Sort 시간복잡도: O(n^2) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 각 리스트를 한 번씩 훑을 때마다 가장 끝 자리의 원소는 정렬에서 제외된다. 각 회전마다 하나의 원소씩 제외하고, 각 원소의 길이 -1(두 개씩 비교하기 때문) 만큼 회전을 반복하기 때문에 ..

백준 문제를 풀다가 계수 정렬에 대해 알게되었다. 상황에 따라서는 상당히 매력적인 배열 방식인 것 같다. 원리는 간단하다. A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] 라는 리스트가 있을 때, 리스트를 차례대로 돌면서 해당 원소가 몇 번 나왔는지 체크하면 된다. 코드로 살펴보면 다음과 같다. A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] cnt = [0 for _ in range(8)]# A에서 나올 수 있는 원소의 최댓값 + 1 for a in A: cnt[a] += 1 print(cnt) # [0, 1, 1, 3, 2, 1, 1, 1] for i in range(1, 8): for _ in range(int(cnt[i])): print(i, end= ' ') # ..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 브론즈 문제지만 counting sort에 대해 알고있지 않다면 풀 수 없는 문제이다. 리스트의 정렬을 생각하면 우선 그 리스트를 온전히 다 입력받은 상태에서 어떤 정렬 방식을 쓰는 것이 가장 효율적일까를 생각하겠지만 이 문제의 경우 입력값의 개수 N 이 최대 10,000,000이기 때문에 이를 다 입력받으면 메모리 초과가 발생한다. 그렇다면 모든 원소들을 입력받지 않고 정렬을 진행해야 한다는 것인데.. 힌트는 입력..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분 탐색을 공부하는 중 대표 문제로 지정되어 있어서 들어가 봤더니 이전에 다른 방식으로 해결한 문제였다. 이번엔 이분 탐색을 사용하여 풀어 보았다. 파이썬 이분 탐색 라이브러리: from bisect import bisect_left, bisect_right 이를 이용해서 리스트에 자신이 찾길 원하는 숫자가 존재하는지 확인할 수 있다..! bisect_right(a..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 여러 책 이름들을 입력받는데 이 중 가장 많이 중복된 책의 이름을 출력하면 되는 문제이다. 중복되는 요소의 count -> C++에서는 map, 파이썬에서는 dictionary를 이용하면 된다. 여기서 한 가지 더 생각해야 하는 것은 count가 같은 책 이름들이 있을 때, 사전순으로 나열해 가장 앞에 오는 순서의 책 이름을 출력해 주어야 하는 것인데, 결국 map, 또는 dic을 써서 카..