[ 백준 1377 : 버블 소트 ]
c++로 작성된 버블 소트 소스가 문제에 주어져 있다.
몇 번이나 숫자들이 옮겨지는 과정을 반복하는지를 출력하는 소스다.
버블소트 알고리즘이 시간복잡도가 N^2이라는것은 N번 반복되는 FOR문이 이중으로 써져있으니까
눈으로 쉽게 확인이 가능하다.
그럼 N의 범위를 보자 ... 음 ! 50만이면 50만*50만 = 1억을 넘는군. 그럼 1초를 넘는군
당연하게도 이렇게 풀면안된다.
그럼 규칙을 찾아야한다.
테스트 케이스를 보면
테케-> 10 1 5 2 3
1번 -> 1 5 2 3 10
2번 -> 1 2 3 5 10
3번 -> 탈출~
처음엔 제일 큰 수가 뒤로가고 그다음 수가 뒤로가고 끝
다른 예제를 생각해보자.
입력-> 5 6 1 3 2 9 8 10 13
1번 -> 5 1 3 2 6 8 9 10 13
2번 -> 1 3 2 5 6 8 9 10 13
3번 -> 1 2 3 5 6 8 9 10 13
4번 -> 탈출~
이미 큰 수들이 뒤에 위치해있다. 하지만 첫 번째 반복에서 많은 변화가 일어났다.
바로 6과 9까지 정렬이 되었다.
두 번재 반복에서는 5까지 뒤로가고 세 번째에 완전히 정렬이 된다.
여기서 주목할 점은 작은 수들의 위치 변화이다.
1은 3번째 위치에서 첫번째 위치까지 왔고 2는 5번째 위치에서 두번째 위치까지 왔다.
그럼 반복된 횟수로보면
1은 3번째 위치에서 두번씩 스왑이 되었을까?? 아니다
당연히 한번씩 위치가 바뀐다. 그러니까 인덱스 3에서 1로 오는데 두번은 반복이 된것이다.
그럼 2는?????
세번 반복된거다.
이런식으로 본다면 처음 위치한 인덱스에서 정렬이 된 후의 인덱스 차이를 보면된다.
그 차이가 가장 큰 만큼 위치가 변한 것이니 문제에 나온 소스와 같은 출력결과를 볼 수 있다.
이 블로그 검색
피드 구독하기:
댓글 (Atom)
-
[ 백준 1024 : 수열의 합 ] 간만에 푼 백준~ 쉬운 문제라고 생각하고 풀었는데 계속 틀려서 봤더니 예외 처리를 한 개 안해준것이 있었다. 만약 이 글을 보기전에 풀었을때 채점이 60%에서 자꾸 틀린다면 90%확률로 나와 같은 실수를 ...
-
[백준 1091 : 카드 섞기 ] 이 문제도 5달 전에 풀었다가 포기했었던 문제였나보다. 오늘 틀렸던 문제 다시풀기 중 풀게 되었다. 문제를 읽는데 헷갈려서 머리카락 한 10번은 쥐어짠듯. 아마 전에 풀었을때는 P배열이 각 카드가 최후에 ...
-
아마 나와 비슷한 나이대의 학생들은 대부분 대학에서 수업을 들으면서 꾸준하게 들었을 것 같다. 물론 내가 그래서 그렇다. 4차산업~ IT의 시대~ 빅데이터~ 데이터 마이닝~ 하지만 컴퓨터 관련 전공자가 아니고 더군다나 공학 계열 전공자가 아니라...
[백준 16236] 아기 상어
[ 백준 16236 : 아기 상어 ] 2018 삼성전자 sw직무 하반기 기출문제입니다. 역대 삼성전자 기출문제가 그렇듯 역시나 BFS,DFS,완탐,DP,단순구현 입니다. 저는 문제를 단순히 BFS로 풀어갔습니다. 조건만 잘 지킨다면 한번에 ...
댓글 없음:
댓글 쓰기