6. 기본정렬에 대하여- 버블정렬, 선택 정렬, 삽입 정렬(백준 2750 파이썬)
기본 오브 기본 정렬 문제도 풀어보았다. 내가 기억하는 애들은 기본적인 버블정렬, 선택정렬, 삽입정렬 그리고 대망의 퀵정렬이다. 아마도 앞의 정렬들은 직접 구현하기보다 파이썬의 sorted()나 .sort()를 써서 해결할 것 같고, 실제 구현을 하게 될 애는 시간복잡도 nlogn에 빛나는 퀵정렬이 아닐까 한다. 백준에 정렬 기본 문제는 2750(브론즈1)과 2751(실버5)가 있는데, 차이는 주어지는 수의 크기 차이로, 실버 문제는 일반 정렬로는 시간초과가 나오지 않을까 예상이 간다. 그래서 오늘은 2750번은 버블정렬, 선택정렬, 삽입정렬 3가지로 풀어보고, 다음 게시글에서 2751번은 퀵정렬을 구현하는 시간을 가져보겠다. https://www.acmicpc.net/problem/2750 2750번:..
더보기
3. 이제는 친숙해진 DFS, BFS (백준 1260 파이썬)
처음 배웠을 때는 충격과 공포였는데, 이제는 오히려 안심이 되는(?) 친근해진 DFS, BFS다. 생각보다 개념은 단순하게, 트리모양을 보면 이해가 빨리 되고, 실제 문제를 풀 때 내가 가장 쉽게 이해한 방법은: DFS는 stack, 그리고 재귀는 결국 stack이므로 재귀로 풀 수 있음 BFS는 queue, 그래서 더 쉽긴한데 pop(0)이 좀 효율성이 안좋다 이외에 좀 주의해야 하는 부분은 입력 값을 어떻게 저장하는가 부분이다. 사실 그래프 유형과 DFS BFS 유형도 비슷한 것 같고,, 재귀로 푸는 문제들도 서로서로 비슷한 것 같고.. 약간 딱 나눠서 할 수 있나 싶은데 (백준에서도 브루트포스 재귀로 분리되어 있는 문제가 DP로 풀기도 하고..) 여튼 그래프 형식은 노드, 간선, 시작점 입력에 익숙..
더보기
