퍼사드? 그게 뭔데 패턴으로 붙여 놨을까? 이것 부터 알아야할듯 싶다. 완벽하게 일치는 안해도 퍼사드 하면 떠오르는 이미지가 있는게 좋지 않을까? 퍼사드는 건물의 정면을 말한다고 한다. 어떻게 보면 이름을 잘지은 패턴이라고 할 수도 있겠다. 퍼사드 패턴은 객체지향의 최소 지식 원칙을 준수한다고 한다. 최소 지식 원칙이라는게 무엇일까? 여기서 말하는 지식은 도대체 뭘까? 내가 생각할 때, 사람의 지식은 아닌것 같다는 느낌이 든다. 이게 무슨 말이냐면... 보통 지식은 많은 것을 아는 것을 뜻한다. 하지만 객체지향의 지식은 조금 다르게 해석 되는것 같다. 바로 클래스의 연결로 결정된다. 이게 무슨 말이냐면 A,B클래스가 있다고 가정하자. 또, A클래스는 B클래스와 연결이 되어있다. 이 정도가 최소 지식 원칙..
브릿지 패턴..... 이것도 어뎁터와 마찬가지로 떠오르는 이미지가 있을거다. 바로 이런 다리 이미지를 떠올릴 것이다. 물론 동물의 다리를 떠올리는 분도 있겠지만 말이다. 근데.. 나는 잘 모르겠다. 왜 이름이 브릿지인지에 대해 전혀 감이 잡히지 않고 있다. 어째든 브릿지 패턴의 가장 큰 특징은 구현과 기능을 분리한다는 점에 있다. 이걸 따로 공부했을때는 아 그렇구나 라고 느꼈는데, 구현과 기능을 합쳐서 내가 아는 구현이 맞는 구현인가라는 착각이 들기도 한다. 결론부터 말하면 내가 생각한 구현이 맞다. 다만, 기능을 분리한다는데 구현에는 뭐가 들어있는 걸까? 구현을 하면 당연히 구현안에도 기능이 있을 텐데.... 왜 이걸 구현과 기능의 분리라 한것일까? 사실 분리하는 기능은 기본 기능은 제외된거였다. 예를..
문제 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 이 문제가 LCD라 였나.. 그런건데.. 나는 잘 모르겠다. 아무튼 이런류의 문제의 핵심은 dp를 조작하지 않는것이 핵심이다. 이 말이 어떤 뜻인지는 계속 읽어보면 알 수도 있을것 같다. 10 30 ..
어댑터라고 하면 제일 먼저 생각나는 건 대충 이런 이미지를 생각한다. 그럼 어댑터라는건 어떤 역할을 하는 걸까? 일상생활에서의 어댑터는 전기를 변환하는데 사용이 된다. 가령, 소켓(플러그를 꼽는 곳)은 220V를 사용되는데, 사용하는 전자기기가 사용하는 V는 110V를 사용한다고 한다. 이 두개가 호환성이 맞지않기 때문에 전력은 들어오지 않는다. 이때 필요한것이 바로 어댑터다. 어댑터를 이용하면 220V라는 전력을 110V로 바꿔준다. 어떻게 보면 컨버터랑 비슷하지만.. 뭐 이건 전기 수업이 아니므로 넘어가도록 하자. 또, 내가 전기를 잘 아는게 아니기 때문에 틀리게 말할 수 도 있다. 하지만 하나 확실한건 호환되지 않는 두 장치를 연결시켜준다는 점은 변함이 없다. 즉, 두개가 호환이 되게 해주는 역할을..
문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 ..
문제 M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는 64, 81, 100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다. 입력 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10000이하의 자연수이며 M은 N보다 같거나 작다. 출력 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 완전제곱수가 없을 경우는 첫째 줄에 -1을 출력한다. 흠 이건.. sqrt를 잘 사용하면 답을 쉽게 맞출 수 있다. ..
문제 최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다. 내린 사람 수탄 사람 수1번역(출발역)2번역3번역4번역(종착역) 0 32 3 13 28 25 39 0 예를 들어, 위와 같은 경우를 살펴보자. 이 경우, 기차 안에 사람이 가장 많은 때는 2번역에서 3명의 사람이 기차에서 내리고, 13명의 사람이 기차에 탔을 때로, ..
문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다. N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 출력 첫째 줄에 N자리 이친수의 개수를 출력한다. 이 문제도 그려 보면 답이 쉽게 나온다. 1자리 ..
문제 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 ..
문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 이 문제는 조건이 너무 많다. 그것들을 전부 신경쎠줘야 하기 떄문에 생각보다 까다로운 문제였다. #include using namespace std; bool compre(const string a , const string b) { if ..
문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 이 문제는 재귀가 아니라 동적 프로그래밍으로 푸는 문제다. 동적이 뭔지 감이 잡히지 않았는데 알고 보니 점화식을 만들어서 그 값들을 배열에 넣고 사용하는 방식인 듯 싶다. 어쩌다 보니 정답이긴 한데... 조금 그렇다. #include using namespace std; ..
문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그..