본문 바로가기

로봇이아닙니다

백준 11048 / 이동하기 다이나믹 프로그래밍 문제 가중치는 같지만 사탕을 가져올 수 있는 최대값을 문제이기 때문에 BFS로 풀 수 없다. 다양한 점화식이 있지만 가장 간단한 방법을 사용했다. D[i][j]가 i,j에 도착했을때 가진 사탕의 최대값, map[i][j]가 i,j에 놓인 사탕의 개수라 가정했을 때, 위에서 왔을 경우 : D[i][j] = D[i-1][j] + map[i][j] 왼쪽에서 왔을 경우 : D[i][j] = D[i][j-1] + map[i][j] 왼쪽 위 대각선에서 왔을 경우 : D[i][j] = D[i-1][j-1] + map[i][j] 이기 떄문에 D[i][j]는 max(D[i-1][j], D[i][j-1], D[i-1][j-1]) + map[i][j]이 된다. 문제의 조건인 (1,1)에서 시작하여 (n,..
백준 15558 / 점프 게임 최단거리가 있으면 갈 수 있다라는 뜻이기 떄문에 BFS로 풀 수 있다. n보다 큰 모든 칸을 갈 수 있는 칸으로 설정했고, k의 최대치가 100000으로 맵의 크기를 200000으로 설정했다. tuple을 사용하여 시간초를 추가해주었다. 시간초는 뒤로 이동하는 경우에만 영향을 준다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#include#include#include#include#include using namespace std; int map[2][200000];bool check[2..
백준 6087 / 레이저 통신 하다가 로직이 너무 무식한데? 싶으면 빨리빨리 손절하고 다시 세우자 최단경로가 아닌 방향을 최소 몇번 꺾어야 되는지 묻는 문제이다. 방법이 도무지 떠오르지 않아 다른 사람들의 코드를 참고했다. (ㅠㅠ) 로직은 이렇다. 첫번째 C(시작점)에서 4방향으로 벽이나 밖에 부딪힐때까지 선을 긋는다. (선을 그으면서 dist를 체크해준다.) 선이 그어진 부분에서 다시 4방향으로 선을 긋는다. (이미 선이 그어진 곳이라면 긋지 않는다.) 이를 반복하면 갈 수 있는 모든 빈칸에 dist가 체크되는데 도착점의 dist에서 1를 빼주면 답이다. 결국 거울의 개수를 생각하면서 푸는 문제가 아닌, 몇번의 직선으로 도착점에 도달할 수 있는 가에 대한 문제로 생각해서 풀면 더욱 쉽다. 코드 123456789101112131415..
백준 4991 / 로봇 청소기 총 n개의 쓰레기를 치우는 최소거리는 치우는 순서에 따라 다르다. 그렇기에 1,2......, 최대 10번째 쓰레기를 치우는 순서를 모두 정한 후 최소값을 구하면 된다. 총 10!(>300만)개의 경우의수가 생기니 next_permutation 안에서 bfs를 매번 돌리면 시간초과가 뜬다. 해결법은 로봇청소기와 쓰레기 n개 사이의 거리를 모두 구해놓는 것이다. 쓰레기가 10개라고 가정하면 로봇청소기와 쓰레기 사이의 거리 : 10개 쓰레기와 쓰레기 사이의 거리 : 10C2개 총 55개의 거리를 BFS로 구하면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565..
백준 9328 / 열쇠 난 아직 멀었다는 생각이 들었다. 쉽게 풀 수 있는 문제를 어렵게 접근했던 것 같다. 처음엔 문제의 조건 그대로 구현하려했다. BFS를 돌리되, priority_queue를 이용하여 획득한 파일의 개수, 좌표, 획득한 키(string으로 저장), 획득한 파일의 좌표 를 계속 넘기며 정답을 찾으려 했다. 50%에서 자꾸 메모리 초과가 나서 다 지우고 로직을 새로 세웠다. 문제는 쉽다. 우선, 상근이는 빌딩 밖으로 나갈 수 있기 때문에 맵 주변에 빈칸을 생성해준다. 열쇠나 파일을 찾을 때마다 다시 0,0,으로 돌아와 bfs를 돌리면 된다. 문을 열거나 파일을 찾으면 맵을 빈칸으로 갱신하고 다시 0,0으로 돌아온다면 그 문을 지나가거나 파일이 있던 곳에 접근할 수 있다. 열쇠를 획득하는 건 map을 사용했다...
백준 9376 / 탈옥 이 문제를 단번에 풀었다면 나는 당장 하산했을 것이다. 처음 문제를 풀었을 때 여러가지 해결법이 떠올랐다. 그중 가장 그럴 듯 했던건 모든 문의 좌표를 받고 0개를 열었을 때, 1개를 열었을 때, 2개를 열었을 때 ...... n개를 열었을 때 탈옥에 성공하는 문의 최소개수를 구하는 방법이었는데. 한 케이스당 bfs를 2번씩 해야되니 시간초과에 걸렸다. 맵이 작았으면 괜찮았을 텐데.. 이 문제의 해결법은 이렇다. 죄수1과 죄수2 그리고 맵 밖에 있는 사람이 있다고 가정하자. (문제에 힌트가 있다. 상근이는 어디에나 있을 수 있다고..) 맵도 바꿔준다. 맵의 가장자리 부분에 빈공간(.)를 추가시켜준다. 그리고 죄수1과 죄수2 밖의사람의 모든 dist를 bfs로 구한다 이떄 문이 아닌 빈 공간을 지나가는 경..
백준 12851 / 숨바꼭질 2 다른 숨바꼭질 문제는 경로를 출력하는 문제였던 것 같다. 그떄 여러가지 답이 가능해서 '스페셜 저지'가 붙어있던거 같고. 이 문제는 최단경로를 출력함과 동시에 몇가지 경로가 가능한지에 대해 묻는 문제다. 최단경로를 출력하는 방법은 숨바꼭질4(https://naivep.tistory.com/22) 참고. 최단으로 갈 수 있는 경로가 몇개 있는지 알아내는 방법은 현재 인덱스까지 올 수 있는 방법이 몇개 있는지 담는 cnt[인덱스] 배열을 만들어 check가 true임에도 next의 위치에 가는 경로가 최단경로와 같다면 cnt를 늘려주는 방법이다. 그림으로 보면 5까지 가는 최단경로가 2, 9까지 가는 최단경로가 2라고 가정하자. 10은 아직 들린적 없다. 우선 5가 10에 접근한다. dist[10]은 3이된..
맵(map) 클래스 배열의 인덱스로 String이나 큰 수를 넣고 싶은데 불가능하다면, #include map은 STL(Standard Template Library)이 제공하는 자료구조 중 하나. map의 배개변수 Key - map에 저장되는 키 데이터 형식Type - map에 저장되는 요소 데이터 형식Traits - 함수 개체를 제공하는 형식은 map 내에서의 상대적인 순서를 결정하는 정렬 키로 두 요소 값을 비교 가능Allocator - map의 메모리 할당 및 할당 취소에 대한 세부 정보를 캡슐화하는 저장된 할당자 개체를 나타냄 map 클래스 특징 - 연결된 키 값을 기반으로 요소 값을 효율적으로 검색하는 다양한 크기의 컨테이너.- 이는 해당 요소에 엑세스할 수 있는 양방향 반복기를 제공하기 떄문에 되돌릴 수 있다...

티스토리툴바