영감을 (inspire) 주고픈 개발 블로그

문제 * input 10[ab] * output abababababababababab * * input a3[b2[c]v] * output abccvbccvbccv 압축한 문자열을 원본 문자로 바꿔주는 알고리즘이다. 들어올 수 있는 단어는 숫자[0 - 9] / 대괄호[] / 소문자 [a-z] 이며 [] 안의 문자를 앞의 숫자 만큼 출력하는 식이다. 주의할 점은 대괄호 안에 대괄호가 있을 경우 안쪽의 문자를 중복으로 풀어야하므로 까다로울 수 있다. 처음엔 숫자랑 문자를 따로 스택에 저장하면서 처리하려고 했는데 오히려 그러면 인덱스 맞추는 부분에서 어려울 수 있어서 구현이 어려웠다. 스택에 들어갈 문자열을 continueStrBuilder 로 하고 isPrevNumber 값을 통해 continueStrBui..

반년 정도 꾸준히 풀다보니 BOJ에서 151문제를 풀었다. 막판엔 갑자기 랭킹에 욕심이 생겨서 쉬운 문제를 몰아서 푼 것도 있지만 나름 뿌듯하다. 랭킹도 1000위 안에 들었다. 작년 말까지만해도 꿈꿔보지도 못한 일이다. 이제 좀 더 어려운 문제 좀 고민해봐야겠다.

https://www.acmicpc.net/problem/2374 https://www.acmicpc.net/problem/13146 프로그래밍 문제를 접근할 때 가장 중요한건 문제를 단순화 시키는 것이다. 이번 문제를 간단히 해보면 가장 낮은걸 수를 가장 높은 수와 같게 만드는 것이다. 이 때 연속된 이웃이 같으면 같이 올라가야한다는 조건이 붙는다 같은 수로 만들기는 두 가지로 풀었다. 위의 문제에서 첫번째는 재귀를 이용한 divide and conquer 접근했고 두번째 문제는 stack을 이용한 방법으로 접근했다. 처음 떠오른 아이디어는 범위내(오름차순, 혹은 내림차순을 방해하는 걸로 짤라서)에서 가장 큰 수와 가장 작은 수를 맞추는 식으로(divide and conquer) 했고 첫번째 제약조건은..

알고리즘 문제를 풀다보면 소수 판별에 대한 개념이 많이 나오곤 한다. 소수는 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수로 정의된다. 규칙성이 증명이 안되서 참 난해한 부분이 많다. 정수론에서 매우 중요한 역할을 담당한다. 이진코드나 수학적 특성을 이용한 알고리즘 문제를 풀 때 생각보다 많이 사용되어서 정리해보자 참고 사이트 : 코드와 함께 정리가 잘 되어있다. 이거보다 잘할 자신이 없어서 문제풀이만 올린다. http://ledgku.tistory.com/61 요약 하자면, "모든 자연수는 소수들의 곱으로 표현된다." 1. 소수는 구하고자하는 값의 root 만큼만 체크하면 확인 가능하다.(에라토스테네스의 접근) * 연산 횟수 sqrt(n-2) 2. 구하고자 하는 수 이하의 배수 값을 저장하면서 걸..