보자마자 DP문제다. DP문제는 점화식을 세워야 한다. 가로의 길이는 2*n+1이므로 현재 위치에서 어떤 타일을 사용해서 모양을 완성시킬 수 있는가에 대해 알아보자 가로로 타일을 채워갈 때 크게 두 가지로 나눌 수 있다. 타일을 정삼각형으로 쌓아야 하는 경우, 역삼각형으로 쌓아야 하는 경우다. 현재 위치가 x일 때, 삼각형 하나만 사용하는 경우엔 가로로 한 칸을 채울 수 있다. 따라서, dp [x] += dp [x-1] 마름모 타일이 서있지 않는 경우, 둘 다 가로로 두 칸을 채울 수 있다. 따라서 , dp [x] += dp [x-2] 마지막으로 마름모 타일을 돌려 높이가 1인 경우다. 이땐 현재 위치에서 타일을 정삼각형으로 쌓아야 하는 경우, 현재 위치보다 한 칸 앞의 타일의 높이가 1인 경우이다. 따..

문제흐름을 살펴보면 카드가 2장 주어졌을 때, 한 장도 가지지 않을 것인지, 한 장을 가질 것인지, 두 장을 가질 것 인지를 결정해야 한다. 여기서 포인트는 카드를 뽑을 것인가는 당장 정하지 않는다는 것이다. 지금 당장 n+1을 만들 수 있는 카드 조합이 있다면, 카드를 뽑지 않고, 카드 더미에 쌓아두는 것이다. 당장 카드를 뽑지 않아도 나중에 필요할 때 coin을 사용해서 n+1 카드를 만들 수 있는 것이다. 따라서 전체적인 흐름은 아래와 같다. 1. 카드를 카드 더미에 쌓는다. 2. n+1 해결하기 1. 수중에 있는 카드로 n+1을 만들 수 있다면, 다음 카드 뽑기 2. coin을 사용해야 한다. 2-1. coin 없다면 게임 끝 2-2. coin 한 개를 사용해서 (수중에 카드 한 장 + 카드 더미..

문제의 흐름을 파악하면 크게 3단계로 나눌 수 있다. 1. 모든 주사위 조합을 구한다. 2. 조합들을 비교하여 , A가 B를 이기는 가장 높은 확률의 주사위 조합을 구한다. 3. 가장 확률이 높은 주사위 번호를 오름차순으로 정렬한다. 결국 주사위 n/2개를 뽑은 A가 나머지 주사위를 고른 B를 가장 많이 이기는 주사위 n/2개의 주사위 조합을 구하면 된다. 실제 코딩테스트를 볼 때 위의 단계까진 생각했으나 구현에서 막혔다. 시간 복잡도를 계산하면 n의 범위는 10이므로 A가 가질 수 있는 최대 주사위의 개수는 5개, 5개의 주사위에서 나올 수 있는 주사위의 합은 최대 6*6*6*6*6= 7776개이다. A가 B를 이기는 횟수를 구하기 위해 A가 가질 수 있는 주사위의 합의 개수, B가 가질 수 있는 주사..

우선 이 문제는 두 포인터를 활용한 문제다. 두 개의 눈사람 키 차이 중 최솟값을 구하는 문제이다. 문제 풀이를 보고 이해가 안 가는 부분이 있었는데, a, b와 사이엔 최소 2개의 원소가 있어야 그 안에서 투포인터를 돌려 a, b로 이루어진 눈사람의 키와 차이가 가장 적은 눈사람을 만들 수 있다. 정렬된 배열에서 두 포인터를 돌리므로, a

이번 문제를 풀 때 가장 중요한 점은 주어진 수가 이진트리로 표현할 수 있는가? 였습니다. 따라서 처음에 주어진 수를 이진수로 변환한 뒤 이진트리가 될 수 있도록 패딩을 먼저 진행하였습니다. ( 자릿수가 2의 제곱수보다 1 작도록 설정 ) 그 후 루트 노드 ( 이진수의 가운데 수 )의 왼쪽 트리의 루트 노드, 오른쪽 트리의 루트노드를 검색하는 재귀 함수를 작성하였습니다. 이때 루트노드가 0이며, 왼쪽 트리의 루트 노드, 오른쪽 트리의 루트 노드가 모두 1일 경우 표현 불가능한 이진트리로 판단하였습니다. 문제 자체는 어렵지 않고, 실제로 작년 카카오 코딩테스트 때 구상까지는 완료하였으나, 구현에서 막혀 풀지 못한 문제였습니다. import math def get_digit(number): pow = 0 w..

사실 카카오 인턴 코딩테스트를 봤었기 때문에 문제의 내용과 어떻게 풀어야 할지는 대충 감을 잡은 상태로 문제를 풀었습니다. 단순히 DP로만 풀면 되겠지 하고 문제를 풀어나갔을 때 정확성만 맞고 효율성에서 시간초과가 가는 코드를 작성하였습니다. 제가 이와같은 문제를 해결할 때 두 가지 문제 점이 있었는데, 한가지는 시간복잡도 , 다른 한가지는 alp, cop 가 m_alp, m_cop ( 알고력 중 제일 높은 알고력, 코딩력 중 제일 높은 코딩력 ) 보다 큰 경우입니다. 시간 복잡도를 맞추기 위해 커팅이 필요했는데 카카오 문제풀이 해설에서 시간 복잡도가 O(목표 알고력 * 목표 코딩력 * ( problems 배열의 길이 )) 라고 하여 이에 맞게 조정하였습니다. alp, cop 가 m_alp, m_cop ..

문제를 읽어보면 두개의 큐가 같은 합을 가져아한다고 말한다. 이 때 두개의 큐의 합의 절반을 각각의 큐가 가져야 한다는 것을 알 수 있다. 두개의 큐의 합의 절반을 가진 큐를 구하기 위해 두개의 큐가 하나로 합쳐져 있다고 생각하면 구간 합이라는 것을 알 수 있다. 생각해야 할 점은 구간합이 두개의 큐의 합의 절반이더라도 또 다른 구간이 나올 수 있으므로 구간합이 두개의 큐의 합의 절반이더라도 탐색을 종료하면 안된다. 또 생각해야 할 점은 구간이 정해졌을 때 end가 큐의 길이보다 작을 때와 클 때의 작업 횟수가 다르다는 점이다. def solution(queue1, queue2): s = (sum(queue1)+sum(queue2))/2 start , end = 0, 0 q = queue1+ queue2..

문제를 읽어보면 구현 문제라는 것을 알 수 있다. 따라서 문제 포인트만 말해보면 ( R , T ) , ( C , F ) , ( J , M ) , ( A , N ) 중 하나씩 골라야 한다. 문제 조건 중 두개 중 점수가 같아 고를 수 없으면 사전 순으로 빠른 순서를 지닌 성격 유형을 고른다. survey 를 하나씩 검사하여 점수를 부여하면 된다. from collections import defaultdict def solution(survey, choices): answer = '' d = defaultdict(int) for idx in range(0,len(survey)): if choices[idx] 4: d[survey[idx][1]]+=choices[idx]-4 mbti=[['R','T'],['..