lecture.js/algorithm.log17 #018 배열조각하기 문제 풀이 사전 과정 짝수 인덱스일 때에는 배열 arr의 query[i]의 인덱스 뒷부분을 잘라서 버림. 홀수 인덱스일 때에는 배열 arr의 query[i]의 인덱스 앞부분을 잘라서 버림. 문제 풀이 세부 과정 주어진 Array를 List로 변환한다. arr을 for문 돌면서 index가 짝수/홀수인지 분기한다. 짝수/홀수일 때에 뒷부분/앞부분을 잘라서 버리기 때문에 List.subList를 사용한다. 주의 사항 java에서 subList할 때 인자값(parameter)에 대한 결과를 체크해본다. 두번째 파라미터(잘라내는 마지막 값)에다가 values.size()-1했다가 삽질함. 테스트 실행 시에는 모두 성공해서 금방 끝났었는데, 제출하면 일부 문제가 계속 런타임 실패로 나와서 삽질함. query값 중.. 2023. 6. 14. #017 퀵 정렬 # 문제) 아래와 같이 정렬되지 않은 배열이 있을때 퀵 정렬을 사용하여 오름차순 정렬하여라. 5 2 4 3 1 병합 정렬과 거의 유사한 분할&정복 방식임. 다만 병합 정렬의 경우, 새로운 배열을 통해 정렬한 반면 퀵정렬을 pivot값을 기준으로 swap하여 정렬한다. 퀵정렬은 먼저 partition작업을 통해 정렬을 수행한다. left를 기준값으로 pivot을 잡고 mid=(왼쪽 인덱스+오른쪽 인덱스)/2, low = 왼쪽 인덱스+1, high=오른쪽 인덱스를 초기화한다. *퀵정렬 효율성을 위해 pivot값 선택을 개선할 수 있음. 일단은 왼쪽을 pivot을 잡도록 하겠음. low와 high가 겹치지 않을때까지 아래 내용을 반복한다. low는 오른쪽 방향으로 이동하면서 pivot보다 큰값을 찾는다. hi.. 2017. 7. 18. #015 힙 정렬 # 문제) 아래와 같이 정렬되지 않은 배열이 있을때 힙 정렬을 사용하여 오름차순 정렬하여라. 5 2 4 3 1 힙 정렬의 힙의 특징을 이용하여 정렬하는 방식을 말한다. 힙의 특징은 아래와 같다. 힙은 완전 이진트리 구조를 활용된다. 추가 시에는 맨 마지막 원소에 추가되며 루트 방향으로 올라가면서 부모와 값을 비교해 적절한 위치를 찾는다. 삭제 시에는 최소 힙으로 구성했을 경우, 최소값을 최대 힙으로 구성했을 경우, 최대값을 반환하고 삭제된다. 또한 삭제 후 이진트리 구조를 유지하기 위해 원소의 마지막 값을 root에 위치하여 자식 중 우선순위가 높은 값과 비교하여 원소의 마지막 값의 위치를 찾는다. 즉, 힙 정렬의 경우, 추가시에 정렬이 된 상태로 들어가게 되며 삭제 시에는 최소(또는 최대) 값을 반환하.. 2017. 7. 18. #014 삽입 정렬 # 문제) 아래와 같이 정렬되지 않은 배열이 있을때 삽입 정렬을 사용하여 오름차순 정렬하여라. 5 2 4 3 1 선택정렬은 방향이 버블과 선택과 다르다. 버블과 선택은 왼쪽에서 오른쪽으로 이동했다면 삽입 정렬은 두번째 부터 시작하여 왼쪽으로 이동하며 삽입될 위치를 찾는다. 만약 왼쪽 값이 더 큰 경우, 왼쪽 값을 현재 인덱스 값에 저장한다. (배열 shift처리) 더이상 왼쪽으로 이동할 수 없거나, 왼쪽값이 더 작다면 삽입할 위치를 찾은 것이므로 해당 위치에 값을 저장한다. int tempValue = 2; 5 2 4 3 1 5 5 4 3 1 2 5 4 3 1 int tempValue = 4; 2 5 4 3 1 2 5 5 3 1 2 5 5 3 1 2 4 5 3 1 int tempValue = 3; 2 4.. 2017. 7. 18. 이전 1 2 3 4 5 다음
