알고리즘을 좋아하는 나

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)이 될거같다.

문제를 딱 보고.

아 이건! 미리 구해놓고 하나씩 출력하면 될듯~

에라토스테네스의 체를 복습했다.

c++ 기본기 없이 코딩하려니 에러도 많이나서 질문도 많이했다.

풀이과정은

1. 무식하게 버블정렬 : 시간초과

2. sort를 사용하니까 통과됨

a.length >= b.length를 고려 안해줘서 조금 많이 틀렸다.