1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 자세한 해설 단순하게 N*N 배열을 정의 한 후 B를 만들어서 정렬을 하면 시간초과가 나오기도 전에 메모리초과가 나옵니다. 이 문제를 풀기 위해서는 이진탐색을 활용해야 합니다. 이진탐색으로 B[k]를 찾는 과정을 크게보면 다음과 같습니다. 이진탐색으로 mid를 구합니다. mid가 B에서 몇번째 숫자인지 구합니다. 만약 mid가 k번째 수라면 index도 k라는 뜻이고, mid = B[k] 가 됩니다. "mid가 B에서 몇번째 숫자인..

코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 자세한 해설 한쪽으로만 가면서 계산하는 경우 외에도 오른쪽으로 가다 왼쪽, 혹은 왼쪽으로 가다 오른쪽으로 가야 최적의 해가 나오는 경우가 있습니다. 따라서 모든 경우의 수를 만들어서 가장 낮은 횟수를 구하는 방향으로 풀었습니다. 우선 리스트 슬라이싱을 활용하여 한쪽으로 `i`만큼 밀린 name 2개를 만들어줍니다. name의 중간길이 미만으로 도는 이유는 그 이상으로 돌면 중복이 발생하기 때문입니다. for i in range(len(name..

코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 자세한 해설 재귀함수를 활용하여 쉽게 해결할 수 있습니다. 부모노드를 기준으로 노드를 나누고, 나눈 노드들로 재귀함수를 호출하며 순회를 기록하면 됩니다. programmers에서 채점 할 때 재귀 호출이 많이 깊어지므로 해당 코드가 있어야 런타임 오류가 나지 않습니다. import sys sys.setrecursionlimit(10**6) 부모노드의 x를 기준으로 왼쪽에 갈 노드들과 오른쪽에 갈 노드들을 만들어 줍니다. 이 과정에서 자연스럽게 부모노드는 포함이 되..