[모두의 알고리즘] 탐색과 정렬(1)

탐색과 정렬

순차탐색 / O(n)

• 문제: 리스트에 찾는 값이 여러 개 있더라도 찾는 값의 모든 위치를 리스트로 돌려주는 탐색 알고리즘을 만들어라. 리스트에 없다면 빈 리스트인 [ ]를 돌려준다.

쉽다고 생각하고 들이댔으나 현재 result로 보이는 값을 처음에 전부 lst로 만들었더니 어떤 예를 들던 빈값이 나왔다. if문에서의 lst[i]값이 없어서 조건을 만족시키지 못하고, 그래서 그냥 빈 리스트의 값을 리턴값으로 줬던 것 같다. 

 

 

• 문제: 학생 번호와 이름이 리스트로 주어졌을 때 학생 번호를 입력하면 학생 번호에 해당하는 이름을 순차 탐색으로 찾아 돌려주는 함수를 만들어라 

예시 없이 본다면 이해되지 않을 수도...

개인적으로 맞추고 꽤 기분 좋았던 문제다. 3개의 정보를 받아서 만든 함수는 처음이라 맞나 싶었는데 결과가 정확하게 나오는 걸 보고 '오 되네?!' 하면서 좋아했다. 책을 통해 배운 기초적인 것을 좀 더 활용해서 적용한 느낌이라 뿌듯하기도 했고..

 

 

선택정렬 / O(n^2) - 선택정렬, 삽입정렬, 병합정렬, 퀵정렬, 버블정렬 등이 있다.

• 문제: 일반적인 선택 정렬 알고리즘을 사용해서 리스트 [2, 4, 5, 1, 3]을 정렬하는 과정을 적어라

 

 

• 문제: 기존 오름차순 정렬을 내림차순 정렬로 바꾸려면 어느 부분을 바꾸어야 할까? 

빨간 네모 친 부분. i 다음 인덱스 값이 i보다 클 경우 최대 값을 바꿔준다는 의미이다.

 

 

삽입정렬 / O(n^2)

• 문제: 일반적인 삽입 정렬 알고리즘을 사용해 리스트 [2, 4, 5, 1, 3]을 정렬하는 과정을 적어라 

이미 정해져 있는 사이에 삽입하면서 정렬을 하는 알고리즘

[2, 4, 5, 1, 3]

>>> [2, 4, 1, 5, 3]

>>> [2, 1, 4, 5, 3]

>>> [1, 2, 4, 5, 3]

>>> [1, 2, 4, 3, 5]

>>> [1, 2, 3, 4, 5]

중간에 while문을 통해 i는 앞에 배열된 숫자들(j -= 1)과 자신을 비교하며 들어갈 자리를 찾는다.

 

 

• 문제: 기존 오름차순 정렬을 내림차순 정렬로 바꾸려면 어느부분을 바꿔야 할까 

네모 친 부분. 앞의 숫자가 i 자기자신보다 작으면 위치를 바꾼다

 

두 번째 문제를 풀 때 인덱스 범위에 대한 오류가 계속 발생해 뭐가 문제지 싶었는데, j >= 0 의 조건을 설정 안 해줘서 j가 음수까지 가서 그런 것 같다. 문제 원인 확인 후 바로 고쳐줬고, 사실 첫 번째 문제는 j값의 범위 조건을 설정 안해줘도 풀렸는데 같은 조건을 설정해 줬다.

 

삽입정렬의 경우 앞부분인 왼쪽이 정렬돼 있다고 가정하고 멈출 포인트(어디까지 바꿔야 하는지)를 알고 있기 때문에 선택 정렬보단 효율적일 수 있다. 비교만하고 바꾸는 거 없이 자리를 찾아 들어가기 때문(?!)