IT's me

BFS 알고리즘 문제 - 숨바꼭질 (백준)

처음에는 DFS로 풀어보았는데 시간초과를 극복 할만한 대안이 떠오르지 않았다.

문제 자체가 최단으로 도착하는 방법을 찾는 것이기 때문에 BFS가 더 적합한 것 같다.

숨바꼭질 (백준) - BFS

01. 초기화, 변수 선언 등

02. 함수들

03. BFS 알고리즘

04. 메인

이제 BFS, DFS 알고리즘을 활용하여 간단한 퍼즐 게임을 만들어 보려한다.

위의 두 알고리즘이 퍼즐게임의 핵심 알고리즘으로 활용될 수 있을 것 같아

예전부터 꾸준히 공부해왔는데, 이제 실제로 활용해 볼 때가 된 것같다.

알고리즘 기초 문제 - 하얀 칸, 방 번호, 알파벳 개수, 카이사르 암호, KMP (문자열)

간만에 문자열 문제를 풀어보았다. 어려운 문제는 아니고 어려운 알고리즘 푸는 데에 지쳐

잠시 쉬어가는 시간으로 간단한 몇 문제를 풀어보았다.

01. 하얀 칸

02. 방 번호

03. 알파벳 개수

04. KMP

05. 카이사르 암호

쉬운 문제로 기분 업~~

문자열 , 스택 알고리즘 문제 - 문자열 폭발 (백준)

단순하게 여러번 비교하면 되겠지 했는데, 수행시간이 엄청 걸리겠더라

그래서 이런 저런 방법을 생각해보다가 스택이라는 힌트를 보고 스택을 활용해보았다.

만약 힌트를 안봤다면 절대 스택을 생각하지 못했을 것이다..

스택이란 아이디어를 얻고 술술 풀어나갔는데 예상치 못한 컴파일 에러..

원인을 찾는다고 상당히 오랜시간을 고민한 것 같다.

문제의 원인은 string의 pop_back()을 쓰는 부분이었다.

C++14에서는 pop_back()를 지원하나, C++은 이 부분에서 컴파일 에러가 났다.

string또한 vector와 같은 라이브러리로 생각하고 있는 나로써는 당황스러운 부분이었다.

아무튼 이 문제의 핵심은 스택의 원리를 이용하는 것이다!!

문자열, 스택 알고리즘 문제 - 문자열 폭발 (백준)

01. 변수 선언

02. 폭발 문자열 찾기

03. 메인

알고리즘을 풀면서 지금까지 큐는 상당히 많이 활용했으나, 스택의 활용은 기억이 없다..

스택의 원리를 잘 이해하고 기억했다가, 이 원리를 코드에 활용할 수 있도록 해야겠다.

동적 계획법 기초문제 - 파도반 수열(백준)

점화식 세우는 것이 정말 간단하다..

동적 계획법 문제를 풀 때는 항상 많은 고민을 하는데

이 문제는 딱 보자마자 점화식이 나와서 기분좋게 풀려하는데

자꾸만 틀렸다라는 문구가 나왔다..

혹시나 수가 커지면 다른 공식에 대입해야 하는 것은 아닌가.. 해서

어느정도까지 노트에 적으면서 계산까지 해봤지만 도무지 틀린 곳이 없었다..

문제는 DP배열은 int로 선언했다는 것!

N을 100으로 하면 888855064897이라는 답이 나오게 되는데

이 큰 수를 int에 넣을 수 있을리가 없다.. 이렇게 쉬운 문제가 정답률이 낮은 이유는 바로 이 때문이라 생각한다.

동적 계획법 기초 - 파도반 수열(백준)

01. 다이나믹

동적 계획법(다이나믹 알고리즘)은 코드가 짧은 대신 수학적인 사고력이 필요하기 때문에

쉬운 문제부터 차근 차근 풀어나가면서 수학적인 접근방식에 익숙해질 필요가 있다고 생각한다.

다음 포스팅부터는 난이도를 좀 더 올려서 진행해 보도록 하겠다.

BFS 알고리즘 문제 - 유기농 배추 (백준)

정말 전형적인 BFS알고리즘 문제인 것 같다.

BFS를 처음 공부할 때 풀었던 문제와 좀 흡사해서 금방 풀 수 있었다.

DFS로 하는 것이 더 간단해 보였는데, BFS를 공부중이기 때문에 넓이 우선으로 풀어보았다.

유기농 배추 - BFS 알고리즘

01. 변수 선언

02. 초기화, 인큐, 디큐 등등

03. BFS

04. 메인

항상 이런문제는 이차원 배열의 x,y좌표 때문에 헷갈렸는데

