S E P H ' S

코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 풀이 1. numbers로 만들 수 있는 모든 숫자를 만든다. 2. 순서에 따라 다른 숫자가 되기 때문에 순열을 사용한다. 3. 만들어진 모든 수가 소수인지 판별하고 카운트 한다. from itertools import permutations as perm def solution(numbers): def isPrime(n): if n in (0,1): return False else: for i in range(2, int(n**0.5)+1): i..

코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 1. 동적계획법(DP)로 풀이 2. 반복문을 통한 완전탐색으로 풀이하기엔 시간복잡도에서 막힌다. (행 : 1,000 열: 1,000) 3. 정사각형이 가능한 최소 변의 길이 2만큼부터 파악. 4. dp 배열에 board의 첫번째 행렬을 넣고 대각선 인덱스에서부터 파악해 나간다. 5. 세 값을 비교해 최솟값에 +1을 해나가고 6. 가장 큰 값의 제곱을 리턴 def solution(board): n = len(board) m = len(board[0]) dp = [[0] * m for _ in range(n)] dp[0] = board[0] for i..

코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 풀이 1. 10진수를 n진수로 변환하는 재귀함수 구현 def convert(n, base): arr = "0123456789ABCDEF" q, r = divmod(n, base) if q == 0: return arr[r] else: return convert(n, base) + arr[r] 2. 미리 구할 숫자의 개수 t , 게임에 참가하는 인원 m t*m 까지의 숫자들을 convert하고 후보 리스트에 넣는다. 3. 인덱스가 0부터 이므로 p..

코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 풀이 1. 스택 원리로 풀이. 2. 첫 괄호가 ')'이라면 바로 False 3. 반복문을 돌면서 '(' 이라면 list에 append. 4. 만일 ')'이라면 먼저, 리스트가 비었는지 먼저 체크하고 비었다면 False를 반환한다. -> ex) (())) 과 같은 경우 ')'을 처리하는 부분에서 빈 값에서 pop을 해서 에러가 났었다. 5. 그렇지 않다면 list.pop()을 사용하여 먼저 들어가 있는 '('을 처리 d..