본문 바로가기

PYTHON

 (12)
[ SW Expert Academy / 4839 ] 이진탐색 1. 문제 이해 입력값: P (1 이상) PA PB 유의해야 할 점: 책의 페이지가 대상임으로 숫자 1 부터탐색 대상이 됩니다. middle +1 , middle -1 부터 범위가 정해지는것이 아니라 middle 부터 범위가 다시 정해집니다. // 문제 꼭 읽어야 하는 부분 PA: A 가 찾고싶은 페이지 PB : B가 찾고싶은 페이지 출력 값 누가 더 빨리 원하는 페이지를 찾았는가? (비기면 0 출력) 2. 문제 풀이 법 사용한 방법: 이진 탐색 Start - 탐색 대상의 첫번째 원소 위치 End - 탐색 대상의 마지막 원소 위치 만약, Start > End 가 된다면 해당 범위에 찾고자 하는 값이 없다는것이다 --> FAIL 3. 어려웠던 점 문제를 읽어야 풀 수 있따. middle 페이지
[ 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를 실..
[백준 / 14503 ] 로봇청소기 1. 문제 이해 입력값: N, M (3 이상 50 이하, 세로 가로) R,C,d (위치좌표 , 방향 (북동남서 0 1 2 3) 0 또는 1 (N 줄에 걸쳐) 유의해야 할 점: 1. 로봇청소기가 있는 칸의 상태는 항상 빈 칸 2. 이미 청소되어있는 칸 청소 불가 3. 벽 통과 물가 출력 값: 청소 한 칸의 수 2. 문제 풀이 법 문제에서 주어진 조건들을 코드로 짜면되는것같다. 3. 어려웠던 점 1.문제 이해를 못해서 힘들었었다. 2. // 랑 % 헷갈려서 못했다. dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] def iswall(y,x): if 0
[ 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..

티스토리툴바