IT's me

알고리즘 기초 문제 - 하얀 칸, 방 번호, 알파벳 개수, 카이사르 암호, 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. 메인

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

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

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

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

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

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

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

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

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

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

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

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

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

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

01. 초기화, 변수 선언

02. BFS 알고리즘

03. 메인

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

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

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

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

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

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

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

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

효율적인 해킹 , 시간 초과

01. 변수 선언, 초기화

02. bfs 알고리즘

03. 메인 함수

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

01. 변수 선언

02.  DFS 알고리즘

03. 메인

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

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

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

동적 계획법 알고리즘 기초문제 - 동전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의 경우에는 원리를 이해만한다면 어느정도 풀기가 수월하지만

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