SLENDER ANKLES's 개발블로그

정렬은 데이터들을 특정 기준에 맞게 오름차순, 또는 내림차순으로 나열하는 것을 말한다. 

정렬은 많은 방법들이 있는데, 접하면서 정리되는데로 기록해나갈려고 한다.

정렬은 데이터들을 특정 기준에 맞게 오름차순, 또는 내림차순으로 나열하는 것을 말한다. 

정렬은 많은 방법들이 있는데, 접하면서 정리되는데로 기록해나갈려고 한다.

시간 복잡도 O(n2)

선택정렬(Selection Sort)

가장 큰 것을  선택해서 기준 범위의 앞과 스왑(swap)하는 방식(내림차순정렬)

가장 작은 것을 선택해서 기준 범위의 앞과 스왑(swap)하는 방식(오름차순정렬)

예를 들어

6 2 9 8 3 4 7 이 있다면, 이 것을 선택정렬을 사용하여 오름차순으로 정렬해보겠다.

(1) 6 2 9 8 3 4 7 => 2 6 9 8 3 4 7

(2) 2 6 9 8 3 4 7 => 2 3 9 8 6 4 7

(3) 2 3 9 8 6 4 7 => 2 3 4 8 6 9 7

(4) 2 3 4 8 6 9 7 => 2 3 4 6 8 9 7

(5) 2 3 4 6 8 9 7 => 2 3 4 6 7 9 8

(6) 2 3 4 6 7 9 8 => 2 3 4 6 7 8 9

이러한 과정을 거쳐서 정렬이 완성된다. 

선택정렬의 특징이 하나 있다. 배열의 원소를 최소로 바꾸면서 정렬하는 방법이다.

삽입정렬(Insertion sort)

삽입정렬과 선택정렬이 헷갈렷는데, 삽입정렬에 대해서는 확실히 알게 되었다.

한 마디로 말하자면 현재의 인덱스에 있는 값이 위치해야 할 자리로 가는 것을 말한다. 

예를들어 

6 2 9 8 3 4 7    이 있다면

6 2 9 8 3 4 7

2 6 9 8 3 4 7

2 6 9 8 3 4 7

2 6 8 9 3 4 7

2 3 6 8 9 4 7

2 3 4 6 8 9 7

2 3 4 6 7 8 9

이런식으로 범위를 늘려나가면서 해당 숫자의 자리를 찾아주는 코드이다.

버블정렬(Bubble Sort)

문자 그대로 마치 공기방울이 수면 위로 떠오르듯 가장 큰 레코드가 한칸씩 한칸씩 오른쪽으로 떠올라오는 정렬이다.

6 2 9 8 3 4 7

2 6 9 8 3 4 7

2 6 8 9 3 4 7

2 6 8 3 9 4 7

2 6 8 3 4 9 7

2 6 8 3 4 7 9

2 6 8 3 4 7 9

2 6 8 3 4 7 9

2 6 8 3 4 7 9

2 6 3 4 8 7 9

2 6 3 4 7 8 9

2 6 3 4 7 8 9

2 6 3 4 7 8 9

2 3 6 4 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

2 3 4 6 7 8 9

이런과정을 거쳐서 정렬이 된다. 

동적 계획법(dp)는 가장 흔한 문제 유형 중 하나이고 메모이제이션은 굉장히 자주 구현하게 된다. 

따라서 한 가지 패턴을 정해두고 풀게 되면 확실한 풀이 방법을 알 수 있을 것 같다. 

1. 가장 먼저 basecase 처리

2. cache[]를 모두 -1로 초기화하고, -1이 아니면 cache[]의 값이 없는 것으로 간주.

3. ret(리턴 값)을 참조형(reference)으로 관리하여 실수를 줄임

4. memset을 이용한 초기화

소수 결정 알고리즘을 사용 할 줄 알아야 하는 것도 핵심인 거 같다. 

그 이외에는 몇 가지 예외를 처리하는 식으로 문제를 풀었다. 좋은 방법으로 푼 것은 아닌 것 같아 조금 더 연구를 해봐야 할 것 같다. 

하지만, 더블릿에서 실행 속도 3등을 했다.!!!

설명하기 전에 소수 판별 알고리즘에 대해서 간단히 다시 정리하겠다. 

문제정리)

자연수 n(2이상 1 000 000 000이하)의 자연수가 주어지면

그 것을 소인수 분해하는 것이다.

풀이)

1부터 10000정도까지 소수들의 데이터를 배열에 저장 해 놨다. 굳이 말하자면 소수들에 대한 데이터베이스를 구축해놓고,

열람하며 활용하겠다는 방식이었다. 낭비라는 생각도 들었지만 결과론적으로 이 방법이 꽤 빠르다는 것을 알았다.

그다음부터는

수학공식에 있던 방법을 고대로 가지고 와서 코드로 옮기는 방식을 사용했다. 

매번 지금 계산 되고 있는 것이 소수 인지 판별한다. 소수이면 중단하고 소수가 아니면 소수리스트의 값으로 나누어준다.

이 과정을 반복하게 된다.

위와 같은 식을 인수분해 한다.

입력

예시를 참고하시오

(x-p)(x-q)일때 p <= q이어야 한다.

풀이정리)

(x-p)(x-q)를 펴보았다. x2 -(p+q)x + pq로 펴진다.

p+q == a && pq == b

를 만족하는 p, q를 2중반복문을 사용하여 답을 도출하면 끝

쉬운 문제였다. 피타고라스 정리는 이렇게 풀리지 않는 것이 안타깝다.

c라는 정수가 주어졌을 때 

a제곱 * b제곱 = c제곱

인 a, b를 찾는 문제였다. 

c제곱 - a제곱 = b제곱 이라는 것을 이용하여

a, b for문을 두 개 이용하는 것이 아니라 a에 대한 for문 한 개만 이용하여 푸는 방법인데

c제곱 - a제곱의 sqrt(루트)가 자연수이면 그 것은 성립된다는 것으로 생각하면 된다. 

문제는 소수점에 대한 double형인지 소수점 없이 나누어 떨어지는지에 대해서 알 필요가 있다고 생각했다. 

소수판별은 c제곱 - a제곱인 b제곱인 b를

다시 a제곱 * b제곱 == c제곱 인지 검사해줬다.

이렇게 되면 b가 소수점이 나오게 되면 다른 값이 나올 테니까...

테스트케이스 7개까지 통과 했다. 

이 테스트케이스에서 막혔다 ㅡㅡ ㅜ

118276

다시 풀어 봐야 겠다.

--------------------------------

풀렸다

실수를 했다. a에 대한 for문을 돌리면서 습관적으로 int형으로 선언한 뒤에 돌렸다.

생각해보니까 long long으로 선언해서 돌려야 한다. 

for(long long a = 1; a < c; a++)

이런식으로 돌려되는 것을 long long이 아닌 int로 선언해서 된 오류였다.