hyeoneee's blog

이 문제는 Union & Find 문제이다.

공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진
원소들에 대한 정보를 저장하고 조작하는 자료구조

초기화에는 자신이 부모인 것으로 초기화 해준다.

그리고 나서 부모 - 자식 관계

즉, 문제에서 동맹관계를 알려주면

해당 부모 자식관계를 par[] 배열에 맺어준다

 그런데 어차피

동맹의 동맹은 동맹이므로

최종적으로 가장 높은 root를 같은걸 가리키고 있으면

같은 동맹이란 사실을 알 수 있다.

그래서 find 펑션에서

가장 높은 root를 찾을 수있도록 재귀로 구현해주었다.

동맹관계를 맺어주는

type =0 이면

각각 부모 - 자식관계를 맺어주고

type =1 이면 가장 높은 root를 구해주는

find 펑션을 통해

그 값이 같은지 비교해서

출력해준다.

다음 문제는 count sort를 알면 그렇게 어렵지는 않았다.

먼저

1. 입력 받은 배열을 정렬을 하고

2. 정렬된 배열의 카운트 배열을 만들어준다.

- 카운트 배열을 만들때 모두 다 셀 필요가 없고

이미 정렬되어 있기 때문에

앞뒤 값을 비교 해서 같으면 +1

다르면 1을 넣어주면 된다.

@_@ 하루종일

문제 푸니깐

머리가 더 잘 안돌아가는거 같다,,

자괴감이 든다 ^_^,,,,,

후후,,,,

그럼 이만

뿅!

전형적인 투포인터 알고리즘 문제이다

중요한건 ;ㅅ;

문제를 읽고 투포인터 알고리즘 문제라는 것을

깨달아야 한다는 것이다 ^_^,,,,,,

따흑,,,

이것도 처음엔 문제 이해가 안갔다 @_@

왜이렇게 문제 이해가 어려운것인지,,,,,흑,,,,

결국 이문제도 간단하게 설명하자면

정렬된 길이 n의 A배열과 길이 m의 B배열이 입력으로 주어졌을 때
A[i]+B[j]=X를 만족하는 (i, j)쌍의 개수를 구하는 문제
이다.

이문제는 어떻게 투포인터 알고리즘으로 구현했냐하면

가장 중요한건

작은 (왼쪽~) 은 i로 정의

큰값부터 줄어드는 (오른쪽 ) 은 j로 정의

한다는 것이다!

A

B

이렇게 투포인터를 만들어주고

각각 끝점 값을 더해줘서

값이 크면~ j를 옮기고

작으면 i를 한칸 옮겨준다.

투포인터 알고리즘을

이해하기 좋은 문제인거 같다

다행히 이문제는

쌤의 설명이 바로~ 이해가 갔다

그럼이만

뿅!

아나그램 문제 풀기

우선 아나그램이 뭔지를 알아야 한다

아나그램이란 ? 문자를 재배열 하여 다른단어로 바꾸는 것이다.

이 문제를 검색하면서 찾아보니

구글 면접에서도 나왔던

아니면 it 기술 면접에 종종 나오는 질문인거 같다.

다음 예제로 문제를 보면,

abcab 가 (S1)

aabbcbbaa (S2)에

aabbc / cbbaa

이렇게 두부분 존재한다.

그래서 답은 2이다.

이문제를 처음에는 잘못 이해 했는데

선생님의 말을 들으니 이해가 갔다

결국 물으려고 하는 것은 이것이다.

S2문자열을 S1문자열의 길이로 끊어서 앞에서 부터 보는데,

그중에 아나그램이 몇번 있을 수 있냐 ?

그래서 S2에서 1~5번째 문자열을보고 아나그램인지 보면된다.

그다음 2~6번재 문자열을 보고

이것도 전에 풀었던 결국 투포인터 알고리즘이랑 비슷하다.

그다음에 아나그램인지를 판별하는것은

결국 아나그램을 판단하는것은

해당 문자열이 몇버 나왔는지를, 카운트하는 배열을 만들어서

그 카운트 배열만큼 숫자가

다 같게 있으면

결국은 아나그램인 것이다.

그걸 구현한 소스는 이것이다.

처음엔 카운트 배열을 구현하는것도 어려웠다.

그런데 선생님이 구현한걸 보니

결국 각각 문자열이 가지고 있는 숫자가? 있으니깐

그 배열의 인덱스에 카운트를 증가 시켜줬다. 

(아마 내가 기억하기로 아세키 코드값인걸로 기억한다 ~_~/ 맞겠지 )

그런데 여기서 구현 할때는

1. S1의 카운트 배열을 먼저 생성

2. S2의 카운트배열을 S1의 길이만큼만 생성  ****아주 중요 ****

해서 비교해준다

그리고 나서 S2의 카운트 배열을 앞에를 빼주고 뒤에를 더해준다 ~

(투포인터 개념!!)

이런식으로 해줘야 시간복잡도가 맞지

안그러면 시간초과! 그래서

이부분이 아주~ 중요하당!

그리고 나서 S1의 카운트 배열과 S2의 (S1길이까지만의) 카운트 배열을

서로 비교해서

같으면 COUNT를 하나 높여준다~

@_@ 첫날 알고리즘 수업인데

그래도 올초에 잠깐 공부하다 만

개념이 나와서

조금은 반가웠고

그래서 이해가 좀 수월했다

앞으로 남은 2주 열심히 해야겠당!

블로그에도 꼬박꼬박 정리이 ~~~

그럼 이만

뿅!