Engineering Note

Link : https://school.programmers.co.kr/learn/courses/30/lessons/12982?language=java Note 문제를 해석해보면 각 부서별로 물품 구매를 위해 필요한 금액이 있고, 회사는 전체 예산내에서 각 부서를 지원해줄 수 있다. 이때 최대 몇 개의 부서를 지원할 수 있는지 return 하는 문제이다. 단, 부서별 지원금액은 신청한 금액만큼을 모두 지원해주어야 한다. 나는 평소에 문제를 문자보다 시각적으로 변환해서 이해하는 것을 좋아하여 시각적으로 문제를 표현해 보았다.그리고 다음과 같은 문제와 같음을 이해할 수 있었다. budget 크기의 통에 크기가 부서별 신청 금액에 비례하는 상자를 집어 넣을 때 가장 많은 상자를 넣는 방법은?으로 해석할 수 있..

Link : https://www.acmicpc.net/problem/17298 Note 수열이 있을 때 각 원소, A(i)의 오큰수는 각 원소, A(i)보다 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 처음 생각한 방식은 2중 for문을 돌면서 각 원소보다 큰 원소를 찾으면 내부 for문을 중단하는 방식이다. 하지만 이때 최악의 경우 O(N^2)이 나온다. 최악의 경우가 나오는 경우는 처음 원소부터 모두 감소하는 형태의 수열이 존재하는 경우 모두 오큰수가 존재하지 않아서 모든 수열이 -1의 오큰수를 갖는 경우이다. 하지만 스택을 이용하면 O(N)의 시간복잡도를 가질 수 있다. 스택을 이용한 오큰수 찾기 알고리즘은 다음과 같다. ..

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

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..