프로그래밍 관련 정보

 문제 설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/12902 Idea 풀이 방법이 직관적으로 떠오르지 않아 정의된 문제의 N 값에 따른 답안을 구하며 규칙을 찾아보기로 했습니다. 우선 2x1인 직사각형 타일을 이용하여 3xN인 바닥을 채워야 합니다.  다만, 3xN 바닥의 세로 길이가 3이기 때문에 2x1 직사각형은 반드시 누워져서 들어가는 경우가 발생합니다. 이는 N이 홀수인 경우엔 2x1 직사각형 타일을 이용하여 3xN 바닥을 채울 수 없음을 의미합니다. (아래 그림 참고) 3x3, 3x5인 바닥의 경우 위 이유로 규칙은 N이 짝수인 경우에만 찾도록 하겠습니다. 1. 규칙 찾기 N=0: 0개, 타일을 둘 수 없음 N=2: 3개, 아래 사진 참고 N=4: 11개, (3*3 + 2)   - N=2일 때 있었던 3개의 경우에 다시 3가지의 경우의 수들 추가.   - N=4일 때 특수한 형태의 모양 생성 (그림 맨 하단 참고)  N=6: 41개, (3*11 + 2*3 + 2)   - N=4일 때 있었던 경우에 다시 3가지의 경우의 수들 추가.   - N=4일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우측 참고)      > 특수한 형태의 모양은 "앞, 뒤"에 따라 다른 경우의 수를 만들 수 있습니다.    - N=6일 때 특수한 형태의 모양 생성 (그림 맨 우하단 참고)  N=8: 153개, (3*41 + {6*3+2*2} + 2*3 + 2)   - N=6일 때 있었던 경우에 다시 3가지의 경우의 수들 추가.   - N=6일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우상단 참고)      > 특수한 형태의 모양은 "앞, 뒤"에 따라 다른 경우의 수를 만들 수 있습니다.    - N=4일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우중

  문제 설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/148652 Idea 풀이 방법이 직관적으로 떠오르지 않아 정의된 문제에 대한 규칙을 찾아보기로 했습니다. 1. 규칙 찾기 N=0 : 1 (1개) N=1 : 1 / 1 / 0 / 1 / 1 (5개) N=2 : 11011 / 11011 / 00000 / 11011 / 11011 (25개) N=3 : 1101111011000001101111011 / 1101111011000001101111011 / 000000000000000000  / 1101111011000001101111011 / 1101111011000001101111011 (125개) N-1 값들이 앞뒤*2로 생기며 중간은 N-1의 길이의 0이 생기는 규칙을 발견할 수 있습니다. Ex. N=2라면, 11011(N=1)이 앞뒤*2로 생기며 중간에는 11011의 길이인 5개의 0이 생김       -> 11011 / 11011 / 00000 / 11011 / 110111 2. 규칙 정리 1. 규칙 찾기에서 찾은 규칙을 정리하면 아래와 같습니다. (1만 세서 정리) N cantor_bit total_1 len 1 1/1/0/1/1 4 5 2 4/4/0/4/4 16 25 3 16/16/0/16/16 64 125 4 64/64/0/64/64 256 625 5 256/256/0/256/256 1024 3125 N이 증가함에 따라 1의 수는 $4^{N}$으로, 길이는 $5^{N}$으로 증가하는 규칙을 발견할 수 있습니다. Ex. N=2라면, 1의 수는 총 16개 (4 / 4 / 0 / 4 / 4), 유사 칸토어 길이는 25 3. 수식 정리   1. 총 5개의 그룹으로 나눔 (X / X /

  문제설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/131701 Idea 행의 %N으로 원형 리스트 인덱스를 추출하여 탐색 후 값을 더해줍니다.  중복된 값이 없어야 하기 때문에 set을 이용하여 부분 수열 합의 값을 저장합니다. 이 때 부분 수열의 합을 구한 값을 재사용합니다. (구했던 값을 굳이 또 다시 구할 필요는 없습니다) Solution 01 def solution (elements): N = len (elements) for i in range (N- 1 ): elements.extend([elements[i*N+j] + elements[(i+j+ 1 )%N] for j in range (N)]) return len ( set (elements)) 부분 수열의 합을 구한 값들을 elements 변수에 추가하며 추가된 변수 값과 기존에 제공된 elements의 값을 더해줍니다. 이후 set으로 변경하여 중복되지 않은 부분 수열 합의 개수를 구합니다. Solution 02 def solution (elements): N = len (elements) ans = set (elements) add = [e for e in elements] for i in range ( 1 , N): for j in range (N): add[j] += elements[(i+j)%N] ans.add(add[j]) return len (ans) Solution 01의 접근법과 동일합니다. 다만 01에서 사용한 elements 리스트에 계산된 부분 수열의 합을 추가하는 형식이 아닌, add라는 리스트를 생성하여 부분 수열의 합을 누적하여 계산합니다. 계산된 값은 set에 바로바로 추가하며 중복되지 않은 부분 수열 합의 개수를 구합니다. So

문제설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/131130 Idea 특정 인덱스를 기반으로 cards를 탐색해 해당 리스트 값을 새 인덱스로 설정하며 cards를 탐색합니다. 이미 탐색된 cards에 접근한 경우 탐색을 종료하고, 이 때까지 탐색된 수량을 저장합니다. 전체 cards를 모두 탐색할 때까지 위를 반복합니다. 탐색이 종료된 경우 탐색된 수량이 2개 이상이면 최대 수량 2개의 곱을, 1개 이하면 0을 반환합니다. Solution 01 def solution (cards): ans = [] for i in range ( len (cards)): cnt = 0 pts = i while cards[pts]: cnt += 1 temp = cards[pts] cards[pts] = 0 pts = temp - 1 if cnt: ans.append(cnt) ans.sort() return 0 if len (ans) < 2 else ans[- 1 ] * ans[- 2 ] 0~N-1까지 돌며, 탐색하지 않은 cards[pts]라면 해당 값을 pts 변수에 저장하고 방문한 수량(cnt)을 증가합니다. 이미 방문한 cards라면 그 전까지의 수량을 ans 변수에 저장합니다. ans 변수를 오름차순으로 정렬한 뒤, 길이가 2 이상이면 -1 번째와 -2번째 길이의 곱을 반환합니다. 전체 코드는 깃허브 에서 확인 가능합니다.

문제설명 문제 링크:  https://programmers.co.kr/learn/courses/30/lessons/43105 Idea 문제의 조건을 보면 "꼭대기에서 바닥까지 이어지는 경로 중, 숫자 합이 가장 큰 경우"를 찾는 문제입니다. 2차원 리스트가 주어졌을 때 모든 경우의 수를 계산 해야만 숫자 합이 가장 큰 경우를 찾을 수 있습니다. 리스트의 합을 구하는 조건은 "한 칸 오른쪽"과 "한 칸 왼쪽"으로 갈 수 있다고 정의되어 있습니다. 이는 triangle[0][0]에 있는 값은 triangle[1][0]과 triangle[1][1]로 갈 수 있고,  triangle[2][1]은 triangle[3][1]과 triangle[3][2]로 갈 수 있다는 의미입니다. 숫자의 가장 큰 합을 구해야하기 때문에 triangle[1][0]에는 triangle[0][0]+triangle[1][0]을 해주면 되고, triangle[3][1]은 triangle[3][1] + triangle[2][0] 또는 triangle[3][1] + triangle[2][1] 중 큰 값을 넣으면 됩니다. 이는 triangle[i][j] + triangle[i-1][j]와 triangle[i][j] + triangle[i-1][j+1] 중 큰 값을 triangle[i][j]에 넣어주면 됨을 유추할 수 있습니다. Solution 01 from copy import deepcopy def solution (triangle): # 0.298445245 triangle_temp = deepcopy(triangle) max_sum = triangle[ 0 ][ 0 ] for i in range ( 1 , len (triangle)): for j in range (i): if triangle[i][j] < triangle_temp[i][j

문제설명 문제 링크:  https://programmers.co.kr/learn/courses/30/lessons/42895 Idea 01 유의미한 풀이 규칙을 찾을 수 없어 다른 분의 접근 방법을 참고했습니다. ( 참고 블로그 ) 주어진 N은 2, number이 11일 때 return 3을 구할 수 있는 횟수(n)를 구하는 방법은 다음과 같습니다. n이 1일 때는 딱 1개만 만들 수 있습니다. n이 2일 때는 2를 2번 이어붙인 경우와, 2를 1번(n-1) 사용했을 때 값에서 2를 사칙연산한 경우가 존재합니다. n이 3일 때는 2를 3번 이어붙인 경우와, 2를 2번(n-1) 사용했을 때 값에서 2를 사칙연산한 경우가 존재합니다. N=2일 때, number=11을 만족하는 식은 22/2=11이고 이때 2가 최소 3번 사용된 걸 확인할 수 있습니다. 위 방법을 통한 풀이를 하기 위해서는 2를 이어붙이는 경우를 제외하곤 n이 2인 숫자 조합을 만들기 위해선 2를 1번(n-1) 사용했을 때 값과 2를 사칙연산합니다. n이 3인 숫자 조합을 만들기 위해선 2를 2번(n-1) 사용했을 때 값과 2를 사칙연산합니다. 특정 N에 대한 최소 조합을 구하기 위해선 n-1값에 N을 사칙연산하면 최소 n을 구할 수 있는 것으로 보이지만, 단순하게 n-1 숫자 조합에서 N을 사칙연산하는 방법으로는 최소횟수를 제대로 구할 수 없습니다. N=4일 때 number=3을 만족하는 최소 식은 4-(4/4)이지만, 위의 접근 방법을 사용하면 4에서 (4/4)를 빼주는 경우는 없습니다. (숫자조합이 (2+2)라면 여기에 2를 +, - ,*, / 만 진행하기 때문) Idea 02 위에서 발생한 예외(4-(4/4))를 처리하기 위해 다른 분의 접근 방법을 참고했습니다. ( 참고블로그 ) 우선 N=4일 때, 숫자 4를 최소 1~8번 조합할 수 있습니다. (문제에서 최소 사용 횟수를 8까지 정의) 4를 2번 사용해서 만들 수 있는 경우이며, 이 때 숫자 2에 대한

문제설명 문제링크: https://programmers.co.kr/learn/courses/30/lessons/62048 Idea 01 풀이 방법이 직관적으로 떠오르지 않아 정의된 문제에 대한 규칙을 찾아보기로 했습니다.  방법은 아래와 같이 파워포인트 표에 대각선을 직접 대입하여 단순 무식하게 규칙을 찾았습니다. 1. 정사각형일 때 각 w에 해당하는 길이 만큼 격자칸이 잘리는걸 알 수 있습니다. 사용할 수 있는 격자칸은 w==h라면 w * h - w 2. 직사각형일 때 2씩 넘어갈 때 마다 격자칸이 +2가 되는걸 알 수 있습니다. 3의 배수에 맞춰 중앙 값이 +1 높은걸 알 수 있습니다. 하지만 w가 4로 바뀌었을 때, w가 2일 때와 비교하여 규칙을 찾기가 쉽지 않았습니다. Idea 02 유의미한 규칙을 찾아낼 수 없어 다른 사람들의 접근법을 확인했습니다. 참고블로그 https://leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-in-python 아이디어는 다음과 같습니다. 1. 좌표계로 표현 w=6, h=8인 그림의 직선의 식은 \(y=\frac{8}{6}x=\frac{4}{3}x\)이며, (3,4), (6,8)일 때 위 그림상에 빨간점을 지납니다. 이 때 직선이 지나는 빨간점의 수는 w, h의 최대공약수와 동일합니다. (gcd=2, 빨간점 2) 멀쩡한 사각형에 나온 예시 w=8, h=12인 경우 직선의 식은 \(y=\frac{12}{8}x=\frac{3}{2}x\)이며, (2,4),(4,8),(6,8),(8,12)일 때, 위 빨간점을 지나며 점 4개의 수는 w, h의 최대공약수와 동일한 것을 확인할 수 있습니다. (gcd=4, 빨간점 4) 2. 수식 정의 gcd와 빨간색 점 수가 동일하다는 것을 기반으

문제설명 문제링크: https://programmers.co.kr/learn/courses/30/lessons/42626 Idea scoville 함수에서 가장 작은 값과 2번째로 작은 값 추출 문제에 정의된 공식에 의거하여 값을 계산한 뒤 scoville에 추가 scoville > K인지 판별 scoville > K 조건을 만족하기 위해 몇 번 반복하여 점수 계산을 했는지 반환 Solution 01 def solution (scoville , K): # 0.503594313 N = len (scoville) scoville.sort() for i in range ( 1 , N): n1 = scoville.pop( 0 ) n = n1 + (scoville[ 0 ] * 2 ) scoville[ 0 ] = n scoville.sort() if all ([ 1 if s > K else 0 for s in scoville]): return i return - 1 scoville를 정렬하면 가장 작은 값 순서대로 배열에 정리가 됩니다. scoville[0]과 [1]에 있는 값을 가져와 문제에 정의된 수식에 의거하여 스코빌 지수를 계산합니다. 계산된 스코빌 지수를 scoville에 다시 정렬합니다. (최솟, 2번째 최솟 값을 0, 1 인덱스에서 가져오기 위해) 만약, scoville에 있는 모든 값이 K보다 크다면(scoville > K) 이 때까지 스코빌 지수를 계산한 횟수(i)를 반환합니다. scoville에 있는 모든 값에 대해 스코빌 지수를 계산했지만 여전히 K보다 작다면(scoville < K) -1을 반환합니다. import timeit tests = [[[ 1 , 2 , 3 , 9 , 10 , 12 ] , 7 ] , [[ 1 , 2 ] , 7

 문제설명 문제링크:  https://programmers.co.kr/learn/courses/30/lessons/42839 Idea 순열을 통해 조합할 수 있는 모든 경우의 수 탐색 중복된 수 제거 소수 여부 판별 Solution from itertools import permutations def isprime (n): flag = False for i in range ( 2 , int (n** 0.5 )+ 1 ): if n % i == 0 : flag = True break return True if not flag else False def solution (numbers): # 0.09262283575 p_list = list ( set ( int ( '' .join(p)) for i in range ( 1 , len (numbers)+ 1 ) for p in permutations(numbers , i))) p_list = [p for p in p_list if p > 1 ] return len ([p for p in p_list if isprime(p)]) 입력된 numbers로 표현할 수 있는 모든 경우의 수를 계산하고 중복을 제거한 배열(p_list)을 생성합니다. 소수는 2부터 시작하기 때문에 0이나 1인 값을 제거합니다. 소수를 판단하는 함수(isprime)를 만들어 p_list에 있는 값이 소수인지 아닌지 판별합니다. 소수 판별은 2부터 √n까지의 값을 n이랑 나눠 0으로 나눠떨어지는지 판단합니다.  나눠떨어지는 구간(n%i == 0)이 있다면 소수가 아니기 때문에 포문을 멈추고 소수가 아니라고 판단합니다. ※ √n까지 판별하는 이유는 여기 를 참고해주세요. import timeit tests = [ '11' , '17' ,