등굣길

출처 : 등굣길 Solution Python from collections import deque MOD = 1_000_000_007 def BFS(m, n, puddles): # 방문한 위치인지 확인 / 해당 위치까지 갈 수 있는 방법 / 0 인덱싱 넘버로 변경 visited = [[False]*m for _ in range(n)] board = [[0]*m for _ in range(n)] for x, y in puddles: visited[y-1][x-1] = True # 이동 가능한 경로(방향, (x,y), 상하좌우) direction = ((0,-1),(0,1),(-1,0),(1,0)) # Q에 현재 체크 중인 위치를 넣고 탐색 진행 Q = deque() Q.append((0,0)) board[0][0] = 1 while Q: x, y = Q.popleft() if visited[y][x]: continue visited[y][x] = True # 이동 방향 전부 체크 for dx, dy in direction: nx, ny = x+dx, y+dy # board 범위 안인지 확인 if (0 <= nx < m) & (0 <= ny < n): # visited인 경우 pass if visited[ny][nx]: continue board[ny][nx] += board[y][x] % MOD Q.append((nx,ny)) return board[n-1][m-1] % MOD def solution(m, n, puddles): # dp 배열 초기화 dp = [[0]*m for _ in range(n)] for x, y in puddles: dp[y-1][x-1] = -1 # 시작점(집)은 1로 설정 dp[0][0] = 1 for y in range(n): for x in range(m): # puddles 위치는 못 지나가므로 pass if dp[y][x] == -1: dp[y][x] = 0 continue # 현위치로 올 수 있는 다른 경로의 수도 + if y > 0: dp[y][x] += dp[y-1][x] if x > 0: dp[y][x] += dp[y][x-1] dp[y][x] %= MOD return dp[n-1][m-1] if __name__=="__main__": m, n = 4, 3 puddles = [[2, 2]] answer = solution(m, n, puddles) print(f"{answer==4} / 정답 : 4 / 출력 : {answer}") 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다. 물에 잠긴 지역은 0개 이상 10개 이하입니다. 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다. 입출력 예 m n puddles return 4 3 [[2, 2]] 4 입출력 예 설명

Programmers · 2025-08-31

N으로 표현

출처 : N으로 표현 Solution Python # 사칙연산 후 값 저장해주는 함수 def pmmd(visited, cnt, i1, i2): for n1 in visited[i1]: for n2 in visited[i2]: visited[cnt].add(n1+n2) visited[cnt].add(n1-n2) visited[cnt].add(n1*n2) if n2!=0: visited[cnt].add(n1//n2) def solution(N, number): # 중복 연산 방지를 위해 set으로 설정 visited = [set([0])] + [set([int(str(N)*i)]) for i in range(1,9)] # N과 number가 같다면, 1개만 사용하면 된다. if number==N: return 1 # 사용하게 될 수는 1~8까지 / 1개 사용하는 경우는 앞서 확인했으니 2부터 체크 for count in range(2, 9): for i in range(1, count): pmmd(visited, count, count-i, i) if number in visited[count]: return count return -1 if __name__ == '__main__': # testcase 1 : 4 print(solution(5, 12)) # testcase 2 : 3 print(solution(2, 11)) 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N number return 5 12 4 2 11 3 입출력 예 설명 예제 #1 문제에 나온 예와 같습니다. 예제 #2 11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다. ※ 공지 - 2020년 9월 3일 테스트케이스가 추가되었습니다.

Programmers · 2025-08-31

디스크 컨트롤러

Programmers · 2025-08-31

다리를 지나는 트럭

