DP 문제를 풀다보니 자주 등장하는 유형이 있어 구글링을 해보니 '최장 증가 부분 수열'이라는 유형이였다. # 최장 증가 부분 수열 (Longest Increasing Subsequence) DP 문제로 자주 나오는 유형 O(N^2)의 시간 복잡도 아니면 O(NlogN)의 시간 복잡도를 가진다. 어려운 문제의 경우 당연히 후자.. 개념 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것 어떤 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 '오름 차순을 유지하면 증가하는 부분 수열' 즉, 만들 수 있는 부분 수열 중 가장 길면서 오름차순을 유지하는 수열이 LIS 위의 여러 수열 중 가장 길이가 긴 수열은 [2,3,5,6,7] 뿐만 아니라 [1..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net # 조건 - 트리에서 리프노드란, 자식의 개수가 0인 노드 - 트리가 주어질 때, 노드 하나를 지울 것인데, 그 때 남은 트리에서 리프 노드의 개수를 구하여라 # 접근 방법 - 노드 하나를 지웠다면 아래 자식 노드들 또한 함께 지워지는 것이 규칙 - 따라서 지워지는 노드 기준, 아래로 연결되어 있는 노드들을 -2로 변경해준다. - -2인 경우는 나올 수 없는 수 이기도 하며 False로 설정..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net # 조건 - 토마토를 보관하는 창고가 있는데 익힌 토마토는 1, 비어있는 경우 -1, 그냥 토마토는 0으로 표시 - 익힌 토마토의 좌우상하 토마토는 다음날 익어있다. - 이 때, 모든 토마토를 다 익히는 경우, 최소 일 수를 구하여라 - 만약, 익히지 못한다면 -1 출력 # 접근 방법 - 좌우상하 탐색이 필요하므로 델타 함수를 이용하여 접근해준다. - 또한 바로 내 주변에 토마토가..

https://www.acmicpc.net/problem/1325 B 컴퓨터를 신뢰하는 관계라면, B 컴퓨터만 해킹하여도 A는 자동으로 해킹된다. 이 때, 한 컴퓨터를 해킹해서 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 출력하여라! 여러 대가 있다면, 오름차순 출력 # 접근 방법 자식 노드만 확인하는 것이 아닌 그 컴퓨터를 '신뢰하는' 또 다른 컴퓨터까지 확인해 주어야한다. 따라서 BFS를 확인하여 각 컴퓨터마다 해킹가능한 컴퓨터 수를 기록해주고 가장 많이 해킹하는 컴퓨터를 출력한다. BFS 기본 예제 문제와 비슷해보이지만, 1번이 아닌 모든 컴퓨터를 체킹한다는 것이 다르다. 그러다보니 많은 메모리, 시간을 사용하게 되고 PyPy로 제출하지 않는 이상 통과가 힘들었다.. ```python # N개..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 프로그래밍을 하며 '재귀'를 접하게 되면 가장 먼저 만나게 되는 문제라고 볼 수 있다. 그만큼 유명하고 재귀를 가장 잘 표현하였다고 생각이 드는 것이 '하노이의 탑'이라고 볼 수 있다. # 조건 세 개의 장대가 있고 첫 번째 장대에는 서로 크기가 다른 N개의 원판이 쌓여있다. 한 번에 한 개의 원판만 이동 가능하며 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. # 접근..

목차 1. 데코레이터(Decorator) 2. allowed HTTP methods 1. 데코레이터(Decorator) view 함수를 작성했다면 이번에는 View decorator라는 것을 이용하여 단단하게 만들어주자. 기존에 작성된 함수에 기능을 추가하고 싶을 때, 해당 함수를 수정하지 않고 기능을 추가해주는 함수 Django는 다양한 HTTP 기능을 지원하기 위하여 view 함수에 적용할 수 있는 여러 데코레이터를 제공한다. 위 코드에서 보이듯이 내부 수정이 아닌 `@hello`을 통하여 기능 추가를 해준 것을 출력을 통해 확인할 수 있다. 이런 데코레이터를 이용하여 단단하게 만드는 것이 어떤 것인지 알아보자! 2. Allowed HTTP methods django.views.decorators.h..

form, Modelform을 통하여 view 함수의 변화를 배워왔는데 가장 중요!! 한 것은 로직, 즉 순서를 잘 지키면서 이해한 상태로 작성하자는 것이다. 암기가 아닌 이해가 필요한 과목이다. 이번 글에서는 "HTTP requests 처리에 따른 view 함수 구조 변화"를 알아보자. 목차 1. HTTP requests 2. CREATE 3. UPDATE 1. HTPP requests 앞에서 작성하였던 new-create, edit-update의 view 함수 역할을 잘 살펴보면 하나의 공통점과 하나의 차이점이 존재한다. 공통점 new-create는 모두 CREATE 로직을 구현하기 위한 공통 목적 edit-update는 모두 UPDATE 로직을 구현하기 위한 공통 목적 차이점 new와 edit는 G..

앞서 Form Class를 작성해보며 느낄 수 있었던 것은 "Model이랑 중복되는 부분이 너무 많다"라는 것이었다. 우리는 이미 Article Model Class에 필드에 대한 정보를 작성하였는데 이를 Form에 맵핑하기 위하여 Form Class를 재정의 해야만 하였다. 목차 1. ModelForm 2. ModelForm with view Functions 3. Form과 ModelForm 비교 4. Widgets 활용하기 1. ModelForm ModelForm을 사용하면 위에서 말했던 중복되는 부분들을 제외하고 Form을 더 쉽게 작성할 수 있게 해 준다. Model을 통해 Form Class를 만들 수 있는 helper class ModelForm은 Form과 똑같은 방식으로 View 함수에서..

우리는 지금까지 HTML form, input 태그를 통해서 사용자로부터 데이터를 받았고 현재 우리의 Django는 들어오는 요청을 모두 수용하고 있다. 하지만 분명 이런 요청 중에는 비정상적인 혹은 악의적인 요청이 있다는 것을 생각해야 한다!! 목차 1. Form 2. Widgets 1. Form 위에서 적은 것처럼 사용자가 입력한 데이터가 우리가 원하는 데이터 형식이 맞는지에 대한 유효성 검증이 반드시 필요. 이런 검증은 많은 부가적인 것들을 고려해서 구현해야 하고, 이는 개발 생산성을 늦출뿐더러 쉽지 않은 작업이다. Django Form은 이 과정에서 과중한 작업과 반복 코드를 줄여줌으로써 훨씬 쉽게 유효성 검증을 진행할 수 있도록 만들어 준다!! # Form에 대한 Django의 역할 Form은 ..