# 개요 프로그래머스를 처음 알게 된 것은 2017년 카카오 페스티벌로 처음 알게 됐습니다. 당시 신생 플랫폼인데다가, ICPC 스타일이 아니라 정해진 함수 포맷을 구현하는 문제는 처음 봤기 때문에 거부감이 상당히 강했습니다. 비단 저 뿐만 아니라, 같이 공부하던 분들도 모두 처음 보는 플랫폼에 대한 막연한 거부감이 생겼습니다. 하지만, 복학 이후에 사실상의 메이저 플랫폼이 되어있었고, 상당히 많은 기업에서 자사 코딩테스트 플랫폼으로 채용하게 되었습니다. 때문에 저도 프로그래머스에서 진행하는 여러 대회/채용에 지원하게 되었고, 프로그래머스에서 진행한 채용 프로세스에 합격하여 결국 취업에 성공하게 되었습니다. # 문제 C++로 ps를 쭉 해왔는데, Java에 더 익숙해 지기 위해 최대한 Java8의 Str..
lv.2는 레벨 편차가 엄청 심했던 것 같습니다. 최대한 Java Stream을 활용하려 했는데, Stream사용 시 시간초과가 나는 등 Java언어 자체를 고려하지 않고 만들어진 문제들이 많이 있어서 제대로 활용하지 못 했습니다. 아직 lv.2에 sql문제들이 남아있지만, DB공부를 3월부터 시작할 예정이므로 그때 부터 풀어볼 생각입니다. lv.3부턴 진짜 알고리즘이 사용될 건데, Java로 어떻게 효율적으로 구현할 지 고민해볼 생각을 하니 너무 설렙니다!
입사까지 남은 시간이 5개월인데, 완전히 알고리즘을 손 놓고 있기도 뭐 하고, 그렇다고 잡고 있기도 그래서 Java로 문제들을 풀기로 결정했습니다. 백준 문제들은 풀어본 문제도 많거니와, Java로 하면 실제 로직을 짜는 코드보다 입출력을 건드리는 코드가 더 길 정도로 입출력이 귀찮아서.. 프로그래머스를 밀기로 결정했습니다. 원래 프로그래머스에서 해결한 문제가 3~4문제 정도로, 프로그래머스를 딱히 안 좋아해서 문제 풀어보지도 않았는데... Java로 하기에는 훨씬 편하네요. 입출력이 필요없으니까. 최대한 함수형으로 해결하기 위해서 연습하려고 lv.0부터 시작하여 lv.1까지 다 풀어봤습니다. lv.0과 lv.1 각각 12시간 정도 걸렸는데, 특히 초반에 배열(array)를 Stream으로 다루기 위해서..
얼마전 LCS5 문제를 푼게 크게 작용했다. 딱 1점 남았었는데, class 7번에 까지 딱 1문제 남았었고, 에센셜 문제 하나 보자마자 maximalFlow생각나서 예전에 작성해놓았던 템플릿 이용해서 풀었다. 아직 전성기 시절 두뇌회전의 반도 못 따라가고 있으니 더 분발하자.. 제발
[개요] 3학년 1학기 텀 프로젝트 주제로 식당 테이블 예약 앱을 만들기로 했다. Demo앱처럼 지도 api 넣어서 지도위에서 마커 누르고 하는 것 보다, list형식으로 쭉 띄워주는게 훨씬 보기 좋고, 그게 맞는 방향이라 생각 해서 그 방식으로 진행하려 했다. 단순히 geolocator로 현재 위치를 뽑아오고, 그 위치를 google map api로 넘겨서 주변 식당 list를 쭉 뽑아온 뒤 작업을 하려 했는데 여러 가지 문제가 발생했다. [문제] 1. google map api에서 fetch해 올 수 있는 주변 식당 list는 최대 60개다. 최대 60개라고는 하지만, test해보니 40개 밖에 안 되는듯 하다. 사실상 40개면 이 api를 이용해서 앱 개발은 불가능 하다고 봐야한다. naver나 k..
BOJ2401 약 2주일간 고생한 문제다. 해법은 kmp + dp로 간단한 편이나 시간초과가 날 리가 없는 시간복잡도인데 시간초과가 나버린다. 며칠간 생각해봐도 이 이상의 풀이를 생각해내기가 불가능하다고 판단해서 풀이를 봤는데, 풀이도 똑같은 풀이를 썼다. 한 주간 이것 저것 막 해보다가 발견해낸 차이점은 각각의 index에 matching된 문자열의 길이를 vector로 관리한 코드들은 전부 시간초과가 뜨고 배열로 관리한 코드들은 전부 ac가 됐다는 점이다. 이론상 push_back의 속도는 O(1)이지만 이게 Amortized O(1)이라는 점이 중요하다. 최악의 경우에는 O(n)의 시간복잡도를 갖기 때문에 함부로 O(1)이라고 판단하면 안 된다. 그래서 검색해보니 vector의 reserve를 사용..
1. suffix array설명은 갓-crocus 블로그가, lcp설명은 plzrun 블로그가 제일 정리가 잘 되어있다. 2. suffix array의 존재이유는 lcp를 위해 있다고 해도 과언이 아니다. 3. O($nlogn$)만에 구하는 알고리즘도 있다. O($nlog^2n$) 알고리즘보고 오 기수정렬이랑 비슷하다 생각했는데 역시 radix sort를 이용한단다. 자료구조수업때 한번 본 이후로 처음 보며 처음 써본다. 제대로 이해하기 위해서는 radix sort를 다시 봐야겠다. 설명은 plzrun 블로그. 4. lcp가 이용되는 대표적인 문제는 BOJ_가장 긴 문자열 이다. 한 문자열에서 두 번 이상 나오는 문자열을 포함하는 suffix는 suffix array에서 항상 인접하고, lcp의 정의에 ..