이번에도 초기화를 할 때 x,y를 반대로 입력해서 조금 고전했다..

항상 느끼는 거지만 문제를 꼼꼼하게 읽어보도록 하자.

동적 계획법 기초 문제 - 캥거루 세마리 (백준)

왜 이 문제가 동적 계획법 기초 문제에 있는거지..?

캥거루 세마리(백준)

01. 메인

동적 계획법 기초문제에 있었기 때문에 

양 끝에 서있는 캥거루 중 어떤 놈이 먼저 뛰냐에 따라 달라지는 답을 저장해나가야 하나? 생각했는데

그냥 가장 넓은 구간으로 뛰면 끝이었다.

동적 계획법은 다른 알고리즘보다 수학적 사고력이 더욱 필요하다고 느꼈는데

그 부분 때문에 동적 계획법으로 분류된게 아닌가 싶다..(주관적인 생각)

James Bay - Move together

인터넷을 돌아다니다 우연히 들은 노래

라이브 영상이 마치 inside Lieuyn (인사이드 르윈)의

마지막 장면을 보는 것 같아 계속 보게되었는데 이 때문에 노래도 알게 되었다.

퇴폐미 은은하게 풍기는 가수와 신비함이 묻어나는 목소리가 잘 어울리는 듯한 노래이다.

[자료구조] 이진 탐색 트리의 구현(2) 삽입과 탐색

이번 포스팅에서는 이진 탐색 트리의 삽입과 탐색이 어떻게 구현되는지 알아보겠다.

앞선 포스팅에서 말했듯이 이진 트리의 함수들을 사용하여 이진 탐색 트리의 함수를 만들어보겠다.

코드로써 구현을 하는 것도 중요하지만, 어떠한 식으로 삽입과 탐색이 이루어지는가를

이해하는 것도 상당히 중요하기 때문에, 그 부분에 중점을 두고 이어 나가보도록 하겠다.

point -> 삽입과 탐색의 과정에서 데이터는 key값으로 사용된다. 즉 중복이 있으면 안된다!!

01. 이진 탐색 트리의 삽입과정 (출처 : 윤성우의 열혈 자료구조)

(1) 이진 탐색 트리의 특성상 자신의 왼쪽은 무조건 자신보다 작을 것이며

자신의 오른쪽은 무조건 자신보다 클것이다.

(2) 자신(루트노드)보다 작다면 왼쪽으로 보내고, 크다면 오른쪽으로 보내면된다. 간단한다.

(3) 이런식으로 위치를 찾다가 더 이상 비교대상이 없다면( 끝에 이르렀다면 ) 그 자리에 삽입되게 된다.

02. 이진 탐색 트리의 삽입 구현

03. 이진 탐색 트리의 탐색 구현

이진 탐색 트리의 삽입과 탐색의 과정을 구현해보았다.

1. 가장 중요한 것은 key값을 통해 삽입과 탐색을 진행한다는 것! 즉 중복이 있으면 안된다.

2. 기존의 이진 트리를 구현하는 데 썼던 함수들을 활용하여 구현을 했다는 것!

3. 현재의 노드의 왼쪽은 자신보다 작은 값이 들어가고, 오른쪽은 자신보다 큰 값이 들어가는 특징을 활용한다.

4. 코드로 이해하는 것도 중요하지만, 전체적인 알고리즘을 이해하는 것도 중요하다.

다음 포스팅에서는 이진 탐색 트리의 구현 중 살짝 난이도가 있는 삭제의 과정을 구현해보겠다.

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

모든 목록을 순회하면서 해당하는 컴퓨터와 연관된 모든 컴퓨터를

찾아 큐에다 때려박는 방법 대신, 초기화 할때에 연관된 모든 컴퓨터를

해당 벡터에다가 저장하는 방법으로 풀어보았다.

나는 왜 이런 생각을 못했을까.. 하고 열심히 풀었는데 런타임 에러..

한 시간동안 고민끝에 찾아낸 원인은 큐를 접근하려고 만든 wp,rp변수를

초기화하지 않아서 이 변수들이 큐의 범위를 넘어가 버린 것...

문제를 실컷 다 풀어놓고 이런 사소한 것들 때문에 시간을 허비하니 정말 허탈하다..

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

01. 초기화, 변수 선언

02. BFS 알고리즘

03. 메인

지금까지 BFS를 너무 단순하게 생각해왔던 것 같다.

상당히 쉬운 알고리즘으로 여겨왔는데, 조금만 어려워지니 정신못차리는..

꾸준히 하루에 한 문제씩이라도 풀어보면서 익숙해져야겠다..