컴퓨터공학/알고리즘 공부

[알고리즘 문제 해결 전략] Part 1. 6장 무식하게 풀기

알고리즘 문제해결 전략 1 권, 흔히 불리는 이름은 종만북 ! 그럼 이제,,, 시작.. ( 내 글이랑 문제 글 색이랑 같아서 색을 수정 했다... ) 6장 무식하게 풀기, 완전 탐색? 으로 모든 경우의 수를 찾아서 답을 찾아내는 방식 1. 예제 : 보글 게임 (문제 : ID : BOGGLE, 난이도 : 하)https://algospot.com/judge/problem/read/BOGGLE 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나..

Quicksort 2 - Sorting Hackerrank 퀵정렬 퀵소트 문제!

퀵소트 ! 퀵 정렬 !병합 정렬 , Merge Sort 와 같은 divide conquer 정렬이며O(nlogn) 이 걸리지만 병합 정렬보다 평균 속도가 20% 빠르다. Quicksort 2 - Sorting 문제에 java로 작성된 코드를 그대로 사용하려 노력했다.배열을 넘기기 위해 int [] ar 배열을 백터로 바꾸고 배열을 총 3개 준비 했다. 왼쪽 배열 오른쪽 배열 pivot을 선언하고돌아갈때마다 원래의 전체 배열의 index 0 부터 할당 해주었다. 배열의 크기가 2보다 작을 경우는 이미 정렬된 배열이기 때문에 return을 해줬다. left , right 로 계속해서 함수를 재귀적으로 호출한다.마지막까지 다다르면 left pivot right 순으로 인쇄하며, 원래의 ar 배열에 index ..

Quicksort 1 - Partition Hackerrank 퀵소트 퀵정렬 알고리즘

퀵소트, 퀵정렬정렬되지 않은 배열의 값을 임의로 pivot 변수로 정한 후pivot 보다 작은건 왼쪽 큰건 오른쪽으로 분리 시킨다. 재귀적으로 정렬을 반복하다 보면 O(nlogn) 수행시간안에 정렬이 완료된다. Divide and conquer 분할 정복 알고리즘중에 하나! 아래 문제는 처음 1회의 퀵소트 정렬을 마친 배열을 출력하라고 한다.Quicksort 1 - Partition by HackerRankThe previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with an average case performance of . In these next few challenges, we'..

Insertion Sort 삽입 정렬 Hackerrank

Insertion Sort - Part 1 by HackerRankSorting One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.Insertion Sort These challenges will cover Insertion Sort, a simple and intuitive sorting algo..

Counting Sort 계수 정렬 10989 백준 수정렬하기 3

Counting Sort 계수 정렬 ! 시간 복잡도 O(n + k) 만큼 걸리고 공간 복잡도 O(k) 만큼 걸리는 정렬 알고리즘Radix Sort 기수 정렬보다 공간 복잡도가 적게 드는 장점이 있는 정렬 알고리즘이다. Radix Sort 에서는 Linked list 와 Dynamic Array가 필요하기 때문에 계수 정렬에 비해 공간이 절약된다. 기수 정렬에서 정렬될 Index를 계산 하는데 앞서 Counting number 를 누적해 나간다. 누적하기 때문에 다른 배열을 사용하지 않아도 되는 장점이 있다. Unsorted Array : 7, 2, 3, 5Stored Array : 0, 0, 1, 1, 0, 1, 0, 1 1. 정렬되지 않은 배열의 숫자 범위만큼 Stored Array 를 할당하고 숫자의..