출처 : 다리를 지나는 트럭 Solution Python from collections import deque def solution(bridge_length, weight, truck_weights): answer = 1 Remain = deque(truck_weights) Bridge = deque() Bridge.append([Remain.popleft(),1]) while Remain or Bridge: # 우선 한칸씩 옮겨서 자리를 만든다. answer += 1 for truck in Bridge: truck[1] += 1 # 첫번째 트럭이 Bridge를 벗어났다면 제거해준다. if Bridge and Bridge[0][1] > bridge_length: Bridge.popleft() # Bridge 위에 truck이 올라갈 수 있는지 확인 후, 가능하면 추가 if Remain and sum(truck[0] for truck in Bridge)+Remain[0] <= weight: Bridge.append([Remain.popleft(), 1]) # # truck을 더 못 올리는 상황이라면, 첫번째 트럭을 최대한 한번에 옮기고 진행 # _, now = Bridge.popleft() # n = (bridge_length+1)-now # for truck in Bridge: truck[1] += n # answer += n return answer if __name__=="__main__": bridge_length = [2, 100, 100] weight = [10, 100, 100] truck_weights = [[7,4,5,6], [10], [10,10,10,10,10,10,10,10,10,10]] answer = [8, 101, 110] for b,w,t,a in zip(bridge_length, weight, truck_weights, answer): r = solution(b,w,t) print(f"{r==a} / 정답 : {a} / 출력 : {r}") ''' def solution(bridge_length, weight, truck_weights): # bridge에 0을 채워서 마지막 트럭이 나올 때까지 걸리는 시간을 0의 갯수로 표시 bridge = deque(0 for _ in range(bridge_length)) total_weight = 0 # sum(bridge)를 진행하는 것보다 별도의 변수를 만드는게 훨씬 효율적 answer = 0 # 원래 코드는 truck_weights.reverse()로 list 그대로 사용했으나, deque가 pop 작업이 훨씬 효율적 truck_weights = deque(truck_weights) while truck_weights: answer += 1 # 1턴의 시간이 지났음을 bridge 가장 좌측 값을 제거함으로써 표현 total_weight -= bridge.popleft() # 다음에 들어오는 truck의 무게를 bridge가 못버틴다면 0을 bridge에 추가 if total_weight + truck_weights[0] > weight: bridge.append(0) # 버틸 경우, 들어와야하는 truck을 bridge에 추가 else: truck = truck_weights.popleft() bridge.append(truck) total_weight += truck # 남은 truck이 없다면, bridge 위에 있는 truck이 전부 빠져나오는데 걸리는 시간을 더한다. answer += bridge_length return answer ''' 문제 설명 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5,6] 4 [7] [4,5] [6] 5 [7,4] [5] [6] 6~7 [7,4,5] [6] [] 8 [7,4,5,6] [] [] 따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다. solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요. 제한 조건 bridge_length는 1 이상 10,000 이하입니다. weight는 1 이상 10,000 이하입니다. truck_weights의 길이는 1 이상 10,000 이하입니다. 모든 트럭의 무게는 1 이상 weight 이하입니다. 입출력 예 bridge_length weight truck_weights return 2 10 [7,4,5,6] 8 100 100 [10] 101 100 100 [10,10,10,10,10,10,10,10,10,10] 110 출처 ※ 공지 - 2020년 4월 06일 테스트케이스가 추가되었습니다.

Programmers · 2025-08-31

폰켓몬

출처 : 폰켓몬 Solution Python def solution(nums): n = len(nums)//2 k = len(set(nums)) # 두 값 중 더 작은 값이 가질 수 있는 최대 포켓몬 종류 return n if n<k else k if __name__ == '__main__': testcase = [3,1,2,3] print(solution(testcase)) #2 testcase = [3,3,3,2,2,4] print(solution(testcase)) #3 testcase = [3,3,3,2,2,2] print(solution(testcase)) #2 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택 두 번째(1번), 세 번째(2번) 폰켓몬을 선택 두 번째(1번), 네 번째(3번) 폰켓몬을 선택 세 번째(2번), 네 번째(3번) 폰켓몬을 선택 이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다. 당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다. nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다. 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다. 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다. 입출력 예 nums result [3,1,2,3] 2 [3,3,3,2,2,4] 3 [3,3,3,2,2,2] 2 입출력 예 설명 입출력 예 #1 문제의 예시와 같습니다. 입출력 예 #2 6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다. 가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다. 입출력 예 #3 6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다. 가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

Programmers · 2025-08-31

[PCCP 기출문제] 4번 / 수레 움직이기

