본문 바로가기

전체 글

 (119)
[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" 또는..
[BOJ] 1937. 욕심쟁이 판다(Python) / DFS + DP 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 처음 이 문제를 DFS 각 위치별 완전탐색으로 접근했더니 답은 금방 구했지만, 바로.. 시간초과가 떴다.. 아니나 다를까 DFS + DP의 콜라보로 풀어야 하는 문제였다. 즉, Memoization을 해야한다는 것! Memoization은 이미 한 번 탐색한 위치에 대해서는 재귀로 더 탐색할 필요 없이 그냥 그 값을 가져다 사용할 수 있도록 해당 위치별 값을 미리 저장한 DP Table을 만들어두는 것이 포인트다! 즉, 불필요한 반복 연산 없이 한 번 ..
[BOJ] 20165. 인내의 도미노 장인 호석(Python) / Simulation 20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net # 문제 이해 못 하고 1시간 30분동안 시간 날리고, 문제 이해하고 다 지우고 새로 다시 풀어서 28분만에 pass 사용 알고리즘 : Simulation + Recursive Function 공격, 수비 전에 미리 해둔 것 공격 시작 좌표, 수비 시작 좌표 Input 받으면서 다루기 좋게 indexing 해준다. 수비할 때, 원래 맵에 있는 도미노 정보로 복원해줘야 하기 때문에 raw배열에 board맵을 복사해놓는다. 동서남북 E, W, S, N에..
[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..
[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..
[SWEA] 2112. 보호필름(Python) / DFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 1시간 1분 소요 많이 풀어본 유형이라 큰 고민 없이 풀어낸 문제다. 사용 알고리즘 : DFS 조합 우선, 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다. 고 했으니, 성능검사 함수를 만들어줬다.(testPerformance()) 동일한 특성의 셀들이 K개 이상 연속으로 있는 경우에만 성능검사 통과 한 열의 동일 셀이 K 미만이면 즉시 False 리턴 이중 포문 통과하면 True 리턴하여 ..
[BOJ] 1038. 감소하는 수(Python) / DFS 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 사용 알고리즘 : DFS 10보다 작은 수에 대해서는 input값 그대로 출력 depth를 최대 1..
[BOJ] 1261. 알고스팟(Python) / BFS www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 이 문제는 어제 풀었던 미로만들기 문제 2021.03.25 - [Problem Solving/boj] - [BOJ] 2665. 미로만들기(Python) / BFS와 완전 같은 문제이다. 어제 풀었던 덕인지 30분 정도 소요했다. 사용 알고리즘 : BFS check 배열을 주어진 맵의 크기와 같게 만들고, 최댓값으로 초기화했다. 빈 공간일 때와 벽을 만났을 때 모두 이동 위치에 있는 값을 최..

티스토리툴바