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번

수찾기

(이진탐색) 

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

실패하고

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

개념은 알고

그런데

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

이진탐색의 중요한 것은

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

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

이진탐색은

정렬된 값을

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

비교하지 않고

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

를비교하여

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

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

이진 탐색을 다시한번

복습할 수 있는

문제였다

:)

그럼

이만 뿅!

교토 카페

요지야 카페

은각사지점

강추 후기

교토를 처음 간 목적부터가

조용~ 하고 

교토교토하고 

일본스런~_~

분위기를 즐기고 

힐링하고싶어서 간건데요

딱맞는 장소를 찾았다

아침에 일어나마자 

이 카페로 직행!!

넘나 고즈넉한 풍경이 기다리고 있다

두둥

대문조차 예뻐 고즈넉해!

안에 들어가면 바로앞에 보이는 곳이 입구예요 ㅎㅎ..

잘못하고 안쪽까지 들어갔다가

거기는 기념품

요지야 화장품 , 거울 등등 을 파는 곳이더라고요 

그리고 신발을 벗고 안에들어가면~~

예쁜 요지야 카페를 쳐다보면서 앉을 수 있게 

되어있어요

넘나 예쁜 풍경을 

보면서 차 한잔을 할 수 있습니다 ,,,,

햇살....

햇살까지 이날 다했고요

ㅠ_ㅠ 행복했습니다..

그리고 10시엔가 오픈을 하는데

11시에 도착을했는데

한팀 있었어요

저희가 도착한 이후로는 

사람들이 많아졌어요

빨리가는게 좋을거 같아용 :)

좋은자리 앉고 싶으면

그리고 나서 시킨 

유명한 요지야 세트

11000엔 정도 했던거 같다

하단에 있는

요지야 얼굴 과자에

녹차아이스크림 + 앙꼬를

조그마한 수저로 퍼서

야무지게 만들어서

먹으면 된당

ㄴ ㅑ ㅁ ㅣ ....

그리고 요지야 녹차라떼..

ㅎ_ㅎ 일반 녹차라떼와 거의 똑같지만

사진을 자동으로 찰칵찰칵 찍게만든다

욕구 뿜뿜

그리고 처음엔 얼굴 망가져서 

먹기 아쉽지만

나중엔 

녹차가루를 잘섞고싶어서

결국

슥슥 섞어서 마신다 

~_~

이날 오전엔

요지야 카페를 시작으로

철학자의 길을 걷고

은각사 까지

갔다

완벽쿠한,,,,

코스가 아닐수 없다

:-)

대 추천~~~

위치는 

요기용

그럼 

이만 

뿅!

백준 

2003번

수들의 합 2

문제 풀이 

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

친구의 도움으로

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

투포인터는

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

이 문제로 보면 합을 더해진

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

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

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

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

되어 있다.

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

시작하는 문제로

좋은것 같당

:)

그럼

이만

뿅

안녕하세요!

오랜만에 글쓰네요

이번에 17년도 12월 21일~24일동안

교토에 다녀왔어요

오사카는 전에 가본적이 있는데

교토의 고즈넉~_~한

분위기를 즐기고 힐링하고 싶어서

교토를 다녀왔어용!

그래서 일본일본한 분위기를 더 느끼고싶어서

숙소를 료칸을 잡았는데 

(현대식 료칸)

대대 만족이라서 추천해 드리고 싶어서

오랜만에 포스팅 하네요 ㅎㅎ

숙소는

교마치야 료칸 사쿠라 우루쉬테이

예용!

위치는 처음엔 좋은지 몰랐는데요.. 

교토 관광을 하다보니 정말 좋은 위치인걸 알았어요

니시키시장 걸어서 8분정도

청수사 걸어서 20분정도

기온거리도 걸어서 20분정도

지하철역 걸어서 7분정도

ㅎ_ㅎ.. 처음엔 몰랐는데 

청수사와 기온거리가 너무 가까워서

깜짝 놀랐어요!

그리고 지하철역도 엄청 가까워서 

여러가지로 편했답니당

처음에 딱 료칸 안에 들어가면 이런식으로

인테리어가 되어 있어요

인상깊어서 사진을 찰칵찰칵

다행히 데스크에서 영어는 다통하고요~

그리고 미리 이것저것 설명도 많이 해주세요

특히 좋았던건 

지도를 주시면서 

주변의 맛집이나 좋은 이자까야도 소개해주셨어요

그래서 저희는 첫날 저녁에 

지도에 나온 이자까야가서

가볍게 한잔했답니당 :)

다른 료칸이랑 다른건

우선 탕은 없고요

탕이 1층에 있는데

40분에 500엔정도 내시면 이용할수 있었어요

저희는 안했..

숙소를 딱!! 들어갔는데

너무너무 만족쿠...

침대가 있는 방도 있었는데

저는 일부로 다다미방으로 선택했어용 ㅎㅎㅎ

잘한듯

그리고 진짜 일본호텔은 엄청 조그맣잖아요 

그런데 방크기도 엄청크고!!

특히!!!

화장실이 엄청엄청 넓었어용

(아쉽게 사진은 ㅠㅠ...)

화장실도 넓고 깨끗하고

그리고 일본호텔 화장실 진짜 조그마한데

지금까지 갔던 

일본 화장실중에 가장 넓어서

대대 만족 ㅎ_ㅎ!!!!

그리고 료칸이라 유카타도 있고요

정말 현대식 료칸이라는 말이 딱!

어울리는 숙소 였어용

그리고 넘나 좋은..조식도 주었어요

조식은 그전날 미리 신청하면 된답니당 ㅋ_ㅋ

조식 메뉴판!!

저는 1000엔짜리 연어구이가

나오는 밥을 시켰어용~

맛있으니깐 두장!!

ㅠ_ㅠ 넘나 맛났어용 bbb

가시면 조식은 꼭 드셔주세용...

가격은 저희는 2박에 둘이서

37000엔이었어요!

1000엔짜리 조식 *2 해서

39000엔이요!

그래서 37만원 조금 넘었던거같아요!! 

(엔화가 이때 넘나싸서 ㅎㅎㅎ)

위치는 여기예용~

교토 숙소를 

료칸으로 원하시면

강추!!

그럼 이만

뿅!

동적 프로그래밍(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 보다 큰지만 체크해주면 된다! ( 그전에 구한 값인가~?)

이렇게 하면 쉽지만...

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

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

그럼 이만

뿅!