파이썬알고리즘/SW Expert Academy (7) 썸네일형 리스트형 [ SW Expert Academy / 4837 ] 부분집합의 합 1. 문제 이해 입력값: N (1 이상 12 이하) K (1 이상 100 이하) 유의해야 할 점: 1. 1 부터 12까지의 숫자를 원소로 하는 집합 A N : 부분집합의 원소 수 K : 부분집합 원소의 합 출력 값: 제시된 원소수와 원소 합에 대응하는 부분집합의 수 2. 문제 풀이 법 사용한 방법: 부분집합 구하기 temp_sum - 부분집합 합 temp_cnt - 부분집합 원소 수 부분집합 합과 원소 수 구하는데, 만약 문제에서 제시한 합 또는 원소수를 초과 할 경우 break를 통해 해당 부분집합은 skip 하였다. 3. 어려웠던 점 부분집합 코드 T = int(input()) for tc in range(1,T+1): N, K = map(int,input().split()) result = 0 # .. [ SW Expert Academy / 2819] 격자판의 숫자 이어 붙이기 1. 문제 이해 4x4 격자판에 0부터 9까지의 숫자가 있다. 임의의 위치에서 시작하여 4방향으로 6번 이동하며 7자리 숫자를 만든다. 만들 수 있는 서로 다른 일곱 자릿수 들의 개수는? 입력값: 테스트 케이스 T 각 방의 값 (4 줄에 걸쳐, ' '으로 나누어져 있다.) 유의해야 할 점: 왔던 곳 다시 갈 수 있다. 0으로 시작하는 수도 만들 수 있다. 출력 값: #테스트 케이스, 만들 수 있는 수의 개수 2. 문제 풀이 법 사용한 방법: DFS 1. 4x4의 칸들로부터 시작한다. 2. 현재 자리가 7일 경우 멈추고 결괏값을 저장한다. 인자 : [현재 위치], 자릿수, 현재까지 만들어진 수 3. 어려웠던 점 dfs를 사용할 때 종료 조건이 있고 return을 해줘야 한다는 점을 다시 한번 깨달았다. 1.. [ SW Expert Academy / 1865] 동철이의 일 분배 1. 문제 이해 “주어진 일이 모두 성공할 확률”의 최댓값을 구하기 위해선 일 분배를 어떻게 해야 할지? 입력값: 테스트 케이스 T 직원 수 , 일 수 N i 직원이 j 일을 맡았을 때 성공률 (N 줄에 걸쳐, ' '으로 나누어져 있음) 유의해야 할 점: 성공률이 0인 것도 있음 출력 값: #테스트 케이스, 모두 성공할 확률의 최댓값 ( 소수 일곱째 자리에서 반올림) 2. 문제 풀이 법 사용한 방법: DFS 순열 1. 각 일에 대한 순서는 답에 영향을 주지 않는다. 2. 성공률은 [ SW Expert Academy / 1861] 정사각형 방 1. 문제 이해 시작은 어느 곳이던 가능하며, 4방향으로 현재방의 +1이 있는 방으로만 움직일수있다 어떤 수가 적힌 방에 있어야 가장 많은 갯수의 방을 이동수 있는지? 입력값: 테스트 케이스 T 한 변의 길이 N 각 방의 값 (N 줄에 걸쳐, ' '으로 나누어져있음) 유의해야 할 점: 이동할 수 있는 방의 갯수가 최대인 방이 여러개일경우 그 중 가장 작은 방을 구해야 함 출력 값: #테스트케이스, 첫 출발 방 번호, 최대 이동가능 방 수 2. 문제 풀이 법 사용한 방법: DFS 처음 1에서 출발 했을 때, 1->2->3->.. 이렇게 거쳐왔다면..? 2.3에서 출발 할 필요 없다 왜냐면 겹치기 때문에! 따라서 visited를 만들어서 방문하였다. 방문(visited)하지 않은 수의 방에 대해 DFS를 실.. [ SW Expert Academy / 1949 ] 등산로 조성 1. 문제 이해 입력값: N (3 이상 8 이하) K (1 이상 5 이하) 1 이상 20 이하 정수 (N 줄에 걸쳐) 유의해야 할 점: 1. 가장 높은 봉우리에서 시작 (첫 시작이 정해져 있음) 2. 높은 지역에서 낮은 지역으로 4방향 (같거나 대각선 불가) 3. 딱 한 곳을 정해서 최대 K만큼 지형 깎기 가능 N :정사각형 지도의 한 변의 길이 K : 최대 공사 가능 깊이 출력 값: 가장 긴 등산로의 길이 2. 문제 풀이 법 사용한 방법: DFS 1.가장 높은 봉우리의 높이를 구한다. 2. 가장 높은 봉우리(첫 시작이 됨)를 탐색하여 리스트(starts)로 저장한다. starts의 각 start에 대해 DFS 함수를 실시한다. 인자 : x값, y값, 깎은 유무, 현재까지 등산로 길이 1. visited.. [SW Expert Academy / 5658] 벽돌 깨기 1. 문제이해 입력값: N : 구슬 쏠 수 있는 횟수 W : 벽돌 맵 가로 H : 벽돌 맵 세로 유의해야 할 점: 벽돌을 깨면 4방향으로 그 벽돌의 수-1 만큼 벽돌을 깨게 된다. 출력값: 최대한 많은 벽돌을 깨트리고 남은 벽돌의 수 2. 문제 풀이 법 사용한 방법: 1. comb() 함수로 중복 조합을 사용하여 어떤 열의 벽돌을 깨 트릴지 순서를 정한다. 2. play() 함수로 bfs와같이 queue를 이용하여 깬다. 3. zero() 함수로 벽돌들을 아래로 내려준다. 3. 어려웠던 점 1. 문제 이해를 아예 못했었다. 2. 어떻게 벽돌을 다시 내릴지에대해서 잘 몰랐었다. 1. zero 함수에서 시간을 좀 더 줄일 방법이 있을 것이다 import sys import cop.. [SW Expert Academy / 5658] 보물상자 비밀번호 1. 문제이해 입력값: N (4의 배수, 8이상 28이하) , K (K번째로 큰 수) N개의 숫자 (0이상 F이하 16진수) 유의해야 할 점: 보물 '상자' 이므로 4면이 존재하게 된다. 비밀번호는 시계방향으로 1칸씩 움직일수 있다. N이 4의 배수인 이유!! 한 면에 N//4개의 숫자들이 위치해 있다! 따라서 0번 ~~ N//4-1번 움직이는 경우만 보아도 전체 비밀번호 가짓수를 구할 수 있다. (이걸 몰라서 해맸음!) 출력값: 전체 비밀번호 중 오름차순으로 했을 때, K번째로 큰 수 ( 중복없이) 2. 문제 풀이 법 사용한 방법: 16진수를 10진수로 바꾸는 방법 1. 시작을 한 칸씩 미루면서 시계방향으로 움직이는것처럼 하려고 처음에 입력받는 비밀번호를 2번 반복해서 받았다. 2. 총 N//4 번 돌.. 이전 1 다음
