Engineering Note

Link : https://www.acmicpc.net/problem/11053 Note Dynamic Programming(이하 DP)의 개념을 익히기 위해서 풀어 본 문제다. DP는 기본적으로 작은 단위의 부분 문제들의 해를 구하고 이 부분 문제들을 이용해서 조금 더 큰 문제를 해결하고, 최종적으로는 최초 주어진 문제를 해결하는 알고리즘이다. 우리말로 동적 계획법으로도 불리는데 여기서 계획은 문제를 해결하는 과정에서 부분 문제들의 해를 기록해두면서 테이블을 채워가는 것을 의미한다. 가장 긴 증가하는 부분 수열 문제는 대표적인 DP문제이다. 수열이 주어지고, 수열의 부분집합에서 수들이 증가하는 값들로만 이루어진 부분집합의 크기를 구하는 문제이다. 예를 들어 문제에 주어진 예시 처럼 2, 7, 5, 8,..

Link : https://www.acmicpc.net/problem/2579 Note 도착점의 위치를 N이라고 할때 도착점에 도달 하는 최대를 구하는 방법은 마지막에 2칸을 이동하는 방법인, N-2까지 문제의 조건대로 최대 점수를 구하는 방법으로 온 다음 N으로 가는법과 마지막에 한 칸을 이동하는 방법인 ,N-3까지 문제의 조건대로 최대 점수를 구하는 방법으로 온 다음 N-1, N으로 오는 방법중 최대를 구하면 된다. 이때 후자의 경우 N-1까지 최대로 온 다음 N으로 가면 되지 않나 생각할 수 있는데 이렇게 되면 N-1까지 최대로 온 경우가 N-2를 통해서 왔는지 체크할 수 없기 때문에 안된다. 왜냐하면 N-1까지 오는 최대의 경우가 N-2를 거쳐서 왔다고 하면 N을 밟는 순간 3계단 연속 밟기 때문..

문제 : Note 다이나믹 프로그래밍 문제는 점화식으로 나타낼 수 있고, 점화식으로 나타낸 문제는 재귀로도 구할 수 있다. 재귀를 잘 다루는 방법은 가장 종료시점부터 생각해 보는 것이다. 그리고 함수를 잘 정의해야한다. 이 함수는 무엇을 의미하는지 이 문제를 풀기위해 recur 함수는 dy[N]을 구하는 함수 dy[N]은 Nm길이를 1m,2m로 자르는 방법의 수. 즉 Nm를 1m,2m로 자르는 방법의 수를 구하는 함수이다. 이 함수의 동작 과정을 상태 트리로 표현 한다면 아래와 같다. 재귀를 타고 가다보면 중복되는 함수 호출이 발생한다. 이를 메모이제이션 기법을 이용하면 중복되는 연산의 횟수를 줄일 수 있다. 그리고 재귀 함수는 재귀를 타고 내려간 상태에서 생각할 수도 있고, 재귀를 타기 전 부모노드의 ..

문제 : Note 다이나믹프로그래밍으로 사고하는 연습이 전혀 안되어 있음을 알게 해준 문제였다. 나는 재귀, 트리, 그래프 등으로만 사고를 하여 문제를 해결하는 타입이였다. 이유는 지금까지 그런 유형의 문제를 많이 풀면서 트리로, 그래프로, 재귀로 사고하는 과정이 익숙해기 때문이다. 컴퓨터공학은 사고하는 방법을 배우는 학문이다. 사고를 이론화한 다른학문과는 아주 다른 특이한 학문이다. 이론과 실전의 융합. 실전을 통해 이론의 사용을 명확히 이해할 수 있다. 개념을 정확히 이해하는 것은 매우 중요하지만 문제풀이, 실전경험을 통해 이론이 더 강화 될 수 있다. 제대로 알고 피나는 연습으로 몸에 이론이 달라붙으려면 실전연습이 많이 필요하다. 그렇다고 항상 이론을 먼저 알아야하는 것은 아니다. 실전 연습을 통해..

get 쿼리 파라미터로 전달 된 값을 객체로 받고 나서 다시 객체 값을 돌려 주려고 하는데 에러가 발생했다. 스프링에서는 json을 객체로 객체를 json으로 다룰 때 Jackson 라이브러리를 사용하는데 이 라이브러리가 버전이 호환이 되지 않아서 에러가 발생했다. 나는 코틀린 버전을 1.432를 사용하고 있었는데 구글에 검색을 해보니 코틀린 버전이 1.1이상이라면 jackson 버전을 2.9 이상을 사용하라고 했다. Talend API Tester를 통해 리퀘스트 전송시 아래와 같이 에러 발생 org.springframework.web.util.NestedServletException: Handler dispatch failed; nested exception is java.lang.NoClassDef..

Link : https://www.acmicpc.net/problem/1969 Note 문제를 정확히 읽자. 잘 못 읽은 문장 N개의 길이인 M인 DNA 등의 문장 S와 S1의 Hamming Distance등의 문장 구해야할 새로운 DNA s는 입력으로 주어진 DNA들의 각 위치 별로 가장 많이 등장한 뉴클레오티드로 구성하면 Hamming Distance 합이 최소가 되는 DNA s를 구할 수 있다. 예를 들면 아래와 같은 입력이 주어 졌을 때 새로 구할 S의 첫 번째 뉴클레오티드를 T로 하면 3번째 "AAAGATCC" DNA에서만 첫 번째 자리에서 Hamming Distance값이 더해진다. 즉, 새로 구할 DNA는 주어진 DNA의 각 자리를 모두 확인해서 빈도수가 높은 뉴클레오티드로 채워주면 된다. ..

Link : https://www.acmicpc.net/problem/1010 Note 서쪽과 동쪽의 사이트 마다 1부터 N,M으로 번호를 부여하고 두 사이트 간의 다리 사이의 연결 상태를 직접 그려보다가 트리로 표현하면 편리하겠다 싶어 수형도, 트리로 표현하다보니 규칙을 발견했다. 교차하면 안되기 때문에 현재 연결한 다리의 다음 번호의 다리는 직전 번호의 연결 사이트 보다 최소 1이 큰 값들에만 연결해야 한다. 이 규칙에 따라 트리를 그리다 보면 이전 단계에서 확인한 경우를 다시 구해야하는 경우가 생기게 된다. 그경우 DP배열에 저장해두어 다시 연산하는 과정을 축소했다. Code import sys def recur(west, east): global checked, DP, n,m if west >=n..

Link : https://www.acmicpc.net/problem/1018\](https://www.acmicpc.net/problem/1018) Note 문제에서 주어진 규칙을 어떻게 알고리즘으로 구현할 것인지 생각하면 된다. 직관적으로 생각해보기 위해서 4\*4일 때를 기준으로 먼저 생각해보고 크기를 생각해보았다. 여기서 좀 더 빠르게 구할 수 있는 규칙을 발견했다. 0행 0열이 W일 때와 B일 때로 나누어서 생각하지말고, W이든 B이든 0행 0열의 값을 기준으로 나머지 칸들이 문제에 주어진 규칙에 맞는지 모두 확인하고 다시 칠해야할 칸들의 수(CNT)를 구한다. 이때 구한 칸의 수는 달라질 수있다. 만약 0행 0열을 기준으로 두지 않고 0행 0열을 바꾸고 시작 했다면, 새로 칠해야 할 칸은 4\..