본문 바로가기

분류 전체보기107

DP 풀이방법 5가지 정리 - 백준 11048번 : 이동하기 Python 파이썬 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 방법1 : Top-Down 문제가 점점 작아지는 방식으로 접근 목적지까지 어떻게 왔는지에 대해서 생각하며 접근 결론에 도달하기까지의 과정에 대해 생각하며 접근 dp[i][j] : (1,1)에서 시작하여 (N,M)까지 가는 중에 (i, j) 까지 갔을 때의 가진 최대 사탕의 수 왼쪽에서 온 경우 : (i, j-1)에서 온 경우 왼쪽 위에서 온 경우 : (i-1, j-1)에서 온 경우 .. 2022. 1. 11.
백준 11048 : 이동하기 - 파이썬 Python https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 생각하기 가져올 수 있는 사탕의 최대를 구하는 것이기 때문에 생각을 했다 DFS로 모든 경우를 다 해봐? 규칙 같은 것을 찾아서 DP로 만들어볼까? DFS로 풀면 시간초과가 발생할 것 같다는 생각이 들었다. 1000 * 1000 인데 각 경우가 3가지 경우만 고려하더라도 각 칸은 세가지의 경우로 뻗어나갈 가지수를 가지고 있으므로 최대 가로 세로 1000칸이라면 3000000의 가지수.. 2022. 1. 6.
Spring Boot - Test 코드 작성 Spring 과 Integration하여 Test @RunWith(SpringRunner.class) spring과 integration하여서 메모리 모드로 엮는다 junit4가 지원하는 어노테이션으로, @Autowired @MockBean 이 붙어있는 것들만 application context로 로딩함 Runner - test 프로세스들을 계획하고 실행하는 클래스 @SpringBootTest application context를 모두 적재하여 RunWith를 사용하였을 때보다 무겁다 @Transactional 모든 테스트를 한 후에 roll-back을 하기 위함 @RunWith(SpringRunner.class) @SpringBootTest // unit test 할때는 @DataJpaTest를 써주는.. 2022. 1. 4.
백준 16954번 : 움직이는 미로 탈출 - 파이썬 Python https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 생각하기 시간이 1초씩 지남에 따라서 1. 욱제가 이동하고 2. 벽이 바뀐다 시간이 1초씩 바뀌는 것을 단계별로 나타내기 위해서 bfs를 사용한다 구현하기 큐에다가 row, col 좌표, 흘러간 시간을 묶어서 append 시킨다 큐에서 popleft시키면서 흘러간 시간이 바뀐 경우 체스판의 벽을 한줄씩 내린다 주의할 점 1 체스판의 벽이 한줄씩 내려가다보면 가장 위쪽행은 모두 벽이 없는.. 2022. 1. 1.

티스토리툴바