hyeoneee's blog

DFS와 BFS 문제이당

츄욱,,,,,

대학교때 다 했던건데,,,

지나면 까먹는닷 ^^,,,

그래도 교수님이 잘 설명해주셔서

엄청!! 잘이해했다

(지금만큼은,,,)

여기선 하나만 더하면된다

기본적인 DFS와 BFS를 하고

오름차순 순으로 출력하라고 했으니깐

인접리스트에 오름차순으로 넣어주면 된당!!!!

츄욱,,,

이거때문에 선생님한테 물어도 봣당^_^,,,,,

BFS는

큐를 사용하였고

DFS는 스택을 사용하였당

그리고 DFS는 재귀를 사용!

그리고 C배열을 이용하여

방문하였는지 안하였는지를 쳌쳌!!!!

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

먼저

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

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

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

이미 정렬되어 있기 때문에

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

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

@_@ 하루종일

문제 푸니깐

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

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

후후,,,,

그럼 이만

뿅!

백준 9663번 NQueen 문제.

가장 유명한 백트래킹 문제 nQueen 문제이다.

이전에 시험볼떄 오조오억번 풀어서

달달달~~ 외웠는데

왜 몇년 지나고 다시 풀려고하니 기억이 안나지 ^.ㅜ

휴

두가지 방법으로 풀어 보았다

첫번째는 이전에 공부한 방식

1. 이중 for 문을 쓴 방식

2. for 문을 하나 쓴 방식

1. 이중 for문

열과 행의 정보를 담는 배열을 두개 선언해 주고

해당 열을에 퀸이 있는지,

대각선에 퀸을 놔도 되는지를

체크해준다.

정의를,

열과 행의 정보를 담아준다로

정의해서 이중포문을 썼다.

2. 포문을 하나 쓴 경우

 가지치기 할수 있는 경우를 세개를 정의해서

해당 배열을 3개 선언해주었다.

가. 같은 열에 퀸이 있는지

나. 대각선 체크 y=x 기울기가 1인 대각선 체크

다. 대각선 y=-x 기울기가 2인 대각선 체크

두 개 모두 행을 인자로 두고

재귀를 쓰는것은 똑같다.

휴,, 백트래킹

마스터 함해버자,,,, ^_^,,,,

그럼 이만

뿅!

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

중요한건 ;ㅅ;

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

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

따흑,,,

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

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

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

정렬된 길이 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주 열심히 해야겠당!

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

그럼 이만

뿅!