고양이 두 잔

목차 Strategy Pattern 전략 패턴은 정책 패턴(Policy Pattern)이라 불리기도 하며, 소프트웨어의 실행 중 상황에 맞는 알고리즘을 선택해 실행할 수 있도록 하는 객체 지향 디자인 패턴이다. 예를 들자면 배열을 정렬하는 sort()라는 메서드가 있을 때, 요청한 알고리즘이 어떤 정렬인지에 따라 다른 로직을 실행하도록 소프트웨어를 디자인하는 것이라고 할 수 있다. 위키백과에 따르면 전략 패턴은 대략 아래와 같은 절차에 따라 구성되며, 복수의 알고리즘을 정의 정의한 알고리즘을 캡슐화 해당 알고리즘을 전략에 맞춰 상호 교체 가능하도록 구성 이어서 아래와 같은 세 부분으로 구성된다. 전략 인터페이스(Strategy Interface) 알고리즘을 정의하는 인터페이스. 일반적으로 알고리즘을 수행..

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이 조금 헷갈려서 시간이 들었지만, 흔하고(?) 유명한 동적계획법 문제이다. 먼저 두 문자열 n, m을 입력받고 (n.length + 1)(mlength + 1)크기의 이중 배열을 memo를 생성한다. 이어서 이중 반복문을 순회하며 n.charAt(i - 1..

Index 문제 두 전봇대 A와 B 사이에 하나둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구..

목차 이 글은 아래의 영상을 시청하고 요약 및 정리한 글이다. https://www.youtube.com/watch?v=LGrjmHDwVwk 갑자기 뭔 블로그로 돈 벌기 글을 올리냐는 의문이 나도 들기는 하는데, 앞으로 일을 하는 데 있어서 해당 도메인에 대한 지식이 필요할 거라는 CTO님의 언급이 있었고 영상 링크를 직접 보내주셨기 때문에 반드시 알아야겠다는 생각이 들었다. 다만 영상 및 제공하는 자료도 정확하게 카테고리가 나뉘어있지 않고 직접 카테고리를 나누기엔 아는 것이 너무 없어서 일단 영상의 흐름대로 정리하려고 한다. 우선 시작. Mindset 당연한 이야기지만 모든 수익화의 핵심은 비즈니스 모델이다. 유튜브를 이용하건, 인스타그램이나 블로그를 이용하건 이 기본적인 사실은 변하지 않는다. 조금 ..

문제 수열 $S$가 어떤 수 $S_{k}$를 기준으로 $S_{1} S_{k+1} > ... S_{N-1} > S_{N}$을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열 $A$의 크기 $N$이 주어지고, 둘째 줄에는 수열 $A$를 이루고 있는..

문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N

문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 티어는 하나 낮지만 왜인지 포도주 마시기 문제보다 어려웠던 문제이다. 메모이제이션을 위한 배열을 갱신하는 부분이 특히 어려웠는데, 2차원이 아니라 1차원으로 선언한 뒤 그때그때 바꾸는 방식은 깔끔..

문제 효주는 포도주 시식회에 갔다. 그곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6..

문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 반복되는 동적계획법 문제이다. 계속 풀다 보니 동적계획법은 계획을 세우는 자체보다 경계선을 올바로 잡는 게 중요하다는 생각이 든다. 아니 어쩌면 경계선을 잡는 것 자체가 계획의 전부인지도. 우선 입력으로 주어지는 n을 받아 이차원 배열 memo를 선언했다. 그리고 0을 제외한 memo[1]의 요소를 1로 초기화했는데,..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 조금씩 난이도가 오르는 동적계획법 문제다. 하지만 기본적인 접근 방식은 다를 것이 없어서, 어느 연산을 어떤 식으로 배치하는 지만 정해주면 되는 문제. 우선 주어진 수보다 1이 더 큰 길이를 가진 memo 배열을 선언한다. 그리고 memo[1]에는 초기값으로 0을 입력..