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. 다이나믹

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

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

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