알고리즘을 좋아하는 나

Quick Sort는

최악의 경우 n^2

평균 nlgn

퀵 정렬의 내부 루프는 컴퓨터 아키텍쳐에서 효율적으로 작동되도록 설계되어 있다.

(메모리 참조가 지역화되어 있기 때문에 CPU캐시의 히트율이 높다.)

핵심만 정리하자면

pivot의 왼쪽엔 pivot보다 작은값

pivot의 오른쪽엔 큰값

do

if arr[i] > pivot && arr[j] < pivot // i와 j는 알아서 증가한다고 가정

swap arr[i++], arr[j--]

while(i <= j)

if(left < j) quickSort(arr, left, j)

if(right > i) quickSort(arr, i, right)

5
0 4
1 2
1 -1
2 2
3 3

1 -1
1 2
2 2
3 3
0 4

y를 오름차순으로 정렬하는데, y가 같으면 x의 오름차순으로 정렬하는 문제.

quick sort를 사용하면 nlgn인데,

y, x를 둘다하게되면

시간초과여서

꼼수를 부렸다.

2
-5 1 12 1
7
1 1 8
-3 -1 1
2 2 2
5 5 1
-4 5 1
12 1 1
12 1 2
-5 1 5 1
1
0 0 2

3
0

문제의 입출력이 너무 많아서 어려운줄 알았는데,

생각해보면 쉬운 문제다.

원 안에 점이 포함되면 ++

원이 2점을 감싸면 continue

두 원의 중심과 반지름만 있으면 관계가 어떻게 되는지 구할 수 있다.

문제를 풀면서 distance를 실수형으로 안해서 많이 틀렸다.

3
0 0 13 40 0 37
0 0 3 0 7 4
1 1 1 1 1 5

2
1
0

전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 나가서 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.

이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다.

출처 : https://ko.wikipedia.org/wiki/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4_%EB%AC%B8%EC%A0%9C

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

1
2
2
0
1
2
-1
0
1
-1
0
3

front는 맨 처음에 offer된 변수를 출력하면 된다.

Java에서는 front같은 메소드가 없는거 같아서 iterator에서를

돌려서 출력해줬다.

곱셈의 결합법칙을 이용해서 예외처리를 해줬다.

주석에 설명을 잘 달아놨다.

처음에 문제를 잘 못 이해해서,

8
4
3
6
8
7
5
2
1

이면

8 = n 이고

4번 +하고

4 - 3 + 1 만큼 -하고 이런식으로 되는 줄 알앗는데,

1~N까지 push하고 차례대로 pop해주는거였다.

아이디어 :

1. 에라토스테네스의 체를 이용해서 소수를 구한다.

2. 소수를 primeNumber에 하나씩 넣어준다. 마지막값은 0이다.

3. 2... 돌게되면 0이 나오는데 0이면 반복문을 종료한다.

4. 반복문 안에 반복문을 넣어서 값을 더해주고 맞으면 빼기한 값을 저장하고 그걸로 체크를한다.

더 좋은 방법.

어차피 빼기값을 최소로 구하는거니까. n/2부터 시작해서 하나씩 빼면서 맞는답이 나오면 바로 출력하면 더 빠르다.

이 방법을 사용하면 2번 과정이 없어진다.

더 좋은 방법을 사용한다면,

O(Nnlgn)이 될거같다.