개발과 일상

재귀(再歸)란? 주어진 문제를 해결하기 위하여 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식. 어떤 루틴이나 프러시저가 자기 자신을 반복적으로 호출하여 문제를 풀어 나가는 알고리즘으로, 이를 이용하기 위해서는 스택을 사용한다. 간단한 루틴을 풀 수 있지만, 처리 속도가 느리고 횟수가 지나치게 많으면 프로그램이 정지하기도 한다. - 네이버 사전 재귀 문제의 대표적인 예로는 피보나치 문제가 있다. 위의 인용에서도 언급하고 있지만, 재귀라는 방식 자체가 시간복잡도를 줄여주는 방식은 아니다. 그러나 메모이제이션이라는 방식을 통해 중간 결과를 저장해두는 방식으로 처리한다면, 계산 횟수를 많이 줄일 수 있다. 또 다른 방법으로는 조건문을 통해서 불필요한 가지를 쳐내는 방식으로도 계산횟수를 줄인다. 이번..

백준에서 코테 문제를 풀다보면 느끼겠지만, 입/출력 쪽에서 시간 초과가 자주 발생한다. (분명 알고리즘은 맞았는데, 계속 시간초과가 나면 대부분 이 문제다..) 각각 어떤 곳에서 문제가 발생하는지 파헤쳐보자. 입력 문제 입력에 문제가 생기는 경우는 대부분 Scanner를 써서 여러번 next()나 nextInt()으로 가져오는 경우다. 입력에 문제가 생겼던 문제는 탑 이었다. 50만번은 딱히 많아보이지 않는 갯수이다. N번 정도는 그냥 하면 되는거 아냐? 라고 생각할 수 있겠지만 next의 코드를 따라가보면 문제가 있다는 걸 알 수 있다. public String next(Pattern pattern) { ensureOpen(); if (pattern == null) throw new NullPointe..

멘토링 준비도 할 겸해서 코딩 테스트 고수 지인 분의 도움을 받아 코딩 테스트 문제를 조금씩 풀고 있다. 솔직히 피곤하고 힘들지만 한달간 꾸준히 푼 결과 solved.ac에서 측정하는 레벨이 꽤나 올랐다. 어떤 카테고리부터 푸는게 좋을지 고민 중이었는데, 스택을 추천 받았다. 그런데, 스택 코딩 테스트 문제는 일반적인 자료구조 사용법과 같이 만만하지 않았다. 브론즈부터 벽을 좀 느꼈달까 문제를 푼 순서는 다음과 같다. 1. 막대기 : https://www.acmicpc.net/problem/17608 2. 괄호 : https://www.acmicpc.net/problem/9012 3. 탑 : https://www.acmicpc.net/problem/2493 4. 스카이라인 쉬운거 : https://www..