파이썬62 [BOJ] 12851. 숨바꼭질 2(Python) / BFS 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 해당 번호까지 갈 수 있는 최소 시간과 그 시간에 갈 수 있는 방법은 몇 가지인지 추가적으로 구하는 문제이다! 예전에 숨바꼭질 1 풀었던 문제와 비슷하게 접근했는데, 추가로 구해야 하는 가짓 수 때문에 좀더 머리를 썼다. 사용 알고리즘 : BFS 최단 경로 알고리즘 먼저, K가 N보다 작거나 같다면 -1로 계속 가는 방법 뿐이다. 그러므로 N-K와 1가지 방법을 출력한다. 그렇지 않다면 bfs 함수를 실행해 최소 시간과 경우의.. 2021. 4. 1. [BOJ] 2174. 로봇 시뮬레이션(Python) / Simulation 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 문제명 그대로 주어진 대로 로봇을 움직이는 Simulation 문제이다. # 1시간 59분 소요. 한 번에 pass. 시간, 메모리 1위를 달성 사용 알고리즘 : 구현 맵은 사용하지 않고, 로봇 정보와 위치 정보를 모두 파이썬 Dictionary를 사용했다. 문제 풀기 전에 미리 해둔 것 상하좌우 delta 좌표로 구현(dr, dc) 상하좌우 => NSWE => 0, 1, 2, 3으로 딕셔너리에 방향 정보 저장(dirInfo) "L" 또는.. 2021. 4. 1. [BOJ] 1937. 욕심쟁이 판다(Python) / DFS + DP 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 처음 이 문제를 DFS 각 위치별 완전탐색으로 접근했더니 답은 금방 구했지만, 바로.. 시간초과가 떴다.. 아니나 다를까 DFS + DP의 콜라보로 풀어야 하는 문제였다. 즉, Memoization을 해야한다는 것! Memoization은 이미 한 번 탐색한 위치에 대해서는 재귀로 더 탐색할 필요 없이 그냥 그 값을 가져다 사용할 수 있도록 해당 위치별 값을 미리 저장한 DP Table을 만들어두는 것이 포인트다! 즉, 불필요한 반복 연산 없이 한 번 .. 2021. 4. 1. [BOJ] 20165. 인내의 도미노 장인 호석(Python) / Simulation 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net # 문제 이해 못 하고 1시간 30분동안 시간 날리고, 문제 이해하고 다 지우고 새로 다시 풀어서 28분만에 pass 사용 알고리즘 : Simulation + Recursive Function 공격, 수비 전에 미리 해둔 것 공격 시작 좌표, 수비 시작 좌표 Input 받으면서 다루기 좋게 indexing 해준다. 수비할 때, 원래 맵에 있는 도미노 정보로 복원해줘야 하기 때문에 raw배열에 board맵을 복사해놓는다. 동서남북 E, W, S, N에.. 2021. 3. 30. [BOJ] 3079. 입국심사(Python) / Binary Search 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 입국 심사대의 개수 N과, 심사를 받을 인원 M이 주어지고, 각 입국 심사대의 심사에 걸리는 시간이 주어질 때 모든 인원이 심사를 받는 최소 시간을 구하는 문제 사용 알고리즘 : 이분 탐색 Binary Search 최소, 최대 시간을 left, right라 두고 그 중간값을 mid로 하여 전원 total 이 입국심사 가능한 시간이라면 mid-1를 right로 최대 시간을 줄여 다음 턴 때의 탐색 범위를 좁힌다. 불가능하다면 left를 mid + 1.. 2021. 3. 30. [SWEA] 2105. 디저트 카페(Python) / Brute Force SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 1시간 32분 소요 사용 알고리즘 : Brute Force + Simulation 모든 경우의 수에 대해 다 검사해야 하는 완전탐색 문제이다. 마름모를 그릴 때 시작점이 되는 점은 행은 0부터 N-3까지, 열은 1부터 N-2까지의 영역 안에 들어야 한다. makeDistance(sr, sc) 함수에서 시작점의 위치 행, 열 좌표를 인자로 넣으면 시작점에서 대각선 사각형을 이루는 왼쪽, 오른쪽의 대각선 한 변이 될 수 있는 각각의 길이를 이중 포문으로 구한다. 이 때, 시작점의 반대편에 있는 꼭지점의 행 위치가 맵을 넘어가면 안 되므로, 그 경우는 if sr+l.. 2021. 3. 30. 이전 1 ··· 3 4 5 6 7 8 9 ··· 11 다음