출처 : [PCCP 기출문제] 4번 / 수레 움직이기 Solution Python from collections import deque def check_move(n, m, y, x, log, maze): # maze 범위 벗어나는지 체크 if not ((0 <= y < n) & (0 <= x < m)): return False # 이미 지나온 위치인지 체크 if log[y][x]: return False # 진행 방향에 벽이 있는지 체크 if (maze[y][x] == 5): return False # 모든 경우 다 되면 True return True def move(n, m, y, x, log, maze): # 수레가 갈 수 있는 방향 / 상하좌우 direction = [(-1,0), (1,0), (0,-1), (0,1)] # 이동 가능한 좌표 값은 리스트에 저장 result = [] # 4방향으로 수레를 이동시킬 수 있는지 체크 for i in range(4): dy, dx = direction[i][0], direction[i][1] # check_move 함수를 통해 체크하고 if check_move(n, m, y+dy, x+dx, log, maze): # 유효한 위치라면 result에 추가 result.append((y+dy, x+dx)) # result를 반환해준다. return result def bfs(maze, ry, rx, by, bx, n, m): # 최단 횟수 저장할 변수 answer = 0 # 방문용 배열 만들기 (ry, rx, by, bx) visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)] # 최근 기록 배열 만들기 log_red = [[False] * m for _ in range(n)] log_blue = [[False] * m for _ in range(n)] # 스타트 위치는 방문으로 표시해준다. log_red[ry][rx] = True log_blue[by][bx] = True # BFS 탐색으로 최단 횟수를 알기 위해, Queue 생성 Q = deque() Q.append((ry, rx, by, bx, log_red, log_blue, 0)) # BFS 탐색 시작 while Q: # Q의 값을 꺼내온다. ry, rx, by, bx, rV, bV, cnt = Q.popleft() # 방문한 장소라면 패스 if visited[ry][rx][by][bx]: continue # 아니라면 방문 체크 visited[ry][rx][by][bx] = True # 빨간 수레, 파란 수레 도착지점 체크 변수 chk_r, chk_b = False, False # 빨간 수레가 도착지점 도착 시 True if maze[ry][rx] == 3: chk_r = True # 파란 수레가 도착지점 도착 시 True if maze[by][bx] == 4: chk_b = True # 둘 다 도착지점 도착 완료했다면, if chk_r & chk_b: # answer에 현재까지 카운트 저장 후 탈출 answer = cnt break # 빨간 수레, 파란 수레 둘 다 도착 못 함 elif ((not chk_r) & (not chk_b)): # 빨간 수레 유효 좌표 체크 nrs = move(n, m, ry, rx, rV, maze) # 파란 수레 유효 좌표 체크 nbs = move(n, m, by, bx, bV, maze) # 빨간 수레 도착, 파란 수레 미도착 elif (chk_r & (not chk_b)): # 파란 수레 유효 좌표 체크 nbs = move(n, m, by, bx, bV, maze) # 빨간 수레는 현위치 고정! nrs = [(ry, rx)] # 빨간 수레 미도착, 파란 수레 도착 elif ((not chk_r) & chk_b): # 빨간 수레 유효 좌표 체크 nrs = move(n, m, ry, rx, rV, maze) # 파란 수레는 현위치 고정! nbs = [(by, bx)] # 빨간 수레 이동 가능 위치와 파란 수레 이동 가능 위치 탐색 for nry, nrx in nrs: for nby, nbx in nbs: # 현재 이동한 위치의 두 수레가 겹치면 패스 if ((nry == nby) & (nrx == nbx)): continue # 만약 서로 이동한 위치가 이전 위치를 바꾼거라면 패스(겹치는 이동) if (((nry==by)&(nrx==bx))and((nby==ry)&(nbx==rx))): continue # 걸리는 부분 없이 이동가능하다면, 해당 위치로 옮겨준다. cnt += 1 # 해당 위치 방문 체크를 해준다. rV[nry][nrx], bV[nby][nbx] = True, True # Q 에 해당위치들을 넣어준다. Q.append((nry, nrx, nby, nbx, rV, bV, cnt)) # for 문 내에서 다음 위치들 확인할 때 누적연산 되므로 cnt -= 1 rV[nry][nrx], bV[nby][nbx] = False, False # answer 그대로 return return answer def solution(maze): n = len(maze) # 세로 길이 m = len(maze[0]) # 가로 길이 # 수레들 스타트 위치 찾기 for y in range(n): for x in range(m): # 빨간 수레 위치 저장 if maze[y][x] == 1: ry, rx = y, x # 해당 위치는 빈칸으로 초기화 maze[y][x] = 0 # 파란 수레 위치 저장 elif maze[y][x] == 2: by, bx = y, x # 해당 위치는 빈칸으로 초기화 maze[y][x] = 0 # BFS 탐색 함수에 넣고, 최단 횟수를 answer에 저장 answer = bfs(maze, ry, rx, by, bx, n, m) return answer 문제 설명 n x m 크기 격자 모양의 퍼즐판이 주어집니다. 퍼즐판에는 빨간색 수레와 파란색 수레가 하나씩 존재합니다. 각 수레들은 자신의 시작 칸에서부터 자신의 도착 칸까지 이동해야 합니다. 모든 수레들을 각자의 도착 칸으로 이동시키면 퍼즐을 풀 수 있습니다. 당신은 각 턴마다 반드시 모든 수레를 상하좌우로 인접한 칸 중 한 칸으로 움직여야 합니다. 단, 수레를 움직일 때는 아래와 같은 규칙이 있습니다. 수레는 벽이나 격자 판 밖으로 움직일 수 없습니다. 수레는 자신이 방문했던 칸으로 움직일 수 없습니다. 자신의 도착 칸에 위치한 수레는 움직이지 않습니다. 계속 해당 칸에 고정해 놓아야 합니다. 동시에 두 수레를 같은 칸으로 움직일 수 없습니다. 수레끼리 자리를 바꾸며 움직일 수 없습니다. 예를 들어, 아래 그림처럼 n = 3, m = 2인 퍼즐판이 있습니다. 속이 빨간색인 원은 빨간색 수레를 나타냅니다. 속이 파란색인 원은 파란색 수레를 나타냅니다. 테두리가 빨간색인 원은 빨간색 수레의 도착 칸을 나타냅니다. 테두리가 파란색인 원은 파란색 수레의 도착 칸을 나타냅니다. 위 퍼즐판은 아래와 같은 순서로 3턴만에 풀 수 있습니다. 빨간색 사선이 처진 칸은 빨간색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 빨간색 수레는 빨간색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다. 파란색 사선이 처진 칸은 파란색 수레가 방문했던 칸을 나타냅니다. 규칙에 따라 파란색 수레는 파란색 사선이 처진 칸(방문했던 칸)으로는 이동할 수 없습니다. 위처럼 동시에 수레를 같은 칸으로 움직일 수는 없습니다. 퍼즐판의 정보를 나타내는 2차원 정수 배열 maze가 매개변수로 주어집니다. 퍼즐을 푸는데 필요한 턴의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 퍼즐을 풀 수 없는 경우 0을 return 해주세요. 제한사항 1 ≤ maze의 길이 (= 세로 길이) ≤ 4 1 ≤ maze[i]의 길이 (= 가로 길이) ≤ 4 maze[i][j]는 0,1,2,3,4,5 중 하나의 값을 갖습니다. maze[i][j] 의미 0 빈칸 1 빨간 수레의 시작 칸 2 파란 수레의 시작 칸 3 빨간 수레의 도착 칸 4 파란 수레의 도착 칸 5 벽 빨간 수레의 시작 칸, 빨간 수레의 도착 칸, 파란 수레의 시작 칸, 파란 수레의 도착 칸은 퍼즐판에 1개씩 존재합니다. 입출력 예 maze result [[1, 4], [0, 0], [2, 3]] 3 [[1, 0, 2], [0, 0, 0], [5, 0 ,5], [4, 0, 3]] 7 [[1, 5], [2, 5], [4, 5], [3, 5]] 0 [[4, 1, 2, 3]] 0 입출력 예 설명 입출력 예 #1 문제 예시와 같습니다. 입출력 예 #2 7턴만에 퍼즐을 풀 수 있습니다. 다른 방법으로도 퍼즐을 풀 수 있지만 7턴보다 빠르게 풀 수는 없습니다. 입출력 예 #3 다음 턴에 파란색 수레가 파란색 수레의 도착 칸에 위치한 후 고정되어 빨간색 수레가 빨간색 수레의 도착 칸에 도착할 수 없게 됩니다. 퍼즐을 풀 수 없으므로 0을 return 해야 합니다. 입출력 예 #4 수레는 서로 위치를 바꾸면서 움직일 수 없으므로 퍼즐을 풀 수 없습니다. 따라서 0을 return 해야 합니다.

Programmers · 2025-08-17

kangspa.com

About Me

Programmers