IT's me

BFS 알고리즘 - 효율적인 해킹 문제 (백준)

하.... 런타임 에러 찾느라고 밤을 꼬박 샌 문제..

결국에 찾긴 했는데 정말 사소한 문제라 더더 기억에 남을만한 문제이다.

런타임 에러 문제를 해결하고 나니 시간초과.. 정답률도 상당히 낮은 나름 어려운 문제였지만

BFS 문제를 상당히 오랜만에 풀어본 것도 나름 원인중 하나였던 것 같다.

효율적인 해킹 , 시간 초과

01. 변수 선언, 초기화

02. bfs 알고리즘

03. 메인 함수

런타임 에러가 난 이유는 내가 큐를 읽고 쓰는 데에 wp, rp라는 변수를 통해서 접근을 했다.

큐를 한번 쓰고 다시 쓰기전에 이 변수들을 초기화해줘야 하는데 이 부분을 잊어 버렸다..

때문에 이 변수들이 큐의 범위를 넘어서 버린 것... 하.... 이것 때문에 몇시간을 고민했는지..

암튼 이 문제를 풀기위해 생각한 방법은

먼저 모든 컴퓨터 목록을 배열에다가 저장하고,

1번 컴퓨터부터 차례로 큐에 넣은 다음 연관있는 모든 컴퓨터들을 큐에다 넣고 조사하는 방식을 선택했다.

이렇게 문제를 풀면서도 상당히 비효율적이라 생각이 들어서 동적 계획법을 살쩍 섞어 볼까도 생각했었다..

하지만 조합하는 도중에 포기하고 원래 방식대로 모든 목록을 순회하는 방식을 사용..

역시나 시간초과.. 다른 이들은 어떻게 풀었나 궁궁해서 슬며시 찾아보니.. 

벡터를 사용한 기가막힌 방법이 있어서 그 방식을 연구해보았다.

다음 포스팅에서 벡터로 이 문제를 멋지게 해결한 방법을 알아보겠다.

DFS 알고리즘 - 순열 사이클(백준)

딱 봐도 DFS 알고리즘으로 풀면 쉽겠다.. 했는데

요즘 BFS알고리즘을 너무 안했다 싶어서 BFS로 도전했다가

2시간 고전끝에 풀지못하고 결국엔 DFS로..

문제를 다 파악하고 난 뒤라 그런지 10분 컷

01. 변수 선언

02.  DFS 알고리즘

03. 메인

DFS는 내가 생각하는대로 함수를 구성하면 짧고 쉽게 풀리는 반면

BFS는 큐도 만들어야 하고.. 코드도 상대적으로 길고.. 위와 같이 깊이를 우선적으로 탐색해야하는

문제에서는 적용하기가 힘든것 같다. 아직 BFS문제를 많이 안풀어본 것 또한 문제 중 하나

that thing you do (댓 씽 유 두)

오늘 소개할 영화는 우리가 너무 잘 알고 있는 톰 행크스가 나오는 댓 씽 유 두

한 줄로 소개를 하자면 시골의 촌뜨기 밴드가 유명한 밴드로 성장해 나가면서 겪는 갈등을 그린 영화?

사실 이 한 줄만 읽는다면 진부하고 뻔한 그런 성공스토리를 그린 영화구나.. 할 수 있지만 뭔가 특별한 것이있다.

사실 이 영화에서 톰 행크스의 비중은 그리 압도적이지 않다. 영화를 보고나서 가장 기억에 남는 사람은

드러머 역할을 했던 톰 에버렛 스콧!!(이 영화를 통해 첨 알게된 배우) 사실 이 영화의 가장 비중있는 주인공이라 할 수 있다.

다소 촐싹거리는 이미지를 가지고 있지만, 영화에서 상당히 매력적으로 나온다..

남자가 봐도 정말 멋있다고 할 정도.. ㅋㅋ

밴드의 보컬을 맡은 조나슨 스케치라는 배우.. 사실 영화에서도 그리 매력적으로 나오는 것도 아니고

유명한 배우도 아닌 것 같지만.. 이 영화의 주제곡 that thing you do를 부르는 보컬로 나오는데

