zoonvivor

1931 문제를 풀고 난 후 푸니까 매우 쉬웠다.

Comparator를 사용한 정렬을 했다.

아래는 1931 문제에서 Comparator를 사용한 내용

그리고 11650 좌표정렬하기 1 번이랑 문제가 또오오오옥같다. (x좌표랑 y좌표만 바꾸면 됨)

-------------------------------------1931------------------------------------- 

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3

처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

-------------------------------------1931------------------------------------- 

11651 좌표 정렬하기 2 소스코드

계속 해서 Comparator를 사용해서 문제를 풀고 있다. 으흠

1. 맨처음 나이순으로 정렬한다.

끝이다.

그 다음 가입한 순서대로 정렬을 해야하는데 들어온 순서가 가입한 순서기 때문에 이미 정렬이 되서 들어왔다.

단순히 String[][] 2차원 배열을 어떻게 정렬할까에 대한 문제이다.

1931 문제를 풀고 난 후 푸니까 매우 쉬웠다.

Comparator를 사용한 정렬을 했다.

아래는 1931 문제에서 Comparator를 사용한 내용

-------------------------------------1931------------------------------------- 

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3

처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

-------------------------------------1931------------------------------------- 

11650 좌표 정렬하기 <소스코드>

Comparator 가 부족한것 같아서 Compartor를 이용해서 문제를 풀었다.

Comparator에서 int, float, char 등은 원시적인 데이터등은 정렬이 되지 않고 Object등만 정렬 가능하다. (String, Integer 등등)

그런데 원시적인 데이터의 2차 배열은 객체인가보다.. int[][]는 Comparator를 통해 정렬을 할 수 있다.  너므 어려운것...

나는 그래서 이문제를 Comparator를 통해 풀고자 int배열이 아닌 Integer 배열을 사용했다.

나처럼 Comparator를 사용해서 푼 사람은 많이 없는거 같아서 나한텐 어려웠던 문제

푸는 방법) 

끝난 시간이 빠를 수록 다음 시작시간이 빠르기 때문에 2차원 배열을 정렬한다.

다음 제일 빨리 시작하는 회의를 선택한다. (끝나는 시간도 제일 빠르다. 이미 정렬을 해 놨으므로)

차례대로 마지막까지 반복한다.

1. 시작시간 - 종료시간 을 arr[][] 배열에 저장한다.

2. arr[][] 배열을 종료시간에 따라 정렬한다.

이때, 나는 Comparator를 이용해 정렬을 했다.

정렬을 할 때 

1 1                0 1

1 1      --->      1 1

0 1      --->      1 1

2 3                2 3

처럼 정렬이 되어야 하는데 기본 Comparator 에서는 정렬되지 않기 때문에

동일 시 되었을 경우 앞에 값을 우선으로 하는 start[1] ==end[1] 이라는 조건을 넣어

종료시간 정렬 후 종료 시간이 같을 경우, 시작시간에 따라 다시 한번 정렬을 했다.

3. 정렬이 되었다면, 종료시간과 다음에 올 시작시간을 비교하면 된다.

BFS를 통해 푸는 문제이다. 물론 DFS로 문제를 풀 수 있을 것 같다.

나는 세가지 변수를 설정했다.

1. 1촌 관계를 저장하는 배열 : Arr[][2]

2. 방문했던 점을 저장하는 배열 : visited[]

3. 얼마만큼 지나왔는지 저장하는 배열 : total[]

세가지만 이용하면 쉽게 문제를 풀 수 있다.

문제에 나와있지 않은 예시를 하나 들자면.

10

7 6

9

1 2

1 3

1 4

9 1

9 10

3 5

3 6

2 7

2 8

이 있다. 이때의 결과값은 4가 나와야 한다.

규칙만 찾으면 정말 금방 풀 수 있는 문제이다.

DP 문제는 일단 경우를 모두 써서 규칙을 찾아내는 게 중요하다고 배웠다.

그래서 무작정 경우를 작성해보았다.

위 표와 같은 결과가 나온다.

위 표에서 DP[] 라는 배열을 할당했을때

 - 0은 횟수(N)이 증가함에도 상관없이 1임을 알수 있었다.

 - 1~9는 횟수(N)이 1일때를 제외하고, 이전에 있던 자신의 값과 바로 전값의 합임을 알 수 있었다.

즉,  dp[i] = dp[i]  dp[i - 1] 이라는 규칙을 얻어 낼 수 있었다.

<소스코드>

아주 간편히 배열을 출력하는 방법이 있다.

일반적인 for문

위의 반복문을 아래오 같이 바꿀 수 있다.

간편한 for문 (for each) 의 구조

2. ArrayList를 사용한 경우

등 Char[], Int[] 배열에도 사용될 수 있다.

항상 모든 경우의 수를 구할 때 어려움을 겪어왔다.

예를들어, 배열 N칸이 있는데 N칸 중 부분 배열의 합이 M 이상되는 경우를 구하라는 문제가 있다고 가정하자.

그럼 000, 001, 010, 011, 100, 101, 110, 111 를 모두 구해야 한다. (N칸을 3으로 가정)

가장 쉬운 방법으로는 반복문(for 문)을 3개를 작성하면 된다. 하지만 N의 값이 유동적이라면?

미리 반복문을 만들 수 없다. 어떻게 해결해야 할까?

해결책은 2가지가 있다.

1. 재귀를 이용한 백트래킹

2. 비트연산을 이용한 방법

나는 재귀보다 속도가 빠른 비트 연산을 방법을 이용하겠다.

12라인에 있는  i < 1 <<N; 은 i< (1<<N); 이다. 즉, 1을 N 만큼 left Shift 한 결과로 2^N 이 된다.

예를 들어, 1일경우 2가 되고 2일 경우 4가 된다.

그 뒤 i 값을 bit로 받아 bit가 0이 될때 까지 right Shift 한다.

예를 들어 i가 7인경우 0111 로 나타낼 수 있는데 

0111 를 right Shift 하여 0011 --->0001 --->0000 으로 나타낼 수 있다.

여기서 (1&bit)를 하게 되면 가장 오른쪽에 있는 값과 &연산을 하여 1일 때만 나가도록 한다.

0000 일때는 나가는 값이 없고 1101 일때 1, x , 1, 1 순으로 나가게 된다.

나가는 순서가 반대이므로 abc 배열은 역방향으로 저장된다.

그렇게 떄문에 반복문을 반대로 출력한다. 

그 결과 

순으로 출력된다.

원하는 000, 001, 010, 011, 100, 101, 110, 111 값들을 얻게 되었다!.

*반대로 출력하고 싶다면 첫번째 반복문을 for (int i = (1<<N)-1; i >=0; i--) 으로 바꾸면 된다. (감소하는 순으로)

배열이 아닌 큐를 사용해서 풀었다.