hyeoneee's blog

백준 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주 열심히 해야겠당!

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

그럼 이만

뿅!

백준 2805

나무자르기

(이분탐색)

풀이

이분탐색이라그래서

어제푼 문제 그대로 풀었더니

안되었다..

이 문제의 가장 우선적으로 중요한 점은

int가 아닌 long을 써야한다는 것이다.

입력이 2억까지인데.

int는 2의 32승으로 약 21억

하지만 합도 구해야하기때문에

long으로 해야한다.

그리고 주석에도 있지만

헷갈리는것은

등호 하나로 틀렸다.

비교하는 시작점~ 끝점을 

무조건 while 조건문에 시작점이 >끝점보다 작을때까지 

while조건문을 수행하도록 하였지만

그러면 시작점 = 끝점일 경우가 고려가 되지않아

틀렸다.

그리고 나무 크기를 자르는 것이 m의 값으로 딱

떨어지지 않을수도 있기때문에

m보다 클때의 값을 구해야한다.

그중에 가장 큰값.

기본적으로 이분탐색이기 때문에

lo와 hi를 두어야한다

(시작~끝)

그리고 중점을 잡아 비교해야한다.

중점이 곧 구하고자하는 값이다.

이 시작 / 끝을 정의를 잘하는 것도 필요한 것 같다.

저번문제에서는 인덱스로 정의하였지만

이번엔 나무의 길이로 정의하였다.

차근 차근 더 풀어보아야겠다

그럼

이만

뿅!

백준

1920번

수찾기

(이진탐색) 

처음에 이진탐색 아닌 다른걸로 푸려고하다가

실패하고

이진탐색을 공부하기로했다..

개념은 알고

그런데

꼭 구현해보려면 하면 헷갈리더라..

이진탐색의 중요한 것은

우선 순서대로 정렬이 되어 있어야 한다는 것이다.

그래야 해당 순서로 비교 할 수 있기 때문이다.

이진탐색은

정렬된 값을

처음부터 끝까지 모두 이값이 맞는지?

비교하지 않고

중간값으로 이값인지? 이값보다 작은지 ? 이값보다 큰지?

를비교하여

중간번째의 값이 구하고자 하는 값이면 리턴해주고

작거나 크면 구하고자하는 구간을 조정해주면된다.

이진 탐색을 다시한번

복습할 수 있는

문제였다

:)

그럼

이만 뿅!

백준 

2003번

수들의 합 2

문제 풀이 

문제를 접근할때 어려웠는데

친구의 도움으로

투포인터라는 알고리즘이란걸 알았다.

투포인터는

즉, 시작점과 끝점을 기록한다는 것인데

이 문제로 보면 합을 더해진

시작점과 끝점으로 합을구해

이전에 구했던 합을 다시 구하지 않고

답이아니면 시작점의 값을 빼주고

다시 끝점을 늘려가는 형식으로 

되어 있다.

다음번 문제를 차근히 풀어봐야겠당

시작하는 문제로

좋은것 같당

:)

그럼

이만

뿅

동적 프로그래밍(Dynamic Programming)이 란?

작은 결과 값을 이용해 더 큰 결과값으로 올라가 구하려는 결과값을 얻어 내는 알고리즘

> 중복되는 것은 기억해 두어서 skip (메모이제이션)

대표적인 것으로 피보나치 수열이 있다.

f(x) = f(x-1) + f(x-2);

1,1,2,3,5,7,14,21 ... 34,55

단순한 피보나치 수열을 짠 코드는 

int fibo1(int n) {

if (n < 2) {

return 1;

}

return fibo(n - 1) + fibo(n - 2);

}

이렇게 된다.

하지만 이 과정에서 똑같은 작업이 중복되어 일어난다.

예를들어 5를 구할때

5 - 4 -3  -2

      -1

 - 2   

   - 3 - 2

   -1

3부터는 중복이 일어난다 

이러한 중복을 막기위해 쓰는 것이 메모이제이션이다.

한번 구했던 값이면 다시 구하지 않고 넘어가도록 !

구했던 값인지 체크하는 로직을 넣어주기만 하면된다.

메모이제이션이 적용된 피보나치 수열 코드이다.

int fibo(int n) {

if (dp[n] > 0) {

return dp[n];

}

if (n < 2) {

return dp[n] = n;

}

return dp[n] = fibo(n - 1) + fibo(n - 2);

}

가장 이해 하기 쉬운 예로 접하니 더 이해하기 좋다.

구한 값을 dp[n]에 넣어주니 dp[n]의 값이 0 보다 큰지만 체크해주면 된다! ( 그전에 구한 값인가~?)

이렇게 하면 쉽지만...

다른 문제들을 풀어보면 어렵더라 

다른 문제를 풀어 보고 더 적용해 봐야겠다.

그럼 이만

뿅!