사실 이 배우가 실제로 부른건지는 잘 모르겠지만.. 이 사람이 부른다 생각하고 봤더니 상당히 매력적이더라

그도 그럴것이 이 영화의 가장 특별한 점이라면 이 영화의 OST이기 때문이다.

극단적으로 표현하면 이 영화는 that thing you do라는 노래로 시작하고 이 노래로 끝이 난다.

무슨 대단한 노래길래 이러나 싶겠지만.. 막상 들어본다면 제목은 모르지만 아! 이노래! 하면서 나도 모르게 흥얼거리고 있을 것이다.

노래가 영화 도중에 상당히 많이 나오는데 나올 때마다 사람을 설레게하는 매력을 가진 곡이다.

영화를 보면서 끝으로 갈수록 '뭐 이런 개막장이 있어'라고 생각한 부분도 있는데

가장 마지막 부분을 본다면 나도 모르게 수긍하게된 그런 영화이다.

아무튼 이 영화 풋풋한 청춘 영화의 색을 띄고 있고, 설레는 OST까지 있으니 한번 쯤 꼭 보길 바란다.

매우 주관적인 별점 3.5/5.0

Maxwell - this woman's work

상당히 좋아하는 가수 중 한명인 맥스웰

네오소울이라는 다소 호불호가 갈리는 장르를 대표하는 아티스트 중 한명

우리 나라에서는 가수 정엽과 상당히 스타일이 비슷하다고 보면 된다.

그의 노래 중 this woman's work라는 곡을 소개할텐데

이 노래는 정말 옛날 가수이자 영국의 싱어송 라이터 케이트 부시의 곡을 리메이크 한 것이다.

어느 순간부터 가성을 쓰는 남자 가수가 상당히 섹시하다고 느껴졌는데

맥스웰의 노래를 듣고부터 그런 생각이 든 것 같다.

[자료구조] 이진 탐색 트리의 이해(1)

이진 탐색 트리는 말 그대로 탐색에 특화된 이진 트리이다.

앞서 이진 트리를 공부했기 때문에 이해와 구현이 어렵진 않겠지만,

기본적인 기능인 삽입, 삭제, 참조 중 삭제의 구현이 까다롭다.

왜 까다로운지, 어떻게 구현하는지는 차차 알아가 보도록하겠다.

이진 탐색 트리는 이진 트리의 확장 버전이라고 생각하면 된다.

이진 탐색 트리 = 이진 트리 + 데이터의 저장 규칙    ( 저장 규칙은 곧 탐색 규칙이라 말할 수 있다. )

위의 트리는 이진 탐색 트리를 나타낸 것이다.

루트 노드보다 작은 쪽은 왼쪽으로, 루트 노드보다 큰 쪽은 오른쪽으로라는 단순한 저장 규칙이다.

자세히 보면 꼭 루트노드가 아니더라도 어떠한 노드를 찍었을 때 왼쪽은 현재 노드보다 값이 작고 오른쪽은 크다.

정리하자면

1. 이진 탐색 트리의 저장된 키는 유일하다.

2. 루트 노드의 키 > 왼쪽 서브 트리의 루트 노드의 키

3. 루트 노드의 키 < 오른쪽 서브 트리의 루트 노드의 키

4. 왼쪽과 오른쪽 서브트리 또한 이진 탐색 트리이다.

지금까지의 내용은 이진 트리에서 간단한 규칙하나만 적용되었을 뿐이다.

하지만 이 간단한 규칙에 의해 탐색에 엄청난 효율을 가져올 수 있는데, 그 구현은 다음 포스팅에서 다루도록 하겠다.

3 doors Down - Here Without you

우연히 접하게 된 노래인데, 요즘 이 노래만 듣고 사는 것 같다..

이런 가수가 있는지도 몰랐는데 이 노래가 WWE 월드스타 에디게레로의 추모곡이란다..

잔잔한 락풍의 노래같은데 상당히 애잔하게 들린다.

한 때 좋아했던 트랜스포머의 OST The Fray - Never say Never과 비슷한 느낌도 있고

상당히 좋아하는 에어로스미스와 느낌이 비슷한 거 같아 한번 듣고 완전 꽂혔던 거 같다.

