Engineering Note

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계단 연속 밟기 때문..

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

Link : https://www.acmicpc.net/problem/1913 Note 숫자 입력 방식에서 규칙이 없을지 직접해보면서 방향 전환에서 규칙을 발견했다. N이 3일 경우 1:(상, 우) 2:(하,하 좌,좌, 상,상) N이 5일 경우 1:(상, 우) 2:(하,하, 좌,좌) 3:(상,상,상, 우,우,우) 4:(하,하,하,하, 좌,좌,좌,좌, 상,상,상,상) N이 7일 경우 1:(상. 우) 2:(하,하, 좌,좌) 3:(상,상,상, 우,우,우) 4(하,하,하,하, 좌,좌,좌,좌) 5:(상,상,상,상,상, 우,우,우,우,우) 6:(하,하,하,하,하,하, 좌,좌,좌,좌,좌,좌, 상,상,상,상,상,상,상) 으로 변화한다. i가 1부터 N-2 까지는 증가할 때 방향회전 방식은 다음과 같다. 상,우,하,좌가..

Link : https://www.acmicpc.net/problem/2444 Note N에 대하여 1번째줄부터 N번째 줄까지는 다음과 같은 규칙을 갖는다. i 번째 줄은 " "(스페이스 공백)은 (N-i)개를 출력하고 "*"은 (2*i-1)개를 출력한다. 그리고 다시 N+1 부터는 N+N-1번째 줄까지는 다시 N+1 번째 줄을 새로운 첫 번째 줄이라고 생각할 때 j번째 줄은 " "(스페이스 공백)은 j번 출력하고 "*"를 (2*(N-1) -(2*j-1))을 출력한다. 예를 들면 N이 5일 때, 첫 번째줄 " "-4번, *-1번 두 번째줄 " "-3번, *-3번 세 번째줄 " "-2번, *-5번 네 번째줄 " "-1번, *-7번 다섯 번째줄 " "-0번, *-9번 여섯 번째줄 " "-1번, *-7번 (새..