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에서 몇번째 숫자인..

백준에서 문제를 풀면 여러 줄의 패턴을 input 함수로 입력 받을 때가 많습니다. 하지만 input 함수보다 sys.stdin 을 사용하는 것이 더 빠릅니다. input 함수의 동작 input은 입력만 받는 것이 아닙니다. 출력도 할 수 있고 문자열 마지막의 개행문자(\n)도 제거해서 반환합니다. input('input here! : ') # input here! : hello world\n 'hello world' sys.stdin.readline 함수의 동작 반면 sys.stdin.readline의 경우 그저 입력을 받을 뿐입니다. 따라서 input 함수보다 빠릅니다. import sys sys.stdin.readline() # hello world\n 'hello world\n' sys.stdin..

N진수를 담은 list는 N진수를 직접 사용하는 알고리즘 뿐만 아니라 여러가지 구현을 할 때 전반적으로 자주 쓰여서 정리하였습니다. itertools의 product를 사용하면 원하는 Bit 개수 만큼 N진수를 생성 할 수 있습니다. from itertools import product base = 2 bit = 3 result = list(product(range(base), repeat=bit)) 결과는 다음과 같습니다. [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]

코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 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를 기준으로 왼쪽에 갈 노드들과 오른쪽에 갈 노드들을 만들어 줍니다. 이 과정에서 자연스럽게 부모노드는 포함이 되..