LIS(Longest Incresing Subsequence) 개요 최대증가수열 문제는 Dynamic Programming을 공부하기에 좋은 문제 중 하나로 잘 알려져 있다. 백준에서는 가장 긴 증가하는 부분수열 이라는 카테고리로 따로 다루고 있을정도로 문제의 변형도 많은 듯 하다. 가장 긴 증가하는 부분 수열 수열 A=[1, 5, 2, 4, 7]이 있을 때, [1, 2, 4]는 A의 부분 수열이다. 부분 수열에 포함된 수가 순 증가 (strictly increasing)하면 이 부분 수열은 증가 부분 수열 이라고 한다. LIS는 수열이 주어졌을때 이러한 증가 부분 수열 중 가장 길이가 긴 수열을 찾는 방식이다. 아이디어 완전 탐색 가장 먼저 떠오른 아이디어는 완전탐색이다. 모든 경우의 수를 따라 어딘가..

주간 리뷰 이분 탐색문제를 열심히 풀었다. 그래프 같은 것들은 구현의 빈도가 높았지만, 정렬, 탐색 문제를 풀이해보면서 느낀 점은 수학적 사고력을 요구하는 문제 또는 수학적으로 풀이할 경우 구현이 간단해지는 경우가 많았다. 당연하게도,, JS와 JQuery에 대한 책을 읽고, 실습하였다. 사실 단독망 안에서 개발 연습을 하려고 산 책인데, 당일날 단독망 서버가 나가서 못해봤다. 책은 크게 두개의 파트로 나뉘어 있는데 자바스크립트의 문법 파트는 어렵지 않게 읽었다. 책을 읽으면서 "인수인계 페이지"를 만드는것이 목표이다. 목표를 위해서는 JS/JQuery 이외에도 CSS 같은것들을 배울 필요가 있을거 같은데 프론트는 이렇게 각잡고 해보는것이 처음이라 아직 감도 안온다. 또한 서버를 만질수 없는 상황에서 데..

구현(Implement) 개요 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제들이 많다. 또한 문제가 길거나, 문제의 조건이 많은 것들이 구현으로 구분된다. 구현 문제는 프로그래밍 문법의 숙지가 미흡하거나, 라이브러리 사용 경험이 부족하면 문제 풀이가 더욱 어렵다. 예를 들면 순열을 구현해야 하는 문제에서 C++의 STL을 모르거나 PYTHON의 itertools를 모른다면 생짜로 구현해야 하는 상황이 올 수도 있는것이다. 구현 문제에서는 다른 것 보다 특히 메모리 제약사항을 눈여겨 보아야 한다. C언어라면 정수의 표현 범위일 것이며, 파이썬이라면 리스트의 크기 정도가 될 수 있다. 대체로 문제에서는 128~512MB의 메모리..

그리디(탐욕 알고리즘) 개요 최적해를 고르는 근사적인 방법 이며, 지금 당장 좋은것만 고르는 알고리즘이다. 해당종류의 알고리즘은 응용이 많아 단순히 암기로 풀이하기 어렵다. 따라서 많은 문제를 풀어보는 것이 좋으며, 특히 다른 알고리즘과 접합하여 문제가 나오면 난이도가 높아진다. 특히 정렬 알고리즘과 접합하는 경우가 많은 것 같다. 또한 알고리즘 구현 과정에서 문제풀이에 아이디어를 제시하고 아이디어가 정당한가 검증할 수 있어야 한다. 마지막으로 최적해를 고르는 것이지 항상 그것이 최적인 방법은 아니다. 즉, 그리디를 이용해 문제를 풀이 할 수 있으려면 다음의 두가지 조건을 만족해야 한다. 탐욕스러운 선택 조건 (Greedy Choice Property) 앞의 선택이 이후에 영향을 주지 않는다. 최적 부문..

개요 파이썬으로 코딩테스트를 준비하면서 공부한 알고리즘 내용을 내가 알기 쉽게, 남에게 설명하듯 작성하고, 많은 문제를 풀이하고, Write-Up을 작성하고, 적은 경험이지만 남들에게 공유하고 싶다 라는 생각으로 만든 목적성 분명한 블로그입니다. 목표는 24년 SW-Maestro 합격이고, 이를 위해 각종 알고리즘을 공부중이며, 각 알고리즘마다 Solved.ac 기준 GOLD III을 무리없이 풀이할 수 있다면 다음 알고리즘을 넘어가는 방식과, 이를 달성하기 위한 목표 시간을 설정하여 공부중입니다. 공부 순서는 다음과 같습니다. GREEDY (그리디) IMPLEMENT (구현) DFS / BFS (그래프 탐색) MST (최소 스패닝 트리) SEARCH (탐색) BINARY_SEARCH (이분 탐색) 이후..

길다면 길었고 짧았다면 짧은 4월이 지났다. 처음 소마에 지원하기로 마음먹은 이후 가장 먼저 실행에 옮긴게 코딩테스트 준비였다. 맨날 미루기만하다가 처음으로 책을 사보고, 알고리즘 하나하나를 격파해나가는 재미가 있었다. 또한 말로만 결심한게 아니라 1달 (근무가 있던날을 제외) 하고는 내내 1문제 이상 고민하며 풀어냈다. (사실,, 근무가 있던 날도 슬쩍 풀이 한 적도 있다.) 4월에 공부한 알고리즘 중 가장 성과가 높았던 것은 아무래도 그래프 이론이었다. 4월 한달의 대부분 이상을 BFS/DFS 구현과 일부 백트래킹, MST와 Disjoint-Set을 공부하고 문제를 풀이하는데 시간을 많이 들였다. 1개월 동안 73 문제를 풀이했으며, 하루에 2-3문제 정도씩 꾸준하게 풀이 했다. 또한 골드 문제와 일..