수 많은 커버곡을 들어보았지만 역시 원곡자가 최고

동적 계획법 알고리즘 기초문제 - 동전1 (백준)

기존에 풀어오던 동적 계획법과 조금 다른 방식으로 접근을 해야해서

시간이 조금 오래걸렸다. 알고리즘을 오랜만에 풀어서기도 하겠지만

여전히 점화식을 세우는 것이 상당히 어렵게만 느껴진다.

이번 문제는 동전을 주고 해당하는 값을 이 동전으로 채울려면 몇 개의 경우의 수가 있느냐이다.

문제는 1,2,5원이 주어지고 10원을 채워야할 때 과연 경우의 수가 얼마인가.. 였다..

문제를 딱보자마자 dp배열에 다 때려박은 다음에 10원까지 쭉올라가다보면

답이 알아서 나오겠구나.. 생각했다..

기존에 동적 계획법을 풀때에는 답을 찾은 dp배열은 다시 건들지 않았다.

하지만 이번 문제는 답을 한번에 찾고 넘어가는 것이 아니라

다시 돌아와서 갱신을 해가면서 풀어야 한다는 것이다.

물론 기존에 찾은 답을 바탕으로 현재의 답을 찾는다는 동적 계획법의 기본은 충실하면서

동적 계획법 알고리즘 기초문제 - 동전1 (백준)

처음 들었던 생각은 1,2,3,4,5.... 차례로 쭉올라가면서 해당되는 값의 경우의 수를 찾아내고

그 수를 바탕으로 어떠한 점화식을 세운다면 답이 수월하게 나올줄 알았다.

하지만 값이 점점 커질수록 사용되는 동전의 수가 늘어나고 어떠한 규칙에도 예외가 생겨버렸다..

이 규칙을 찾으려 상당히 오랜시간을 고민했다. <-- 틀에 박힌 사고의 문제점

이 문제의 해답은 바로 dp배열을 점차 갱신해가며 답을 찾아 나간다는 것!

1,2,5원의 동전이 주어졌을 경우를 예로들어 설명을 하면

1. 1원 밖에 주어지지 않았을 때 1~k 값을 채울 수 있는 경우의 수를 구한다.

2. 2원 밖에 주어지지 않았을 때 2~k 값을 채울 수 있는 경우의 수를 구한다.

3. 5원 밖에 주어지지 않았을 때 5~k 값을 채울 수 있는 경우의 수를 구한다.

5원 밖에 주어지지 않았을 때 5원 이하의 값들은 5원의 영향을 받지 않기 때문에 제외.

하.. 동적 계획법은 정말 수학적 머리가 타고나야 하는 것 같다.

DFS, BFS의 경우에는 원리를 이해만한다면 어느정도 풀기가 수월하지만

동적 계획법은 공부를 하면 할수록 더욱 어려워 지는 것 같다..

Mikky Ekko - Stay

Disappear 이라는 곡으로 알게된 가수 미키에코

다소 몽환적인 노래가 많은 터라 매니아 층만 안다는 그런 가수이다.

Disappear 또한 상당히 몽환적인데.. 내 생각엔 호불호가 정말 심하게 갈릴듯 하다.

그의 노래 중에서도 상당히 유명한 노래가 있는데 (미키에코의 노래라기 보다 리아나의 노래)

리아나와 같이 부른 Stay라는 곡이다. 리아나의 버전과 미키에코의 버전이 있는데

개인적으로는 미키에코의 버전을 훨씬 더 선호하는 편이다.

또 하나 내가 이 노래를 정말 좋아하는 이유는 가사 때문인데

Not really sure how to fell about it

어떻게 그런 감정을 느끼는지는 모르겠지만

something in the way you move

너의 움직임은

make me feel like i can't live without you

너 없이는 내가 살 수 없을 것 처럼 느끼게 만들지

it take me all the way

그것은 나를 완전히 사로잡아

i want you to stay

난 네가 머물기를 원해

해석을 어떻게 하느냐에 따라 다르겠지만, 이 후렴부분과 더불어

전체적인 가사가 상당히 시적인 느낌